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

**Related posts**:

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