<div dir="ltr">I have written a "relaxator" which is called after the LP relaxation (for the current node) has been solved.<div><br></div><div>It works (well, should work) by solving a combinatorial relaxation of the current problem: a subscip is created by copying some but not all of the main problem's constraints. An extra constraint is then added to this subscip which says that the objective value of any solution cannot be better (which means lower since we are working with the transformed problem) than that of the LP solution which has just been found: call this the "objlimit constraint". This subscip is then solved.</div><div><br></div><div>A problem I am having is that the objective value of the solution to this subscip is almost always slightly better than is allowed by the "objlimit" constraint. In some cases it is equal. Here is an example of that:</div><div><br></div><div>Here is an "objlimit" constraint (the LHS is the objective, the RHS the current lower bound):</div><div>....<br></div><div><div>+2233.687538<t_I#36#24>[B] +3470.976165<t_I#36#22#23#25>[B] +3514.739589<t_I#36#22#25#34>[B] +3600.517959<t_I#36#22#25#26>[B] +3602.888251<t_I#36#22#25>[B] +4315.968312<t_I#36#23#25#26>[B] +4353.360389<t_I#36#25#26#34>[B] +4364.720055<t_I#36#25#26>[B] </div><div>....</div><div>+7696.24707<t_I#36#19#27>[B] +7755.844738<t_I#36#27#32>[B] +7767.597019<t_I#36#21#27>[B] +7769.766551<t_I#36#27>[B] +8160.498138<t_I#36#17#28>[B] +8232.30374<t_I#36#28>[B] +8344.946419<t_I#36>[B] >= 97290.4565854556;</div><div><br></div></div><div><div>And here is a solution to my relaxed problem, containing the above objlimit constraint:<br></div><div><br></div><div>objective value: 97290.443308</div><div>t_I#0#13 1 <span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(obj:575.319346)</div><div>t_I#2 1 <span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(obj:1558.283114)</div><div>t_I#3#8#15#33 1 <span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(obj:708.049421)</div><div>....</div><div><div>t_I#36#24 1 <span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(obj:2233.687538)</div></div><div><br></div><div>Clearly, we illegally have a solution with obj value 97290.443308 which is strictly lower than 97290.4565854556</div><div><br></div><div>Am I right in thinking that this is some sort of rounding error? Is there perhaps a better way of indicating that only solutions which are no better than some value are allowed? The objlimit constraint contains every variable (!) so perhaps it should be no surprise that there are problems.</div><div><br></div><div>I suspect that this particular relaxator approach may not be a great idea, but I would still like to get to the bottom of this phenomenon.</div><div><br></div><div>James</div><div><br></div><div><br></div>-- <br><div class="gmail_signature">James Cussens<br>Dept of Computer Science &<br>York Centre for Complex Systems Analysis<br>Room 326, The Hub, Deramore Lane Tel +44 (0)1904 325371<br>University of York Fax +44 (0)1904 500159<br>York YO10 5GE, UK <a href="http://www.cs.york.ac.uk/~jc" target="_blank">http://www.cs.york.ac.uk/~jc</a><br><a href="http://www.york.ac.uk/docs/disclaimer/email.htm" target="_blank">http://www.york.ac.uk/docs/disclaimer/email.htm</a></div>
</div></div>