Decision Optimization

Expand all | Collapse all

Obtaining feasible solution at each node in branch-and-cut with docplex python

  • 1.  Obtaining feasible solution at each node in branch-and-cut with docplex python

    Posted 26 days ago
    Hi, 

    I have tested a MIP problem in branch-and-cut and got those results below.

    --------------------------------------------------------------------------------------------------------
    Reduced MIP has 33 rows, 132 columns, and 288 nonzeros.
    Reduced MIP has 12 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.00 sec. (0.18 ticks)
    Found incumbent of value 396952.000000 after 0.02 sec. (0.30 ticks)
    Probing time = 0.00 sec. (0.04 ticks)
    Tried aggregator 1 time.
    MIP Presolve eliminated 22 rows and 88 columns.
    Reduced MIP has 11 rows, 44 columns, and 96 nonzeros.
    Reduced MIP has 4 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.00 sec. (0.07 ticks)
    Probing time = 0.00 sec. (0.01 ticks)
    Tried aggregator 1 time.
    Detecting symmetries...
    Reduced MIP has 11 rows, 44 columns, and 96 nonzeros.
    Reduced MIP has 4 binaries, 0 generals, 0 SOSs, and 0 indicators.
    Presolve time = 0.00 sec. (0.05 ticks)
    Probing time = 0.00 sec. (0.01 ticks)
    Clique table members: 1.
    MIP emphasis: balance optimality and feasibility.
    MIP search method: dynamic search.
    Parallel mode: deterministic, using up to 16 threads.
    Root relaxation solution time = 0.00 sec. (0.02 ticks)

    Nodes Cuts/
    Node Left Objective IInf Best Integer Best Bound ItCnt Gap

    * 0+ 0 277443.0000 192888.0000 30.48%
    0 0 272456.4088 2 277443.0000 272456.4088 7 1.80%
    * 0+ 0 273984.0000 272456.4088 0.56%
    * 0 0 integral 0 272484.0000 Fract: 1 8 0.00%
    0 0 cutoff 272484.0000 272484.0000 8 0.00%
    Elapsed time = 0.02 sec. (2.92 ticks, tree = 0.01 MB, solutions = 5)
    --------------------------------------------------------------------------------------------------------

    Now I am trying to get feasible solutions found at each iteration in python docplex for MIP problem.

    Is it possible to obtain feasible solutions found at each iteration?

    Also I would like to ask whether is it possible to get objective value at each node in branch-and-cut.

    Thank you.

    ------------------------------
    Sangjeong Lee
    ------------------------------


  • 2.  RE: Obtaining feasible solution at each node in branch-and-cut with docplex python

    Posted 26 days ago
    Assuming that by "get feasible solutions" you mean get each new incumbent as it is found, you could do this with a generic callback in the "Candidate" context. To get the objective value at each feasible node, I believe you could use a generic callback in the "Relaxation" context.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 3.  RE: Obtaining feasible solution at each node in branch-and-cut with docplex python

    Posted 26 days ago
    Thank for your kind reply.
    Here is my brief code.
    --------------------
    from docplex.mp.model import Model
    mdl = Model('test')

    A = [(j, r) for j in range(3) for r in range(5) ]
    B = [(j, r, v) for j in range(3) for r in range(5) for v in range(4)]
    z= mdl.integer_var_dict(A, lb=0, ub=1, name='z')
    weight = mdl.continuous_var_dict(B, lb=0, ub=1, name='weight')
    N_weight = mdl.continuous_var_dict(B, lb=0, ub=1, name='N_weight')

    mdl.add_constraints( mdl.sum(z[j, r] for r in range(5) ) == 1 for j in range(3) )
    mdl.add_constraints( mdl.sum(weight[j, r, v] for v in range(4) ) == z[j, r] for j in range(3) for r in range(5) )
    mdl.add_constraints( mdl.sum(N_weight[j, r, v] for v in range(4) ) == z[j, r] for j in range(3) for r in range(5) )

    mdl.add_constraints( scheduled_W[j]>= initial_w+mdl.sum(time[j, r, v]*weight[j, r, v]+N_time[j, r, v]*N_weight[j, r, v] for r in range(5) for v in range(4) ) for j in range(1) )
    mdl.add_constraints( scheduled_W[j]>= scheduled_W[j-1]+mdl.sum(time[j, r, v]*weight[j, r, v]+N_time[j, r, v]*N_weight[j, r, v] for r in range(5) for v in range(4) ) for j in range(1,3) )

    mdl.minimize(mdl.sum(price*consumption[j, r, v]*weight[j, r, v]+H_price*N_consumption[j, r, v]*N_weight[j, r, v] for j, r, v in B))
    mdl.print_information()
    solution = mdl.solve(log_output=True)
    print(solution)


    -------------------
    So I would like to ask is it possible to use cplex function to get feasible solution even though I used docplex to get solution?

    I have found the related docement to the relaxation context,  https://www.ibm.com/docs/en/icos/20.1.0?topic=classes-cplexcallbackscontexttype.
    In python 20.1.0.0

    But I am still confused about how to import the callbackcontext class in python and how to get the incumbent  from solutions obtained in docplex.
    I have tried 
    from cplex.CALLBACKCONTEXT import *
    But it seems that there is no callbackcontext provided in python API.

    What I found is 

    from cplex.callbacks import MIPCallback
    from cplex.callbacks import HeuristicCallback

    Does these two class have functions of giving new incumbents as it is found and how to use with solutions obtained by docplex?
     
    Thank you.


    ------------------------------
    Sangjeong Lee
    ------------------------------



  • 4.  RE: Obtaining feasible solution at each node in branch-and-cut with docplex python

    Posted 26 days ago
    Callback examples based on the standard callback hierarchy are now part of docplex examples.
    See for example this one based IncumbentCallback on https://github.com/IBMDecisionOptimization/docplex-examples/blob/master/examples/mp/callbacks/incumbent_callback.py

    For an example based on the generic callback, see https://github.com/PhilippeCouronne/docplex_contribs/blob/master/docplex_contribs/src/docplex_gencb.py

    ------------------------------
    Vincent Beraudier
    ------------------------------



  • 5.  RE: Obtaining feasible solution at each node in branch-and-cut with docplex python

    Posted 26 days ago
    Thank for your reply.

    I have just found that I need to import Modelcallbackmixinto use callback function in cplex callbacks.
    Then I could define the customized callback function just like examples you share

    import cplex.callbacks as cpx_cb
    from docplex.mp.callbacks.cb_mixin import ModelCallbackMixin

    class CustomIncumbentCallback(ModelCallbackMixin, cpx_cb.IncumbentCallback):
    ……
    And this customized callback function could be combined with my model in docplex as follows.

    mdl.register_callback(CustomIncumbentCallback)


    I also found that docplex provides listner function to monitor how the solutions are improved.
    from docplex.mp.progress import *
    mdl.add_progress_listener(TextProgressListener())
    mdl.solve(clean_before_solve=True)

    link:https://github.com/IBMDecisionOptimization/docplexexamples/blob/master/examples/mp/jupyter/progress.ipynb

    I appreciate your help and good examples.


    ------------------------------
    Sangjeong Lee
    ------------------------------