Among other things, CP Optimizer is using a relaxation for scheduling problems which is solved by CPLEX. Depending on the cost function, this can provide a more or less tight lower bound on the cost. You can find some more details here around slide 43.
https://www.slideshare.net/PhilippeLaborie/planningscheduling-with-cp-optimizer
Best regards,
Paul
------------------------------
Paul Shaw
------------------------------
Original Message:
Sent: Mon February 28, 2022 04:50 AM
From: Mohamed Awad
Subject: Question of optimality gap of CP solver
Thanks a million Paul for your great help. Really appreciated!
Waiting for IBM experts to advise on how the lower bound is calculated for CP models.
Best regards,
Mohamed
------------------------------
Mohamed Awad
Original Message:
Sent: Fri February 25, 2022 05:36 PM
From: Paul Rubin
Subject: Question of optimality gap of CP solver
In the order asked:
- The optimality gap is a conservative estimate. There may or may not be a feasible solution better than the incumbent by that much, but there definitely is not a feasible solution better than the incumbent by more than the optimality gap (give or take a bit of rounding error if floating point numbers are involved). So if you are comfortable with the possibility that there might be a solution lurking somewhere that is better by the amount of the optimality gap, feel free to accept the incumbent and stop.
- Yes.
- Beats me. Someone from IBM will have to answer this.
- There is nothing particularly surprising here. There may be lots of solutions with similar makespans (requiring more searching to find the best) but only a few with low costs (facilitating search). The constraints involving cost may make it easier to reduce the domains of key variables than the makespan constraints do. It may be that you have an efficient formulation from the cost perspective but an inefficient formulation from the makespan perspective (i.e., reformulating using different variables and/or constraints might make it easier to minimize makespan) (but perhaps harder to minimize cost).
Paul
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Fri February 25, 2022 03:37 PM
From: Mohamed Awad
Subject: Question of optimality gap of CP solver
Dears,
I have a question regarding the optimality gap of CP solver. I am running a larger scheduling problem where I can either minimise the makespan or the cost. Whenever I run the model for minimising the makespan, the optimality gap is always very large (~75%). However, when I minimise the cost, the optimality gap becomes 0 in very short time. My question are:
- To what extent can I relay on the optimality gap as a stopping criteria?
- Can I assume that I reached the optimal solution for the case of cost minimisation as the optimality gap is zero?
- How the CP solver calculates the lower bound?
- Why the objective function can cause such large variation of the gap (makespan vs cost)?
Best regards,
Mohamed
------------------------------
Mohamed Awad
------------------------------
#DecisionOptimization