Multiple Children – Again!

Written by: Paul Rubin

Primary Source: OR in an OB World

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:

The following two tabs change content below.
I'm an apostate mathematician, retired from a business school after 33 years of teaching mostly (but not exclusively) quantitative methods courses. My academic interests lie in operations research. I also study Tae Kwon Do a bit on the side.

Latest posts by Paul Rubin (see all)