Tuesday, August 3, 2010

Iterating over a CPLEX Model

Periodically a question arises about how to parse an LP (or QP or MIP) in CPLEX after it has been constructed. CPLEX provides iterators in at least the C++ and Java APIs, and probably in the other APIs as well. In C++ the iterators are classes; in Java they implement the standard Java Iterator interface. I'll give a small Java example here (using CPLEX 12; there may be some differences with earlier versions).

To illustrate the process, I'll create a CPLEX model for the following linear program:\begin{eqnarray*}\textrm{maximize} & x+2y+3z\\\textrm{s.t.} & x+y+z & \le 5\\ & y+2z & \le 3\\ & x-z & =0\\ & x,y,z & \ge 0.\end{eqnarray*} Ignoring, as usual, any need to deal with exceptions, here is the code to create the model:

IloNumVar[] vars = new IloNumVar[3];
vars[0] = cplex.numVar(0, Double.MAX_VALUE, "x");
vars[1] = cplex.numVar(0, Double.MAX_VALUE, "y");
vars[2] = cplex.numVar(0, Double.MAX_VALUE, "z");
cplex.addMaximize(
  cplex.scalProd(
    new double[] {1., 2., 3.}, vars), "Obj");
// first constraint: x + y + z <= 5
cplex.addLe(cplex.sum(vars), 5., "Con1");
// second constraint: y + 2z <= 3
cplex.addLe(
  cplex.scalProd(
    new double[] {0., 1., 2.}, vars), 3., "Con2");
// third constraint: x = z
cplex.addEq(vars[0], vars[2], "Con3");

There are several choices for how I iterate over the model.  I'll focus specifically on constraints by using a rangeIterator. (With a more general iterator, I might need to rely on instanceOf comparisons to interpret what the iterator was giving me.) Here is the rest of the code:

