Multiple Children - Again!

I thought I had exhausted this topic, but no such luck ...

As noted in a previous post ("When the OctoMom Solves MILPs"), CPLEX (and I believe most other integer programming solvers) are have a design limitation of at most two child nodes per parent node in the search tree. Personally, I don't consider that limitation a problem, but occasionally someone comes along wanting more children. In the aforementioned post, I described a way to work around the limitation by creating nodes that combined two or more of the intended children and then splitting those nodes. In a follow-up post ("Birthing a Litter in CPLEX"), I proved a test case (assigning students to teams so that average GPAs for all teams are comparable) and supplied some Java code. I'll repeat the key illustrations here for context.

The search tree our hypothetical user wants contains a child under the root for each choice for the number of teams to create.

What can actually be accomplished, using the workaround, looks like the following.

Note the presence of three "meta-nodes" (with team ranges marked alongside them in blue) in addition to the nodes from the first diagram.

A point was recently raised in a discussion about this on OR-Exchange: those extra meta-nodes require the solution of additional node LPs. My first reaction is that the extra pivots are not likely to be a problem, for two reasons. First, the default for CPLEX (and, again, I suspect most solvers) is to use dual simplex pivots to restore feasibility when solving the child node's LP (which differs from the parent's LP just by the cut(s) added to create the child node). Second, I suspect that some of the same pivots would occur if you were to solve the leaf node LPs directly. If a substantial portion of the pivots that solve the "6-7 teams" node would occur in both the "6 teams" node and the "7 teams" node, were those nodes spawned directly from the root, then solving the meta-node LP might actually be more efficient (by virtue of doing those pivots once rather than twice).

All that said, I got curious whether I could con (er, "induce") CPLEX into creating meta-nodes that were direct clones of their parents. The goal was a tree looking as follows, where the nodes marked with an asterisk (*) are direct clones of (identical to) their parents.

The answer, for the moment at least, is "yes". I have placed sample Java code in a Git repository open to the public for download. (There's also an issue tracker in the unlikely event that you should find a bug.) See the side panel for license information. It's based on the code from the second post mentioned above, and as such is slightly over-engineered (I did not take the time to eliminate features from the previous code that are not needed here).

The key lines, appearing in the branch callback, are the ones that create a child that is a direct clone of the parent:

// second child clones the parent with adjusted node data
info = new BranchInfo(min + 1, max);
id = makeBranch(new IloRange[0], obj, info);

The info variable holds "node data" that is attached to the clone node; variable id contains the node ID assigned by CPLEX to the clone node. Fair warning: the code relies on an "undocumented feature" (programmer oversight?) of the Java API, which means it could cease to work in some future version. The trick is to pass the makeBranch() method an empty (length 0) array of "cuts" to add. Note that passing null, rather than an empty array, results in an uncaught exception.

I have no idea whether other APIs have the same "feature".