Friday, May 31, 2013

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).

6 comments:

  1. A few other things effect the solution path :

    1) Reduced cost fixing is improved with a user provided cutoff value, potentially making the node problem smaller and cutting off "redundant" branches

    2) Obj cutoff can be used in cuts and node presolve

    3) Cutting down the tree size and allowing the dual simplex to stop prematurely in nodes exceeding the bound.

    ReplyDelete
    Replies
    1. Bo: Thanks for the additions. Given all this, I guess the tripled run time the questioner reported when he added the bound is further proof that, with MIPs, doing "good" things can accidentally shift you from a more productive search path to a less productive path. Maybe solvers should come with totems for good luck. :-)

      Delete
  2. Hi Paul,

    Nice post. In my experience the primary "culprit" for this sort of
    node increase is that the artificial upper bound negatively impacts
    pseudocost estimation, so very poor branching choices are made.
    (This is assuming that one imposes the upper bound with a constraint: s <= \bar{s})



    ReplyDelete
    Replies
    1. Jeff,

      Thanks for both the comment and the compliment. The person that originally posed the question to me used $\bar{s}$ as an upper bound on $s$, rather than adding it as a constraint. I'll confess to being a bit undereducated on the estimation of pseudocosts, but I'm guessing that the reduced cost of $s$ is used in the calculation the same way that the dual variable would be if the bound were an explicit constraint (?).

      Delete
  3. Hi Paul, nice post.

    For some reason my best bound is extremely large, and even though I know that my optimal solution's max is 50, the bestbound is around 5000, making the optimality gap to be around 99%. So the solver never stops, as the number of active nodes gets bigger and bigger. In this case, how would you handle the fact that I know that my solution should be under 50?

    Thanks a lot.

    ReplyDelete
    Replies
    1. This depends on the solver you are using. As described in the post, with CPLEX (and perhaps some other solvers) you can use a callback to stop the search if it finds a solution that you know is optimal. (I'm assuming here that you somehow know that 50 is the optimal objective value, as opposed to knowing that it will be no more than 50.)

      Another possibility is that your solver may have a parameter (UpperObjStop in CPLEX for max problems) that tells it to stop as soon as it gets a solution with objective value at or above some threshold. If you know your optimal objective value will be at most 50 (but possibly less), you could try setting a cutoff of 49, or 49.5, or whatever you think is reasonable.

      Neither of those fixes the best bound and gap. The only ways I know to reduce the best bound are to come up with a tighter formulation (always desirable, but easier said than done) or tell the solver to use best bound search (always selecting the node with the highest bound). The latter is definitely *not* guaranteed to help, and it might actually hinder progress on the gap. The gap depends on both the upper bound and the lower bound (best known solution), and forcing the solver to concentrate on the upper bound may result in it taking longer to improve the lower bound.

      Tightening the formulation is your best bet, *if* you can do it.

      Delete

Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.