Solution Pool: "All" Is Not All

I was struck by an idle thought (which left a wicked bruise) regarding yesterday's post about finding "all" MIP solutions using the CPLEX solution pool. Branch-and-bound and branch-and-cut algorithms generally prune a node for one of three reasons:

• the LP relaxation is infeasible, in which case no amount of further torture will cause the node to confess to a solution;
• the objective value of the LP relaxation is worse (or at least no better) than that of the current incumbent solution, in which case further division of the node will never yield a solution better than the incumbent; or
• "the" optimal solution to the LP relaxation is integer-feasible, in which case it is unclear how to further partition the node (and whether to bother).

Note the quotation marks around "the" in the third bullet. When searching for all optimal solutions, or even all feasible solutions, the first rule (prune an infeasible node) still makes sense. The second rule needs to be tempered, as there may be solutions in other parts of the tree that are as good as the incumbent even if they are not better (and, in the case of finding all feasible solutions, you do not care that solutions in other branches of the tree have worse objective values). That brings us to the third rule.

A node problem whose LP relaxation has an integer-feasible optimum may in fact have multiple integer-feasible optima, and certainly may have multiple integer-feasible solutions (which is important if you are looking for all feasible solutions, not just all optima). The usual branching rule (pick a variable that should be integer but is not and separate into two nodes by rounding it up or down) is of no avail if the solution is integer-feasible. One could concoct an arbitrary rule for further partitioning, but it would be outside the scope of the normal branch-and-bound algorithm.

[Edit: Ed Klotz pointed out an important distinction to me. When the node relaxation solution is integer-feasible, you need to look at the sequence of branching decisions leading to the node. If those decisions fixed all the integer variables to specific values, then the node LP solution is the only integer-feasible solution at that node, and there's nothing left to do but prune it. If the branching decisions leave open the possibility that some of the integer variables might take on different values consistent with all the added cuts that got you there, then further processing is required, and CPLEX will indeed do this.]

So the idle thought was "what does the CPLEX populate function do in the third case?", and the answer seems to be "prune the node". [Edit: I think I was wrong here. See the update below.] Consider the following trivial test problem:\[ \begin{array}{lrcl} \textrm{maximize} & x_{1}\\ \textrm{s.t.} & \sum_{i=1}^{d}x_{i} & \ge & \frac{d}{3}\\ & x & \in & \mathbb{B}^{d} \end{array} \] where $\mathbb{B}=\{0,1\}$. There is no significance to the choice of 3 as the denominator of the right-side of the constraint, and in fact the constraint is there primarily to make sure that CPLEX extracts and solves for all variables. (Without it, CPLEX treats the problem as having a single variable $x_1$.) The problem clearly has multiple optimal solutions, formed by setting $x_1=1$ and $x_j=1$ for at least $d/3-1$ other values of $j$.

I ran the populate method against this problem, using the same parameter choices mentioned in yesterday's post (and in particular asking for up to 100 optimal solutions). For various (small) choices of $d$, CPLEX produced only a single solution in the pool ($x_j=1$ for all $j$). Turning off the presolver did not affect this, nor did monkeying with the root and node LP algorithms (nor any other parameter change I tried). I'm not sure why that particular solution was the winner. As to why only one solution was returned, my guess is that the first step branches on (or otherwise fixes) $x_1$, rules out the node where $x_1=0$ based on bound, finds an integer-feasible optimum in the node where $x_1=1$ and then fails to partition that node any further. (This is strictly conjecture, since I am not privy to the inner workings of populate.)

My conclusion is that if you really need all the optima for a MIP, you will need to do something clever (either with callbacks or looping through a sequence of problems) and not rely on the CPLEX solution pool.

Update: My conjecture about CPLEX branching once and then not partitioning the winning node was wrong. I noticed that neither the "phase I" nor "phase II" output contained a node log, which would suggest that CPLEX obtained the one solution it found by presolving, even though I had presolving turned off. So I modified the objective function to $x_1 - \epsilon \sum_{j\gt 1}x_j$, which means it is no longer harmless to force all $x_j$ to 1 for $j\gt 1$. With the new objective, CPLEX generated a node log and found all optimal solutions (as well as some suboptimal ones). Similarly, with just one of the variables penalized, say an objective function $x_1 - \epsilon x_2$, CPLEX branched and found all optima.

So failing to partition a node with an integer solution is not the problem. This may just be a bug.

Update #2: It is a bug. Here's an official response from the IBM/ILOG support team.

This is a bug that we will fix. Thomas Opfer's conjecture from Jan 28 is on target:

> Might it be that they iterate trivial examples because it is faster than starting the complete CPLEX-overhead?

Specifically, before CPLEX's main presolve gets started, CPLEX computes a trivial objective upper bound on this maximization problem by removing all the constraints and setting the variables to their appropriate bound based on the objective value. In this case that established an upper bound of 1. CPLEX also applies some very simple heuristics, which find a feasible solution with an objective of 1. So, the lower and upper bound for the MIP already match, which means an optimal solution has already been found. So, no tree, which the solution pool algorithm requires, is available, and CPLEX essentially stops with the one optimal solution in the pool. This is not correct behavior when the solution pool intensity has been set to 4 to tell CPLEX to enumerate all solutions. CPLEX properly handles a similar case when the full presolve solves the whole model and no tree is available to the solution pool, so we need to do likewise in this situation.

We will fix this in either the next fixpack or feature release, whichever comes first. Sorry for the inconvenience, although the good news is that the bug will only bite on very simple models that CPLEX can solve to optimality with some very minimal presolving effort. In the short term, you can work around this on such models by setting the heuristic frequency parameter to -1 to disable heuristics.