A Priori Objective Bound

I was asked a question about mixed integer programs (MIPs) that I'm pretty sure I've seen on forums before, so I'll summarize my answer here. The question was in the context of the CPLEX solver, but the answer applies more generally.

Consider a MIP model of the form \[ \begin{array}{lrclr} \mathrm{maximize} & s\\ \mathrm{s.t.} & Ax+s & \le & b\\ & s & \ge & 0\\ & x & \in & X \end{array} \]where $X$ is some domain and $x$ may be a mix of integer and continuous variables. The questioner knows a priori that $s\le\bar{s}$ for some constant $\bar{s}$. When he adds $\bar{s}$ as an upper bound for $s$, though, his solution time roughly triples. So (a) why does that happen and (b) how can knowledge of $\bar{s}$ be exploited?

Answering the second question first, the main virtue of knowing $\bar{s}$ is that we can stop the solver as soon as it finds a solution with $s = \bar{s}$. Of course, this is only helpful if the bound is tight, i.e., if a feasible solution does exist with $s = \bar{s}$. If so, I think the best way to accomplish the desired end is to attach a callback that monitors incumbents and, when it sees one with $s = \bar{s}$, tells the solver to terminate the search.

Solvers (including CPLEX) typically incorporate a relative convergence criterion, which stops the solver if an incumbent $(x, s)$ is found with\[\frac{\hat{s}-s}{\hat{s}}\le\delta,\]where $\hat{s}$ is the current best bound and $\delta$ is a parameter. Asserting the known a priori bound, this effectively becomes\[\frac{\min(\hat{s},\bar{s})-s}{\min(\hat{s},\bar{s})}\le\delta\]with the left side of the new inequality less than or equal to the left side of the previous inequality (left to the reader as an exercise). Thus the relative convergence termination criterion might be triggered sooner (a good thing), provided that the bound $\bar{s}$ could be communicated to the solver in a benign way.

There are at least two more effects, though, that are harder to predict. Suppose that, in the absence of $\bar{s}$, the solver at some juncture is staring at a number of live nodes with bounds $s_1,s_2,\dots$ greater than $\bar{s}$ and not all identical (which is likely to be the case). When it comes time to leave whatever branch of the tree it is currently exploring, the solver chooses the node with the best bound (the largest among $\{s_1, s_2,\dots\}$). Now suppose that the solver has been informed, in some way, of the upper bound $\bar{s}$. The bounds of all those live nodes are truncated to $\{\bar{s},\bar{s},\dots\}$, meaning that they are all tied for best. The solver will select one, not necessarily the same one it would have selected without $\bar{s}$, and begin exploring it. Thus knowledge of the bound changes the order in which the solution tree is explored, and we have no way of knowing whether this moves the solver from a less productive area of the tree to a more productive area or vice versa.

CPLEX (and I assume other solvers) also employ a test to decide when to backtrack (shift exploration to nodes higher in the tree without pruning the current node). Let $s_{lp}$ denote the bound provided by the linear relaxation of the current node, let $s_{inc}$ denote the value of the current incumbent solution, and as before let $\hat{s}$ be the best bound (the largest linear relaxation bound of any live node). Backtracking occurs when$$\hat{s}-s_{lp}\ge \alpha(\hat{s}-s_{inc})$$with $\alpha\in [0,1]$ a parameter. Smaller values of $\alpha$ promote backtracking ($\alpha=0$, if allowed, would be pure best-first search), while larger values of $\alpha$ inhibit backtracking ($\alpha=1$, if allowed, would be pure depth-first search). The backtracking inequality can be rewritten as$$(1-\alpha)\hat{s}\ge s_{lp}-\alpha s_{inc}.$$Knowing $\bar{s}$ would effectively replace $\hat{s}$ with $\min(\hat{s},\bar{s})$, making the inequality harder to satisfy and thus making backtracking less likely to occur (pushing the solver closer to depth-first search). Again, this changes the way the solution tree is explored, in a way whose impact is difficult to predict.

The questioner said that his solution time roughly tripled when he added $\bar{s}$ as an upper bound. As far as I can tell, that was just bad luck; the solution time might decrease in other cases (but also might increase more). Personally, the only use I would make of $\bar{s}$ would be in an incumbent callback to terminate the search as soon as $s=\bar{s}$ occurred -- and I would only do that if I thought that $\bar{s}$ was really the optimal value (not just a tight bound).