3
$\begingroup$

Here is an extract from the BnB solution process of my problem. The solver determines a value of 2627.452494 as being the best bound of the optimal solution. The value for the best bound remains the same for the next 80000 nodes, then it decreases very slowly (in steps of ca. 2). The optimal solution is known to be 1958.275.

Is there anything I can do to help the solver calculate faster a better best bound?

If this behaviour is an indication of symmetry at the value 2675.564892 how could I possibly break it?

Here, the solver is XPRESS.

Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
   1   319.994373  2675.564892      4      2      1  736.13%    1130    168
   2   319.994373  2627.452537      4      1      2  721.09%     962    171
   3   319.994373  2627.452494      4      2      3  721.09%     716    173
   4   319.994373  2627.452163      4      3      4  721.09%     725    174
   5   319.994373  2627.451885      4      4      5  721.09%     725    174
   6   319.994373  2627.451885      4      5      6  721.09%     724    175
   7   319.994373  2627.451885      4      5      7  721.09%     724    175
   8   319.994373  2627.451885      4      5      7  721.09%     722    176
   9   319.994373  2627.451885      4      5      8  721.09%     722    176
  10   319.994373  2627.451885      4      5      8  721.09%     713    176
  20   319.994373  2627.451885      4      5     17  721.09%     740    192
  30   319.994373  2627.451885      4     13     10  721.09%     739    199
  40   319.994373  2627.451885      4     19     12  721.09%     777    211
  50   319.994373  2627.451676      4     23      9  721.09%     659    218
  60   319.994373  2627.451676      4     23     17  721.09%     680    223
  70   319.994373  2627.451676      4     23     24  721.09%     744    234
  80   319.994373  2627.451676      4     23     32  721.09%     648    244
  90   319.994373  2627.451642      4     44     13  721.09%     814    249
 100   319.994373  2627.451642      4     44     22  721.09%     692    256
$\endgroup$

3 Answers 3

2
$\begingroup$

You could try setting heursearch to e.g. every 1000 nodes or heurstrategy to 1 (only basic heuristics). Those options should free up a lot of computing time to be used on improving the bound. You could also set mipabscutoff to your optimal objective value.

Other things you could do is increase the number of threads, and increasing the integrality and/or constraint violation tolerances (assuming you can live with that).

However, it's very hard to outsmart a commercial solver in general - the solution typically would be to reformulate your model into something that's easier for the solver to handle.

Regarding symmetry, it's hard to tell without seeing your math, but a classic way if e.g. $x$ and $y$ are symmetrical is to add a constraint $x \geq y$ or vice versa.

$\endgroup$
1
  • $\begingroup$ Hi, Nikos. I applied your proposals but they didn't help. The behaviour of xpress is the same. I changed the solver to cplex using the option mipemphasis = moving the best bound, but I didn't get any better results; cplex gets stacked at the same point. Anyway, thank you very much for your comment. I am sure it will be valuable somewhere else. $\endgroup$
    – Clement
    Commented Jan 31, 2022 at 22:22
2
$\begingroup$

In a MIP that we are currently working on, one approach that was helpful was the relaxation of some constraints: This might seem counterintuitive at first, because it would result in weaker best bounds. However for this "relaxed model" many of the original decision variables could be dropped, resulting in a much smaller MIP. The B&B could now process the nodes much faster and made faster progress on the best bound. The best bound for the relaxed model then also presents a best bound for the more constrained original model. Ideally, this new best bound is then lower (in your case) than the best bound that you currently determine.

Whether this approach is applicable to your problem or not, I do not know, but maybe it is worth investigating.

$\endgroup$
1
$\begingroup$

Sometimes a recalcitrant best bound is a sign of a loose formulation. Sometimes it might have to do with numerical issues in the model. Symmetry could be a reason. Sometimes, I think, it's just karma. (If you are able to fix that, please post the method here.)

If your model is a "big M" type model, you might look for ways to shrink your $M$ values, or possibly investigate an alternative approach. If you can identify inherent symmetry in the model, you might be able to add symmetry-breaking constraints (which might or might not pay for themselves). Possibly there is an entirely different and tighter formulation for your problem.

Unfortunately, there is no general fix (independent of the model details) for this. If there were, the commercial solvers would have it by now.

$\endgroup$
1
  • $\begingroup$ "If you are able to fix that, please post the method here." Excellent joke, all the better because I was not expecting it. $\endgroup$ Commented Jan 31, 2022 at 17:36

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.