22
$\begingroup$

Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all optimal solutions, and your solver of choice:

  • For what theoretical and/or practical (implementation-specific?) reason(s) would you not feed this bound to your favorite solver?

  • Or, if you can't think of any such reason, do you have [more or less] justified "opinions" on how not to provide such a bound to the solver (e. g., "hard-wired" $\ge$-constraint vs. some sort of callback/"dynamic cut" vs. ...)?

$\endgroup$
  • $\begingroup$ Who the heck downvoted this and why? $\endgroup$ – Mark L. Stone Jun 12 '19 at 20:57
  • 2
    $\begingroup$ You can check for yourself by solving a problem twice, recording the optimum from the first run and impose a cutoff in the second run. Do you see a difference? $\endgroup$ – Marco Lübbecke Jun 12 '19 at 21:11
  • 2
    $\begingroup$ @fbahr Would you object to changing the last tag to "bounds" instead of "lower-bound"? Since the concept in the question can apply to either, depending on the sense of the objective function. $\endgroup$ – LarrySnyder610 Jun 12 '19 at 23:01
20
$\begingroup$

Interesting topic (the question was raised several times by my students as well).

My short answer is that adding the lower bound through a cut seems a good idea at first glance, but it creates a very large “unnatural” face where your search is trapped for a long while. Essentially you lose the objective function grip, and do not gain anything.

Let me explain. Take a MILP, and let LB be the lower bound at hand.

ASSUMPTION: LB is not tight at the integer optimum (otherwise, as already noticed, you have essentially a “feasibility problem” hence LB can indeed be very useful to stop as soon as a heuristic found a solution with cost equal to LB).

I ask you: what could be a positive effect of adding the cut

$$(1)\quad c x \ge LB$$

to the original MILP model?

Take a generic node of the enumeration tree, where some cuts have been possibly added and some variables have been fixed. Solve the corresponding LP relaxation without (1) and consider its optimal value $z$ (say).

If $z > LB$, then (1) is slack and hence useless. If $z \le LB$ the node lower bound would apparently improve (i.e. increase) going from $z$ (without (1)) to LB (using (1)) but this is again useless as you will never prune this node because of lower bound due to the ASSUMPTION above.

In other words, (1) will never help pruning a node, which would be the main reason to use it.

Instead, the negative effects of using (1) include (as already discussed):

A) huge dual degeneracy $\rightarrow$ you zig-zag between tons of LP solutions with the same cost (=LB)

B) blindness wrt the objective function at the root node and for many many other nodes $\rightarrow$ you are wasting 50 years of clever ideas such as pseudo costs, best-bound search, etc.

All in all, I would not expect any improvement when adding cut (1) to the MILP formulation—barring performance variability of course.

$\endgroup$
  • 4
    $\begingroup$ This reminds me of some folklore around problems when a cut is (near) parallel to the objective. In SCIP, the user can set a lower bound directly, without adding the constraint (1) to the LP relaxation. $\endgroup$ – Robert Schwarz Jun 14 '19 at 7:34
10
$\begingroup$

Branch-and-bound solvers often use node lower bounds to select the next node to process, e.g. in a best-first search. An external lower bound can lead to a different search order, and thus you may have to explore a different number nodes until finding an optimal solution, and proving its optimality.

For concreteness imagine a simple depth $4$ binary search tree over $x\in\{0,1\}^4$ and let the unique optimal solution be $x=(0\:0\:0\:0)^t$. If you set the lower bound equal to the optimal solution value, the search stops when an optimal solution has been found. However, the lower bound does not guide the search, and as a function of the tie-breaker you may explore between $4$ nodes ($0$-first tie-breaker) to $31$ nodes ($1$-first tie-breaker) until that happens.

$\endgroup$
  • 2
    $\begingroup$ I completely agree that this happens sometimes, but at the same time I would not refrain from supplying a lower bound on the basis of this. I don't think there is any way to predict this would occur, and my subjective probability assessment (a.k.a. "gut feeling") is that the chances that the bound speeds pruning outweigh the chances that it causes the solver to take the long way around. $\endgroup$ – prubin Jun 13 '19 at 14:56
9
$\begingroup$

To add to Marcus's answer: you can use a callback to prune parts of the tree when your external bound proves that this part of the tree does not contain an optimal solution, without affecting the branching order.

I wouldn't explicitly impose an objective constraint/explicitly feed the bound to the solver, because if your relaxations at each node can't reproduce this bound then it inhibits accurate pseudocost estimation when branching.

There's a blogpost which touches on some other issues regarding this here: https://orinanobworld.blogspot.com/2013/05/a-priori-objective-bound.html

$\endgroup$
  • $\begingroup$ I guess this answer assumes that you can compute a better external lower bound at each branching node, in which case I agree that using a callback is useful. $\endgroup$ – Matteo Fischetti Jun 14 '19 at 5:46
  • $\begingroup$ It could also be useful if you can only compute the bound at the root node and/or computing the bound at every node is too expensive. For a concrete example take BQP: an SDP relaxation is fairly cheap to compute once (but too expensive to compute at each node), but the SDP bound usually outperforms branch and bound when say $n \geq 200$. In this case a reasonable approach might be to use a callback to prune parts of the tree which the SDP bound proves are suboptimal, but the branch and bound tree itself doesn't "know" are suboptimal. $\endgroup$ – Ryan Cory-Wright Jun 14 '19 at 16:27
  • 1
    $\begingroup$ Still not clear to me how to use the root-node external lower bound to purge a subtree without updating/recomputing it along the tree. In your example, suppose the root-node external lower bound computed by SDP is LB=1000 and the optimal solution value is 1001 (i.e. the lower bound is not tight). Which nodes will you prune that would not be pruned without knowing LB? $\endgroup$ – Matteo Fischetti Jun 14 '19 at 19:30
  • $\begingroup$ I see what you mean. Yes, you are right. $\endgroup$ – Ryan Cory-Wright Jun 15 '19 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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