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_runSeedsFor your model, 10 runs with a time limit of 200s will already give a valuable result.
------------------------------
Philippe Refalo
------------------------------
Original Message:
Sent: Sun July 05, 2020 09:36 AM
From: Dario Pisinger
Subject: accelerate optimization
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