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