Wednesday, June 18, 2014

Turning Bounds into Constraints in CPLEX

I had to delve into the CPLEX documentation today, and found something I had not seen before. As part of a (Java) program I'm writing, I need to use the conflict refiner to track down which upper and lower bounds on variables take a role in making a linear program infeasible. Of course, I could change the bounds to constraints (e.g., add a constraint $x\le 5$ rather than declaring $x$ as a variable with domain $[0, 5]$), but the model is more compact if the bounds are specified as bounds. The answer turns out to be tied to an interface in the Java API named IloNumVarBound. The documentation on it is not entirely self-explanatory, so I thought I'd post a small example.

Let me start by posing a small and obviously infeasible linear program:\[ \begin{array}[t]{cccc} \mathrm{minimize} & y\\ \mathrm{s.t.} & x-y & \le & 10\\ & x & \ge & 20\\ & y & \le & 5\\ & y & \ge & 0 \end{array} \]where only the first constraint is entered as a constraint (the rest being entered as bounds). Here's my Java source code (minus imports, exception handling and other cruft):

IloCplex cp = new IloCplex();
IloNumVar x = cp.numVar(20, Double.POSITIVE_INFINITY);
IloNumVar y = cp.numVar(0.0, 5.0);
cp.addMinimize(y);
IloRange c1 = cp.addLe(cp.diff(x, y), 10.0);
cp.solve();
if (cp.getStatus() == IloCplex.Status.Infeasible) {
  IloConstraint[] constraint = 
    new IloConstraint[] {c1,
                         cp.bound(x, IloNumVarBoundType.Lower),
                         cp.bound(x, IloNumVarBoundType.Upper),
                         cp.bound(y, IloNumVarBoundType.Lower),
                         cp.bound(y, IloNumVarBoundType.Upper)
    };
  double[] prefs = new double[] {1, 1, 1, 1, 1};
  if (cp.refineConflict(constraint, prefs)) {
    ConflictStatus[] status = cp.getConflict(constraint);
    for (int i = 0; i < constraint.length; i++) {
      System.out.println("Constraint " + constraint[i]
                         + " has status " + status[i]);
    }
  } else {
    System.out.println("No conflict found??");
  }
} else {
  System.out.println("Unexpected status = " + cp.getStatus());

If you are not familiar with the use of the conflict refiner, you can find it documented in the CPLEX API manuals. The refineConflict() method takes two arguments: a vector of constraints to consider in locating a conflict; and a numerical preference vector indicating which constraints should be ignored, which should automatically be considered part of any conflict, and what your priority is for including any of the remaining constraints.

The key issue here is that the first argument consists only of constraints, not bounds. The IloNumVarBound interface provides a way of "casting" a bound into something that CPLEX will accept as a constraint. In the Java API, IloCplex.bound() generates an instance of IloNumVarBound from a variable. It takes as arguments the variable and which bound (lower or upper) you want to treat as a constraint. It's important to note that you would not use bound() or IloNumVarBound to create the bound in the model; you still do that by specifying the bound as an argument to the method that creates the variable.

A couple of things in the code bear mentioning:
  • I included all four bounds in the call to the conflict refiner because I was pretending not to know which ones were involved, not because you have to include every constraint and every bound when you call the refiner.
  • In order to pass the one functional constraint to the conflict refiner, I had to assign (a pointer to) it to a variable (ct1).
Here is the output from the program:

Constraint IloRange  : -infinity <= (-1.0*[0.0..5.0] + 1.0*[20.0..infinity]) <= 10.0 has status Member
Constraint Lower bound of [20.0..infinity] has status Member
Constraint Upper bound of [20.0..infinity] has status Excluded
Constraint Lower bound of [0.0..5.0] has status Excluded
Constraint Upper bound of [0.0..5.0] has status Member

You can pretty it up by assigning names to the variables and constraints; I just didn't bother.

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.