2
$\begingroup$

I have developed an IP model for a combinatorial problem. The model is faster than the other models in the literature. However, for some instances, the model reaches the optimum solution (which I know from the literature), but it takes a significant amount of time to prove it as optimal. From what I see, the Gurobi solver's lower bound value is much lower than the optimal value.

Are there any suggestions for such a case while modeling? Did I miss something while formulating it? Do I need to add additional constraints that can eliminate such a case? I have a group of constraints with M-values; could they be the reason?

$\endgroup$
2

1 Answer 1

4
$\begingroup$

As mentioned in comments, a tight value for $M$ helps.

Sometimes, redundant constraints can help the solver by giving it information that lets it generate bound-tightening cuts. As far as I know, this is very much hit-and-miss, meaning if you know a redundant constraint you can try adding it and see what happens, but it is difficult to look at a problem and immediately recognize that a particular redundant constraint will help.

Symmetry can at times cause slow convergence. Symmetry means that, for any feasible solution, there is some permutation of the indices of the variables that will produce another feasible solution with the same objective value. The reason this is problematic is that, after identifying a new incumbent solution, the solver will not be able to prune nodes that contain a permutation of the new incumbent because their bound will typically be better than the new incumbent's objective value. Solvers like Gurobi generally make some attempt at mitigation of symmetry automatically, but it may well have a setting that you can ratchet up to try harder at reducing symmetry ... assuming you model actually has a symmetry problem. If there is symmetry, chances are you can model some of it out of existence by adding constraints designed to break the symmetry.

Sometimes a reduction in model detail can help accelerate convergence. I worked on a model that assigned patients to physicians. The obvious way to model the problem was to use a binary variable for each combination of physician and patient (1 if the patient is assigned to that physician, 0 if not). We sped the model up by putting the patients in pools, where all patients in a pool would have more or less the same requirements, and changed the variables to how many patients from each pool were assigned to each physician. The model got considerably easier to solve.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.