[Osi] re-solving with osiclp branchAndBound

Wed Apr 8 05:53:50 EDT 2009

Jan-Willem,

Looking at your driver, maybe a very simple approach will work best.  I
have put a driver into Cbc/trunk as Cbc/examples/simpleBAB.cpp but it can
be used from stable.  If USE_CBC is defined it uses CbcModel to solve two
IPs and if it is not defined uses OsiCl branchAndBound.

Hope it helps.

John
--------------------------
  OsiClpSolverInterface model;

  int start[] = { 0, 1, 2};
  int index[] = { 0, 0};
  double values[] = {1.0, 2.0};
  double collb[] = {0.0, 0.0};
  double colub[] = {10.0, 10.0};
  double obj[] = { 1.0, 1.0};
  double rowlb[] = { 0.0};
  double rowub[]= { 3.9};

  // obj: Max x0 + x1
  //  st. x0 + 2 x1 <= 3.9
  //          0 <= x0 <= 10 and integer
  //          0 <= x1 <= 10
  model.loadProblem(2, 1, start, index, values, collb, colub, obj, rowlb, rowub);
  model.setInteger(0);
  model.setObjSense(-1.0);
  bool optimal;

#ifndef USE_CBC
  // Save bounds - that and dual limit should be all that is needed
  // For this simple example we could just re-use collb and colub
  double saveLower[2];
  double saveUpper[2];
  int numberColumns = model.getNumCols();
  CoinCopyN(model.getColLower(),numberColumns,saveLower);
  CoinCopyN(model.getColUpper(),numberColumns,saveUpper);
  double objLimit;
  model.getDblParam(OsiDualObjectiveLimit,objLimit);
  model.branchAndBound();
  optimal = model.isProvenOptimal();
  const double *val = model.getColSolution(); // x0 = 3, x1 = 0.45
  printf("Solution %g %g\n",val[0],val[1]);
  // Restore bounds and dual limit
  model.setColLower(saveLower);
  model.setColUpper(saveUpper);
  model.setDblParam(OsiDualObjectiveLimit,objLimit);
#else
  {
    CbcModel model2(model);
    model2.branchAndBound();
    optimal = model2.isProvenOptimal();
    const double *val = model2.getColSolution(); // x0 = 3, x1 = 0.45
    printf("Solution %g %g\n",val[0],val[1]);
  }
#endif

  const int rowCols[] = {0};
  const double rowElements = { 1.0};

  // add x0 <= 2, and solve once again.
  CoinPackedVector v(1, rowCols, rowElements);
  model.addRow(v, 0.0, 2.0);
#ifndef USE_CBC
  model.branchAndBound();
  optimal = model.isProvenOptimal(); // should be x0 = 2, x1 = 0.95
  // Address of solution will be same as only adding rows - but be safe
  val = model.getColSolution();
  printf("Solution %g %g\n",val[0],val[1]);
#else
  {
    CbcModel model2(model);
    model2.branchAndBound();
    optimal = model2.isProvenOptimal(); // should be x0 = 2, x1 = 0.95
    const double *val = model2.getColSolution();
    printf("Solution %g %g\n",val[0],val[1]);
  }
#endif

  From:       Goossens Jan-Willem <Jan-Willem.Goossens at nc3a.nato.int>                                                

  To:         "osi at list.coin-or.org" <osi at list.coin-or.org>                                                          

  Date:       04/06/2009 11:55 AM                                                                                    

  Subject:    [Osi] re-solving with osiclp branchAndBound                                                            

Hi,

I understand that the branchAndBound support within OsiClp is meant to be
only basic. Still:

How can I branchAndBound(), then add a constraint, and branchAndBound()
again?
Just like that, it doesn’t work. With CBC’s saveReferenceModel in mind, I
tried

      OsiClpSolverInterface model;

      int start[] = { 0, 1, 2};
      int index[] = { 0, 0};
      double values[] = {1.0, 2.0};
      double collb[] = {0.0, 0.0};
      double colub[] = {10.0, 10.0};
      double obj[] = { 1.0, 1.0};
      double rowlb[] = { 0.0};
      double rowub[]= { 3.9};

      // obj: Max x0 + x1
      //  st. x0 + 2 x1 <= 3.9
      //          0 <= x0 <= 10 and integer
      //          0 <= x1 <= 10
      model.loadProblem(2, 1, start, index, values, collb, colub, obj,
rowlb, rowub);
      model.setInteger(0);
      model.setObjSense(-1.0);

      model.saveBaseModel(); // maybe this helps, and restoreBaseModel(1)
      model.branchAndBound();
      bool optimal = model.isProvenOptimal();
      const double *val = model.getColSolution(); // x0 = 3, x1 = 0.45
      model.restoreBaseModel(1);

      const int rowCols[] = {0};
      const double rowElements = { 1.0};

      // add x0 <= 2, and solve once again.
      CoinPackedVector v(1, rowCols, rowElements);
      model.addRow(v, 0.0, 2.0);
      model.branchAndBound();
      optimal = model.isProvenOptimal(); // should be x0 = 2, x1 = 0.95

Gives the output

Clp0006I 0  Obj 3.45 Primal inf 1 (1) Dual inf 1e+010 (1)
Clp0006I 1  Obj 2.95
Clp0000I Optimal - objective value 2.95
The LP relaxation is infeasible

So, almost there, but for some reason “The LP relaxation is infeasible”.
The reasons seems to be that within branchAndBound, the test
“isDualObjLimitReached” of the initialSolve returns true..

Note, I’m not working with the very latest sources, so if you cannot
reproduce this…

Thanks,

Jan-Willem
 _______________________________________________
Osi mailing list
Osi at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/osi

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/osi/attachments/20090408/f3239d51/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/osi/attachments/20090408/f3239d51/attachment.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ecblank.gif
Type: image/gif
Size: 45 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/osi/attachments/20090408/f3239d51/attachment-0001.gif>