[Osi] re-solving with osiclp branchAndBound

Tue Apr 14 05:16:11 EDT 2009

John,

Thanks again.
Indeed as you proposed for CLP branchAndBound, the

model.branchAndBound();
[..]
model.setColLower(saveLower);
model.setColUpper(saveUpper);
model.setDblParam(OsiDualObjectiveLimit,objLimit);

is a big part of the trick.
Actually, I  have now implemented this  in my code as

model.branchAndBound();
model.restoreBaseModel(n);
model.setDblParam(OsiDualObjectiveLimit,objLimit);

since, I guess, the save/restore Base Model was introduced just for something like this.

Isnt save/restore Base Model similar to CBC save/reset Reference Model? If so, shouldn’t the OsiCbc implementation of save/restore Base Model call save/reset Reference Model?

Shouldn’t the  dual objective limit be reset either 1) at the end of branchAndBound(), or 2) within OsiClp::restoreBaseModel?
Also, (similar to my CBC question about save/restore Reference Model), shouldn’t this behavior be standard for Osi “Solve” calls, ie, that they automatically cleanup/reset after themselves?

Lastly, this
CbcModel model2(model);
is only a good solution if it doesn’t mean we start keeping duplicate copies of the (potentially large) problems around..
And this only works if the resetting (see above) was don’t properly, since otherwise the wrong bounds etc will be copied.

Regards,

Jan-Willem

From: osi-bounces at list.coin-or.org [mailto:osi-bounces at list.coin-or.org] On Behalf Of John J Forrest
Sent: Wednesday, April 08, 2009 11:54
Cc: osi at list.coin-or.org; cbc at list.coin-or.org
Subject: Re: [Osi] re-solving with osiclp branchAndBound

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

[cid:image001.gif at 01C9BCF1.397F3CF0]Goossens Jan-Willem ---04/06/2009 11:55:38 AM---Hi,

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/20090414/a136825e/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.gif
Type: image/gif
Size: 105 bytes
Desc: image001.gif
URL: <http://list.coin-or.org/pipermail/osi/attachments/20090414/a136825e/attachment.gif>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.png
Type: image/png
Size: 168 bytes
Desc: image003.png
URL: <http://list.coin-or.org/pipermail/osi/attachments/20090414/a136825e/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image004.png
Type: image/png
Size: 166 bytes
Desc: image004.png
URL: <http://list.coin-or.org/pipermail/osi/attachments/20090414/a136825e/attachment-0001.png>