Decision Optimization

 View Only
  • 1.  accelerate optimization

    Posted Sun July 05, 2020 09:36 AM
    Hi all,

    I am working on a multi-commodity flow problem with about 29 orders, 50 arcs and 150 services on my transportation network. I find CP optimiser can find good solution in first 50 seconds, and cannot reduce the gap after 85 seconds. I think the process which proves the current solution is an optimal solution is really time-consuming. So do you know who to reduce the running time? like adding cuts? 


    ------------------------------
    Dario Pisinger
    ------------------------------

    #DecisionOptimization


  • 2.  RE: accelerate optimization

    Posted Sun July 05, 2020 09:42 AM
    Attachment is the output of 10-min running. I also did a 3-hour running, it cannot find another solution after 85 seconds. Is my problem too complex to consume lots of time? or is there something wrong with my code? Should I use decomposition or other method to accelerate my optimisation?



    ------------------------------
    Dario Pisinger
    ------------------------------



  • 3.  RE: accelerate optimization

    IBM Champion
    Posted Sun July 05, 2020 12:19 PM
    Decomposition and adding cuts sound like things you would do with a mixed integer linear program. CP Optimizer is a constraint solver, designed with particular attention to solving scheduling problems. If you are concerned about provable optimality, you might try using CPLEX (with a MIP model) instead. If it turns out CPLEX takes a while to get a solution as good as what you have above, you could run CP Optimizer first and then use the solution from it as a MIP start for CPLEX.

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



  • 4.  RE: accelerate optimization

    Posted Mon July 06, 2020 01:46 AM
    Hi,

    about "you could run CP Optimizer first and then use the solution from it as a MIP start for CPLEX"

    You could use

    Hybrid between CPO and CPLEX in OPL

    in

    https://www.linkedin.com/pulse/how-opl-alex-fleischer/

    regards

    ------------------------------
    ALEX FLEISCHER
    ------------------------------



  • 5.  RE: accelerate optimization

    Posted Thu July 09, 2020 06:38 AM
    The common way to improve solution convergence of constraint programs is to increase the strength of the formulation, that is to make the model achieving more domain reduction.
    For this purpose one can:
    - Use global constraints if the CP Optimizer ones are suited to your problem. Global constraints achieve more domain reduction thanks to a broader view and specialized algorithms (a list is here https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cpo.help/CP_Optimizer/User_manual/topics/constraints_specialized.html)
    - Add extra constraints for expressing mathematical relations that are implicit in the model (these constraints are, strictly speaking, redundant but can provide more domain reduction)
    - Factorize common expressions such that the domain reduction achieved by one constraint on this expression is also "visible" to the others
    To check the strength of a model you can use the runSeeds feature that runs the same model with different random seeds : https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cpo.help/refcppcpoptimizer/html/classes/IloCP.html#method_runSeeds
    For your model, 10 runs with a time limit of 200s will already give a valuable result.

    ------------------------------
    Philippe Refalo
    ------------------------------