Iterator it = cplex.rangeIterator();
while (it.hasNext()) {
  IloRange r = (IloRange) it.next();
  System.out.println("Constraint: " + r.getName());
  IloLinearNumExprIterator it2 =
    ((IloLinearNumExpr) r.getExpr()).linearIterator();
  while (it2.hasNext()) {
    System.out.println("\tVariable "
                       + it2.nextNumVar().getName()
                       + " has coefficient "
                       + it2.getValue());
  }
  // get range bounds, checking for +/- infinity
  // (allowing for some rounding)
  String lb = (r.getLB() <= Double.MIN_VALUE + 1) ?
              "-infinity" : Double.toString(r.getLB());
  String ub = (r.getUB() >= Double.MAX_VALUE - 1) ?
              "+infinity" : Double.toString(r.getUB());
  System.out.println("\t" + lb + " <= LHS <= " + ub);

The output is as follows:
Constraint: Con1
        Variable x has coefficient 1.0
        Variable y has coefficient 1.0
        Variable z has coefficient 1.0
        -infinity <= LHS <= 5.0
Constraint: Con2
        Variable y has coefficient 1.0
        Variable z has coefficient 2.0
        -infinity <= LHS <= 3.0
Constraint: Con3
        Variable x has coefficient 1.0
        Variable z has coefficient -1.0
        -infinity <= LHS <= 0.0
The outer iterator it (and instance of rangeIterator) iterates over all ranges (constraints) in the model, but its next() method returns the generic type Object, which needs to be cast to IloRange. The inner iterator it2 iterates over the expression portion of a constraint, and returns a variable (via nextNumVar()) and its coefficient (via getValue()) at each step.  The iterator exploits any sparsity in the model: only terms with non-zero coefficients are returned.

Suppose that, for some reason, I need to be able to associate the coefficients with their corresponding column indices in the original constraint matrix. I'll add a bit of code near the top to map each variable to its column index. (Add the following after the variable declarations and immediately before the declaration of the objective function.)

HashMap<IloNumVar, Integer> map =
 new HashMap<IloNumVar, Integer>();
for (int i = 0; i < 3; i++) {
  map.put(vars[i], i);
}

I replace the contents of the inner while loop with the following:

    IloNumVar v = it2.nextNumVar();
    System.out.println("\tVariable " + v.getName()
                       + " (column " + map.get(v) + ")"
                       + " has coefficient "
                       + it2.getValue());
 
The relevant portion of the output now reads as follows:
Constraint: Con1
        Variable x (column 0) has coefficient 1.0
        Variable y (column 1) has coefficient 1.0
        Variable z (column 2) has coefficient 1.0
        -infinity <= LHS <= 5.0
Constraint: Con2
        Variable y (column 1) has coefficient 1.0
        Variable z (column 2) has coefficient 2.0
        -infinity <= LHS <= 3.0
Constraint: Con3
        Variable x (column 0) has coefficient 1.0
        Variable z (column 2) has coefficient -1.0
        -infinity <= LHS <= 0.0
Note that I have to save the value of nextNumVar() in a temporary variable (v) because I need it in two places, and if I called it twice it would advance the iterator too often.

15 comments:

  1. To get a list of all variables use the following command.
    (Note that the command assumes that you model only consists of one LPMatrix.)

    IloNumVar[] vars = ((IloLPMatrix)cp.LPMatrixIterator().next()).getNumVars();

    ReplyDelete
  2. Thanks. That's a slick way to do it for a model built from a matrix, and is easily extended to a model with more than one matrix (by looping while the iterator's hasNext() method returns true). Unfortunately, if you build the model from individual variables and constraints (as I did above), rather than using matrices, then the matrix iterator is a null pointer, and the line above will generate a null pointer exception.

    ReplyDelete
  3. The iterator code was useful! Thanks.

    ReplyDelete
  4. Paul, I have a question. How best do I add my cuts to cplex C++ to actually see its effect? The problem is it seems cplex recognizes the cuts (model.add) but my solution time does not change. Thanks.

    ReplyDelete
    Replies
    1. LP or MIP? Are you calling IloCplex::solve() each time you add a cut?

      Two things immediately come to mind. The first is that not all cuts "pay for themselves" by reducing the number of iterations enough to compensate for the extra computational burden they create in each iteration. The second is that the solve model - ad cut(s) - solve model cycle tends to create a fair bit of redundant work, at least for MIPs. (For LPs, hot-starting from the final basis of the previous solve *may* dramatically reduce the rework, but there is no guarantee; "repairing" the old basis to adapt to the new cut(s) sometimes is more work than starting from scratch.) With MIPs, at least, it is often better to do a single solve and add cuts in a callback rather than do the solve - cut - solve cycle. MIP hot-starts tend not to be as efficient as LP hot-starts.

      Delete
  5. Thanks for the reply. Well it is an MIP problem and these inequalities are created and then added to the MIP model as model.add but it feels that cplex recognizes the inequalities as part of the original formulation. e.g.
    original model is max 1x1+1x2+3x3+2x4 s.t. 2x1+1x2+4x3+3x4<=5 and when the cuts are added then the MIP model becomes:
    Max 1x1+1x2+3x3+2x4 s.t.
    2x1+1x2+4x3+3x4<=5
    1x1<=1
    1x1+1x2<=2
    1x1+1x2+3x3<=4
    1x1+1x2+3x3+2x4<=4
    0<=x<=1: integers
    But I would like cplex to recognize them as separate from the original model as this:
    Max 1x1+1x2+3x3+2x4 s.t.
    2x1+1x2+4x3+3x4<=5
    cuts:
    1x1<=1
    1x1+1x2<=2
    1x1+1x2+3x3<=4
    1x1+1x2+3x3+2x4<=4
    0<=x<=1: integers
    Any help is much appreciated. Thanks!


    ReplyDelete
    Replies
    1. CPLEX tightens a MIP model during the presolve phase and generates its own cuts at the root node (and usually at other nodes). It's possible that your cuts are implied by the ones CPLEX generates, and thus do not speed things up. If that's the case, adding them through callbacks will not help; the cuts themselves are simply not useful.

      One way to test this is to use parameter settings to turn off all of CPLEX's cut generation, and also turn off presolving. Also turn off the advanced start switch just to be safe; we don't want a hot start affecting timing. Run the model and time the solution. Then, without turning anything back on, add your cuts to the model and solve it again. If the second solution time is no better (or worse) than the first, your cuts are ineffective. If the second solution is faster, your cuts help. Turn everything except advanced starts back on and repeat the experiment. If your cuts helped with everything off but not with everything on, they're implied by something CPLEX is doing (CPLEX cuts or presolve reductions).

      Delete
  6. So how do I added these cuts in a callback as you suggested?

    ReplyDelete
    Replies
    1. Use of callbacks is covered in the user manual, and the example programs provided in the CPLEX installation contain instances that use callbacks. Since your cuts do not remove any solutions that be feasible in their absence, they would be classified as "user cuts" rather than "lazy constraints", so you would use an instance of IloCplex.UserCutCallback.

      Delete
  7. Thank you. Secondly, am apply sequential lifting to strengthen the inequalities. Do you by any means have an idea? Thank you.

    ReplyDelete
  8. How do I put this in a loop Sir:

    static double solveLIFT_Sub()
    {

    IloEnv envsub;

    IloInt nProd = n1;
    IloInt p;

    IloModel modellift(envsub);

    // VARIABLES
    IloNumVarArray z(envsub, nProd, 0, 1, ILOINT); // MIP

    IloExpr TotalRevenue(envsub);
    for (p = 0; p < nProd/s; p++) {

    TotalRevenue += Valu[p+1] * z[p];

    }
    modellift.add(IloMaximize(envsub, TotalRevenue));
    TotalRevenue.end();


    // CAPACITY CONSTRAINT 1

    IloExpr totalweightExpr(envsub);
    for (p = 0; p < nProd; p++) {
    totalweightExpr += Weght[p+1] * z[p];
    }
    modellift.add(totalweightExpr <= budget);
    totalweightExpr.end();

    modellift.add(z[n1/s]==1);

    IloCplex cplex(envsub);

    cplex.setOut(envsub.getNullStream());

    cplex.extract(modellift);

    cplex.solve();

    cplex.exportModel("relax_LIFt.lp");

    return cplex.getObjValue();

    envsub.end();
    }

    ReplyDelete
    Replies
    1. I'm sorry, but your questions are not connected to the topic of the post on any way that I can fathom. This is a blog, not a support forum. Perhaps you could find help on one of the CPLEX forums.

      Delete

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.