Feeding known lower bounds to solvers

Question

Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all feasible 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. ...)?

Answer 1

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.

Answer 2

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.

Answer 3

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