In a
previous post, I discussed (at a conceptual level) how to work around
CPLEX's limitation of at most two children for any node in the search tree of a mixed-integer program. Following up on a
question on one of their support forums, I'll add some implementation details and an example (using the Java API).
The example that I will use is a team assignment problem. Given $N$ students (indexed $1\ldots N$), with student $i$ having a grade point average (GPA) equal to $g_i$ (on a scale from 0.0 to 4.0), form teams containing between $S_{min}$ and $S_{max}\ge S_{min}$ students on each team, so that the mean GPAs of the teams are as close as possible (minimal spread).
The use of mean GPA, combined with a variable team size (unless $S_{max}=S_{min}$), actually makes this a nonlinear model. I'll finesse that by binary variables, in a Type 1
Special Ordered Set (SOS1), to control the size of each team.
Mathematical Model
Constraint (1) ensures that each student is assigned to exactly one team. Constraint (2) simultaneously defines the $s$ variables (team sizes) and ensures that every team is either empty or has a size between $S_{min}$ and $S_{max}$. Constraint (3) simultaneously makes the $s$ variables for each team a SOS1 and ensures that the size is nonzero if and only if the team is used ($y_j=1$). Constraint (4) eliminates some symmetry in the model by "packing" teams (so that, if fewer than $T_{max}$ teams are used, the ones used are those with lowest indices). Constraint (5) computes the sum of the GPAs of students assigned to each team.
Finally, constraints (6) and (7) define the smallest ($G_{min}$) and largest ($G_{max}$) team GPAs in a linear manner. If $s_{jk}=1$, then team $j$ has size $k$, and (6) and (7) resolve to \[kG_{min}\le G_j \le kG_{max},\] or equivalently \[G_{min}\le G_j/k \le G_{max},\] where $G_j/k$ is the mean GPA of team $j$. If $s_{jk}=0$, (6) and (7) are both nonbinding; given the 0-4 grading scale, the right side of (6) becomes $k G_{max}+4S_{max}\ge 4S_{max}$ (the highest possible sum of GPAs on any valid team), while the right side of (7) becomes $k\left(G_{min} - 4\right)\le 0$.
Branching Strategy
To illustrate how to simulate more than two children at a node, I will adopt the following branching strategy. At the root node, I will branch on the number of teams being utilized (which must be between $T_{min}$ and $T_{max}$ inclusive), creating one child for each possible team count. At any other nodes, I will let CPLEX branch as it pleases. Note that I am not advocating this strategy as an effective method for problems of this nature; it is strictly a coding example.
Of course, I cannot literally create $T_{max}-T_{min}+1$ children at the root node, since CPLEX limits a node to at most children. So my branch
callback will attach to each node a data object containing the fewest ($a$) and most ($b$) teams allowed at that node and its descendants. When I branch on that node, I will bisect $\{a,\dots, b\}$ into $\{a,\dots,m\}$ and $\{m+1,\dots,b\}$, where $\m=\left\lfloor (a+b)/2 \right\rfloor$. If $a=m$ or $b=m+1$, I will create a "normal" child corresponding to that (with no attached data). If $a<m$ or $m+1 < b$, the corresponding child (which I will refer to as a "composite" node) will have the new range ($[a,m]$ or $[m+1,b]$) attached as node data, and will receive the same special treatment when the time comes to branch on it.
Suppose that $T_{min}=3$ and $T_{max}=7$. This is the top of the search tree we want:
The root node would be "composite", whereas all the children would be "normal". This, on the other hand, is the top of the tree we will generate (given CPLEX's two-child limit):
Here there are three "composite" nodes in addition to the root node; the five leaf nodes are "normal".
Java Code
Shown next is the main program. (My usual disclaimer applies: I'm an amateur coder, and I make no claims that this is optimized for anything.) The entire program can be
downloaded here (Java source code, ~5 KB). [Note: This link was updated on 10/02/2014 to point to a new repository.]
There is nothing particularly special about the main program. The GPA is generated randomly; model parameters are set at the top of the
main method. I set the absolute tolerance (EpAGap parameter) to 0.01; there is no point in splitting hairs when working with GPA data.
The information object attached to composite nodes is a simple container class that provides just the minimum and maximum number of teams at that node:
Finally, I present below the branch callback implementation. It contains a bunch of extra print statements just to illustrate how it is behaving. The callback is called at every node. At a "normal" node, where the number of teams is already fixed, it returns without doing anything (allowing CPLEX to branch as usual). At a "composite" node, it produces two children as described above (other than in the pathological case of $T_{min}=T_{max}$, in which case it produces a single "normal" child).
The callback detects a "composite" node by the presence of an information object attached (by an earlier call to the callback) to that node. The one exception is the root node, which we know is composite but to which we cannot attach an information object. I handle that by setting a flag in the callback (at the time of construction) saying that the next node encountered will be the root. The first time branching occurs (which must be at the root), the callback recognizes it as a "composite" node and clears the flag.
/*
* Custom branch callback creating 3+ children.
*
* When branching at the root node, this will create one child node for
* each possible count on the number of teams. At other nodes, it will
* let CPLEX branch as usual.
*/
package multichild;
import ilog.concert.IloException;
import ilog.concert.IloNumVar;
import ilog.cplex.IloCplex;
import java.util.ArrayList;
/**
* @author Paul A. Rubin (http://about.me/paul.a.rubin)
*/
public class Brancher extends IloCplex.BranchCallback {
private int minTeams; // minimum number of teams to create
private int maxTeams; // maximum number of teams to create
private IloNumVar[] teamVars; // boolean variables for team use
private boolean atRoot; // are we at the root node?
private ArrayList<Double> bounds; // bounds for variables when branching
private ArrayList<IloCplex.BranchDirection> dirs; // branch directions
private ArrayList<IloNumVar> vars; // variables involved in branching
private double[] aBds; // bounds as doubles
private IloCplex.BranchDirection[] aDirs; // directions as array
private IloNumVar[] aVars; // variables as array
/**
* Constructor.
* @param minTeams minimum number of teams to create
* @param maxTeams maximum number of teams to create
* @param v boolean variables for team use
* @throws an exception if the variable array has the wrong dimension
*/
public Brancher(int minTeams, int maxTeams, IloNumVar[] v) throws Exception {
super();
this.minTeams = minTeams;
this.maxTeams = maxTeams;
this.teamVars = v;
// make sure the variable vector has the correct dimension
if (v.length != maxTeams) {
throw new Exception("Variable array dimension " + v.length
+ " does not match maxTeams = " + maxTeams);
}
this.atRoot = true;
}
/**
* The actual callback operation.
* @throws IloException if CPLEX gets miffed
*/
@Override
protected void main() throws IloException {
BranchInfo info = null;
Object raw;
String msg = ">>> At node " + getNodeId() + ", ";
IloCplex.NodeId id;
// check whether we are at the root node (which will have no attachment)
if (atRoot) {
raw = new BranchInfo(minTeams, maxTeams); // create an attachment
atRoot = false; // clear the root flag
}
else {
raw = getNodeData(); // get the current node's attachment, if any
}
if (raw == null) {
// no data object -- let CPLEX handle branching
return;
}
else if (raw instanceof BranchInfo) {
// convert the object to an instance of BranchInfo
info = (BranchInfo) raw;
}
else {
// unknown node data type -- should never happen
System.err.println("Encountered unknown node data type!");
abort();
}
// the presence of node data means we are branching on team count
// if the range of team sizes at this node is one or two, just create
// normal children; otherwise, bisect the range of counts and create
// two "special" children
int min = info.getMinTeams();
int max = info.getMaxTeams();
msg += "team range is " + min + " to " + max;
double obj = getObjValue(); // current node bound
switch (max - min) {
case 0: // create a single child with exactly this many teams
// this case should only occur (at the outset) if minTeams = maxTeams
cut(min, max);
id = makeBranch(aVars, aBds, aDirs, obj); // attach no data
msg += " -- adding one normal child ("
+ id + ") with exactly " + min + " teams";
System.out.println(msg);
return;
case 1: // create two normal children
// first child contains exactly min teams, no attached data
cut(min, min);
id = makeBranch(aVars, aBds, aDirs, obj); // attach no data
msg += " -- adding two normal children (" + id + " using exactly "
+ min + " teams and ";
// second child contains exactly max = min + 1 teams, no attachment
cut(max, max);
id = makeBranch(aVars, aBds, aDirs, obj); // attach no data
msg += id + " using exactly " + max + " teams)";
System.out.println(msg);
return;
case 2: // create one normal child and one composite child
// first child uses min to min+1 teams
cut(min, min + 1);
// attach node info to this child
info = new BranchInfo(min, min + 1);
id = makeBranch(aVars, aBds, aDirs, obj, info);
msg += " -- adding one composite child (" + id + ") with range "
+ min + " to " + (min + 1);
// second child uses exactly max = min + 2 teams, no attached data
cut(max, max);
id = makeBranch(aVars, aBds, aDirs, obj);
msg += " and one normal child (" + id + ") using exactly "
+ max + " teams";
System.out.println(msg);
return;
default: // max > min + 2: create two composite children
int mid = (max + min)/2; // midpoint of size range (rounding down)
// first child uses min to mid team count
cut(min, mid);
info = new BranchInfo(min, mid);
id = makeBranch(aVars, aBds, aDirs, obj, info);
msg += " -- adding two composite children (" + id
+ " with range " + min + " to " + mid;
// second child uses mid + 1 to max team count
cut(mid + 1, max);
info = new BranchInfo(mid + 1, max);
id = makeBranch(aVars, aBds, aDirs, obj, info);
msg += " and " + id + " with range " + (mid + 1) + " to " + max + ")";
System.out.println(msg);
return;
}
}
/**
* Sets up the arguments for a cut that ensures somewhere between min and
* max teams are used.
* @param min minimum number of teams to use
* @param max maximum number of teams to use
*/
private void cut(int min, int max) {
this.bounds = new ArrayList<Double>();
this.dirs = new ArrayList<IloCplex.BranchDirection>();
this.vars = new ArrayList<IloNumVar>();
for (int j = 0; j < maxTeams; j++) {
if (j < min) { // force the first min variables to be 1
vars.add(teamVars[j]);
bounds.add(1.0);
dirs.add(IloCplex.BranchDirection.Up);
}
else if (j >= max) { // force variables above max to be 0
vars.add(teamVars[j]);
bounds.add(0.0);
dirs.add(IloCplex.BranchDirection.Down);
}
}
// convert the lists to arrays
aVars = vars.toArray(new IloNumVar[0]);
aDirs = dirs.toArray(new IloCplex.BranchDirection[0]);
// unavoidable PITA -- bounds must be converted from Double[] to double[]
// with a loop
Double[] temp = bounds.toArray(new Double[0]);
aBds = new double[temp.length];
for (int i = 0; i < temp.length; i++) {
aBds[i] = temp[i];
}
}
}
Related post: "
Multiple Children - Again!" (updated code, changing the composite nodes to clones of their parents)
