This has come up twice recently (that I've noticed) in forums, so
it's worth writing up for future reference. In both cases the question
pertained to CPLEX, but I'm pretty sure other contemporary mixed-integer
linear program (MILP) solvers behave similarly. The question is: how
can you create more than two child nodes from a single parent node
in the search tree of a MILP?

MILP solvers typically use some version of branch-and-cut, and it's
important to distinguish between their default behavior, what they'll
let you do if you take control (typically through callbacks), and
what is completely off the table. Although branch-and-cut lets you
separate a node using any number and sort of constraints (so long
as they are linear), most solvers default to an old-fashioned branch-and-bound
behavior, in which a parent node is separated into two child nodes
by taking one integer variable $x$ (with possibly infinite bounds
$a\le x\le b$) and a current non-integer value $\hat{x}$ and rounding
down in one node ($a\le x\le\left\lfloor \hat{x}\right\rfloor $)
and up in the other ($\left\lceil \hat{x}\right\rceil \le x\le b$).
If the solver supports callbacks, however, chances are it lets you
impose your own, more general, separation of a node. CPLEX in fact
does this, allowing linear inequality cuts ($h^{\prime}x\le k$ in
one child, $h^{\prime}x\ge k+\Delta k$ in the other child), multiple
linear cuts, and mixes of linear cuts and bounds. CPLEX does have
a firm limit of at most two children per parent, however. So what
if you want to split a parent node $P$ into $n>2$ children $C_{1},\ldots,C_{n}$,
using sets of cuts/bounds $S_{1},\ldots,S_{n}$? (We'll charitably
assume that the feasible regions for nodes $P\cup S_{1},\ldots,P\cup S_{n}$,
possibly empty in some cases, are disjoint; otherwise it's not really
a valid separation.)

The answer, while perhaps not elegant, is at least simple: create
two children, $C_{1}$ and "not $C_{1}$" (which I'll designate
somewhat more formally as $\tilde{C}_{1}$). Then separate $\tilde{C}_{1}$
into $C_{2}$ and "not $C_{2}$ either" ($\tilde{C}_{2}$),
etc., ad nauseum. The nodes $C_{1},\ldots,C_{n}$ will look more like
cousins than siblings -- they won't be on the same level of the search
tree -- but that really has no practical effect.

Here's a picture of a simple problem in which variable $x\in\{1,\ldots,4\}$
and I'd like to create four children under the root node, one for
each possible value of $x$:

It's possible that the constraints to add for one of the "tilde"
children are not obvious. For instance, $\tilde{C}_{1}$ is defined
by the union $S_{2}\cup\ldots\cup S_{n}$, which might not have nice
compact representation. Not to worry: define $\tilde{C}_{1}$ as essentially
a clone of parent node $P$ by adding some innocuous constraint (for
instance, $y\ge0$, where $y$ is already defined as nonnegative)
-- unless the software lets you create a clone child by adding an
empty set of cuts (doubtful, but perhaps some program will allow that).

## No comments:

## Post a Comment

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 OR-Exchange.