Decision Optimization

 View Only
  • 1.  How to minimize the gap in CP solver

    Posted Tue June 30, 2020 04:33 AM
    Dears,

    I have a question regarding the gap in solution when CP solver runs. I built a large model that has thousands of constraints with the aim to minimize the make span. After running the model for long time, the gap never decreased below 85%. As I understand, the gap is calculated by the difference between the best bound and the current bound. The value of the best bound doesn't change and I assume that it was calculated by a non-constrained version of my problem. My question is how the best bound is calculated, how to close the gap in my solution and how to terminate the solution if for example the gap is 5% (or how to guarantee the optimality of the solution).

    Thanks in advance
    Mohamed

    ------------------------------
    Mohamed Awad
    ------------------------------

    #DecisionOptimization


  • 2.  RE: How to minimize the gap in CP solver

    Posted Wed July 01, 2020 05:22 AM
    Hello,
    initial lower bound is computed at the beginning of the search in quite simple way. The exact way of the computation depends whether it is a pure integer problem (no interval variables) or a scheduling problem (with interval variables). It seems that you have a scheduling model, in this case initial lower bound is computed by:
    • Simple constraint propagation on the objective expression.
    • "Destructive lower bound". CP Optimizer tries to add constraint makespan<X and if constraint propagation proves infeasibility then X is a valid lower bound.
    • Lower bound computed from LP relaxation.
    This initial lower bound could be quite dumb. CP Optimizer puts only minimal effort to improve the lower bound during the rest of the search. Most of the time it is increased only as a byproduct of the search. It typically happens near the proof of optimality.

    However in case of a large model there is usually only a small chance to get optimality proof in a reasonable time (unless the problem is quite simple). And therefore it is also quite unlikely that the lower bound increases.

    Note that large gap does not automatically mean that the solution you're getting is bad. For example, you may already have optimal solution, but the lower bound is bad. It is often the case. So I advice you to not get distracted by the gap. Until recently CP Optimizer didn't display the gap at all (as we know that lower bound could be quite bad). Sometimes even a simple lower bound could be useful, so we provide it now. But it is probably not useful in your case.

    To answer the last part of your question, you may set RelativeOptimalityTolerance parameter to stop the search when gap is low.

    Best regards, Petr

    ------------------------------
    Petr Vilím
    IBM
    ------------------------------