<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=utf-8">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
tt
{mso-style-priority:99;
font-family:"Courier New";}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>John,<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Thanks again.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Indeed as you proposed for CLP branchAndBound, the <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal>model.branchAndBound();<br>
[..]<o:p></o:p></p>
<p class=MsoNormal>model.setColLower(saveLower);<br>
model.setColUpper(saveUpper);<br>
<b>model.setDblParam(OsiDualObjectiveLimit,objLimit);<o:p></o:p></b></p>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>is a big part of the trick.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Actually, I have now implemented this in my code as<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal>model.branchAndBound();<o:p></o:p></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>model.restoreBaseModel(n);</span><br>
model.setDblParam(OsiDualObjectiveLimit,objLimit);<o:p></o:p></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>since, I guess, the save/restore Base Model was introduced just
for something like this.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>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?<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Shouldn’t the dual objective limit be reset either 1) at the
end of branchAndBound(), or 2) within OsiClp::restoreBaseModel?<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>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?<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Lastly, this<o:p></o:p></span></p>
<p class=MsoNormal>CbcModel model2(model);<br>
<span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>is
only a good solution if it doesn’t mean we start keeping duplicate copies of
the (potentially large) problems around.. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>And this only works if the resetting (see above) was don’t properly,
since otherwise the wrong bounds etc will be copied.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Regards,<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Jan-Willem<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<div>
<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in'>
<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span
style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>
osi-bounces@list.coin-or.org [mailto:osi-bounces@list.coin-or.org] <b>On Behalf
Of </b>John J Forrest<br>
<b>Sent:</b> Wednesday, April 08, 2009 11:54<br>
<b>Cc:</b> osi@list.coin-or.org; cbc@list.coin-or.org<br>
<b>Subject:</b> Re: [Osi] re-solving with osiclp branchAndBound<o:p></o:p></span></p>
</div>
</div>
<p class=MsoNormal><o:p> </o:p></p>
<p style='margin-bottom:12.0pt'>Jan-Willem,<br>
<br>
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.<br>
<br>
Hope it helps.<br>
<br>
John<br>
--------------------------<br>
OsiClpSolverInterface model;<br>
<br>
int start[] = { 0, 1, 2};<br>
int index[] = { 0, 0};<br>
double values[] = {1.0, 2.0};<br>
double collb[] = {0.0, 0.0};<br>
double colub[] = {10.0, 10.0};<br>
double obj[] = { 1.0, 1.0};<br>
double rowlb[] = { 0.0};<br>
double rowub[]= { 3.9};<br>
<br>
// obj: Max x0 + x1<br>
// st. x0 + 2 x1 <= 3.9<br>
// 0 <= x0 <= 10 and integer<br>
// 0 <= x1 <= 10<br>
model.loadProblem(2, 1, start, index, values, collb, colub, obj, rowlb, rowub);<br>
model.setInteger(0);<br>
model.setObjSense(-1.0);<br>
bool optimal;<br>
<br>
#ifndef USE_CBC<br>
// Save bounds - that and dual limit should be all that is needed<br>
// For this simple example we could just re-use collb and colub<br>
double saveLower[2];<br>
double saveUpper[2];<br>
int numberColumns = model.getNumCols();<br>
CoinCopyN(model.getColLower(),numberColumns,saveLower);<br>
CoinCopyN(model.getColUpper(),numberColumns,saveUpper);<br>
double objLimit;<br>
model.getDblParam(OsiDualObjectiveLimit,objLimit);<br>
model.branchAndBound();<br>
optimal = model.isProvenOptimal(); <br>
const double *val = model.getColSolution(); // x0 = 3, x1 = 0.45<br>
printf("Solution %g %g\n",val[0],val[1]);<br>
// Restore bounds and dual limit<br>
model.setColLower(saveLower);<br>
model.setColUpper(saveUpper);<br>
model.setDblParam(OsiDualObjectiveLimit,objLimit);<br>
#else<br>
{<br>
CbcModel model2(model);<br>
model2.branchAndBound();<br>
optimal = model2.isProvenOptimal(); <br>
const double *val = model2.getColSolution(); // x0 = 3, x1 = 0.45<br>
printf("Solution %g %g\n",val[0],val[1]);<br>
}<br>
#endif<br>
<br>
const int rowCols[] = {0};<br>
const double rowElements = { 1.0};<br>
<br>
// add x0 <= 2, and solve once again.<br>
CoinPackedVector v(1, rowCols, rowElements);<br>
model.addRow(v, 0.0, 2.0);<br>
#ifndef USE_CBC<br>
model.branchAndBound();<br>
optimal = model.isProvenOptimal(); // should be x0 = 2, x1 = 0.95<br>
// Address of solution will be same as only adding rows - but be safe<br>
val = model.getColSolution();<br>
printf("Solution %g %g\n",val[0],val[1]);<br>
#else<br>
{<br>
CbcModel model2(model);<br>
model2.branchAndBound();<br>
optimal = model2.isProvenOptimal(); // should be x0 = 2, x1 = 0.95<br>
const double *val = model2.getColSolution(); <br>
printf("Solution %g %g\n",val[0],val[1]);<br>
}<br>
#endif<br>
<br>
<br>
<img width=16 height=16 id="_x0000_i1065"
src="cid:image001.gif@01C9BCF1.397F3CF0"
alt="Inactive hide details for Goossens Jan-Willem ---04/06/2009 11:55:38 AM---Hi,"><span
style='color:#424282'>Goossens Jan-Willem ---04/06/2009 11:55:38 AM---Hi,</span><o:p></o:p></p>
<table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width="100%"
style='width:100.0%'>
<tr>
<td width="1%" valign=top style='width:1.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=96 height=1 id="_x0000_i1066"
src="cid:image003.png@01C9BCF1.397F3CF0"><br>
<span style='font-size:10.0pt;color:#5F5F5F'>From:</span><o:p></o:p></p>
</td>
<td width="100%" valign=top style='width:100.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=1 height=1 id="_x0000_i1067"
src="cid:image004.png@01C9BCF1.397F3CF0"><br>
<span style='font-size:10.0pt'>Goossens Jan-Willem
<Jan-Willem.Goossens@nc3a.nato.int></span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width="1%" valign=top style='width:1.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=96 height=1 id="_x0000_i1068"
src="cid:image003.png@01C9BCF1.397F3CF0"><br>
<span style='font-size:10.0pt;color:#5F5F5F'>To:</span><o:p></o:p></p>
</td>
<td width="100%" valign=top style='width:100.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=1 height=1 id="_x0000_i1069"
src="cid:image004.png@01C9BCF1.397F3CF0"><br>
<span style='font-size:10.0pt'>"osi@list.coin-or.org"
<osi@list.coin-or.org></span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width="1%" valign=top style='width:1.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=96 height=1 id="_x0000_i1070"
src="cid:image003.png@01C9BCF1.397F3CF0"><br>
<span style='font-size:10.0pt;color:#5F5F5F'>Date:</span><o:p></o:p></p>
</td>
<td width="100%" valign=top style='width:100.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=1 height=1 id="_x0000_i1071"
src="cid:image004.png@01C9BCF1.397F3CF0"><br>
<span style='font-size:10.0pt'>04/06/2009 11:55 AM</span><o:p></o:p></p>
</td>
</tr>
<tr>
<td width="1%" valign=top style='width:1.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=96 height=1 id="_x0000_i1072"
src="cid:image003.png@01C9BCF1.397F3CF0"><br>
<span style='font-size:10.0pt;color:#5F5F5F'>Subject:</span><o:p></o:p></p>
</td>
<td width="100%" valign=top style='width:100.0%;padding:0in 0in 0in 0in'>
<p class=MsoNormal><img width=1 height=1 id="_x0000_i1073"
src="cid:image004.png@01C9BCF1.397F3CF0"><br>
<span style='font-size:10.0pt'>[Osi] re-solving with osiclp branchAndBound</span><o:p></o:p></p>
</td>
</tr>
</table>
<div class=MsoNormal>
<hr size=2 width="100%" noshade style='color:#8091A5' align=left>
</div>
<p class=MsoNormal style='margin-bottom:12.0pt'><br>
<br>
<br>
Hi,<br>
<br>
I understand that the branchAndBound support within OsiClp is meant to be only
basic. Still:<br>
<br>
How can I branchAndBound(), then add a constraint, and branchAndBound() again?<br>
Just like that, it doesn’t work. With CBC’s saveReferenceModel in mind, I tried<br>
<br>
OsiClpSolverInterface model;<br>
<br>
<span style='color:blue'>int</span> start[] = { 0, 1, 2};<br>
<span style='color:blue'>int</span> index[] = { 0, 0};<br>
<span style='color:blue'>double</span> values[] = {1.0, 2.0};<br>
<span style='color:blue'>double</span> collb[] = {0.0, 0.0};<br>
<span style='color:blue'>double</span> colub[] = {10.0, 10.0};<br>
<span style='color:blue'>double</span> obj[] = { 1.0, 1.0};<br>
<span style='color:blue'>double</span> rowlb[] = { 0.0};<br>
<span style='color:blue'>double</span> rowub[]= { 3.9};<br>
<br>
<span style='color:green'>// obj: Max x0 + x1</span><br>
<span style='color:green'>// st. x0 + 2 x1 <= 3.9</span><br>
<span style='color:green'>// 0 <= x0 <= 10 and integer</span><br>
<span style='color:green'>// 0 <= x1 <= 10</span><br>
model.loadProblem(2, 1, start, index, values, collb, colub, obj, rowlb, rowub);<br>
model.setInteger(0);<br>
model.setObjSense(-1.0);<br>
<br>
model.saveBaseModel(); <span style='color:green'>// maybe this helps, and
restoreBaseModel(1)</span><br>
model.branchAndBound();<br>
<span style='color:blue'>bool</span> optimal = model.isProvenOptimal(); <br>
<span style='color:blue'>const</span> <span style='color:blue'>double</span>
*val = model.getColSolution(); <span style='color:green'>// x0 = 3, x1 = 0.45</span><br>
model.restoreBaseModel(1);<br>
<br>
<span style='color:blue'>const</span> <span style='color:blue'>int</span>
rowCols[] = {0};<br>
<span style='color:blue'>const</span> <span style='color:blue'>double</span>
rowElements = { 1.0};<br>
<br>
<span style='color:green'>// add x0 <= 2, and solve once again.</span><br>
CoinPackedVector v(1, rowCols, rowElements);<br>
model.addRow(v, 0.0, 2.0);<br>
model.branchAndBound();<br>
optimal = model.isProvenOptimal(); <span style='color:green'>// should be x0 =
2, x1 = 0.95</span><br>
<br>
Gives the output<br>
<br>
<b>Clp0006I 0 Obj 3.45 Primal inf 1 (1) Dual inf 1e+010 (1)</b><br>
<b>Clp0006I 1 Obj 2.95</b><br>
<b>Clp0000I Optimal - objective value 2.95</b><br>
<b>The LP relaxation is infeasible</b><br>
<br>
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..<br>
<br>
Note, I’m not working with the very latest sources, so if you cannot reproduce
this…<br>
<br>
Thanks,<br>
<br>
Jan-Willem<br>
<tt><span style='font-size:10.0pt'>_______________________________________________</span></tt><span
style='font-size:10.0pt;font-family:"Courier New"'><br>
<tt>Osi mailing list</tt><br>
<tt>Osi@list.coin-or.org</tt><br>
<tt><a href="http://list.coin-or.org/mailman/listinfo/osi">http://list.coin-or.org/mailman/listinfo/osi</a></tt><br>
<br>
</span><o:p></o:p></p>
</div>
</body>
</html>