<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hello John,<br>
<br>
<div class="moz-cite-prefix">On 26-10-2016 13:03, John Forrest
wrote:<br>
</div>
<blockquote
cite="mid:cfdd4e05-b8f7-a6cc-776c-b599f4cfa9ab@fastercoin.com"
type="cite">
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
<div class="moz-cite-prefix">I have modified (in trunk) the
preprocessing in heuristics to deal better with SOS. However
the heuristics may think they have found a solution but on later
checking decide it is invalid - so it may be easier to switch
off all heuristics.<br>
<br>
I noticed on the example you gave that putting back the SOS as
constraints the problem solved at root node, so you are losing
information by moving the constraints to SOS - but gaining a lot
in speed per node. I think that full formulation is greatly
strengthened in preprocessing so that the two variable
constraints are strengthened to have 5,6,... variables.
Unhappily it looks to be quite a lot of work to just do that
part of preprocessing without solving the LP's.<br>
<br>
I have checked in a bit of code that helps get the optimal
solution faster - but does no good in proving it to be optimal.
As it is work in progress, you would need to add -DSOS_AS_CUTS
to the configure options. This allows the SOS to be added back
as cuts.<br>
</div>
</blockquote>
<br>
I can confirm that indeed trunk rev 2308 fixes the crash on this
instance (thanks!) and that heuristics are apparently thwarted by
the SOS and generate invalid solutions. (That is unfortunate since
the Feasibility Pump + RINS duo seem to work quite well for these
models.)<br>
<br>
The sos.lp model was a simplified version with some constraints
removed. Adding them back, whenever heuristics are turned on, makes
Cbc fail the following assertion:<br>
<br>
<blockquote><tt>Node 81 depth 35 unsatisfied 19 sum 25.2824 obj 97
guess 97.0002 branching on -1</tt><br>
<tt>Cbc0015I Node 81 Obj 97 Unsat 19 depth 35</tt><br>
<tt>Cbc0039I On closer inspection - solution discarded</tt><br>
<tt>Cbc0021I On closer inspection node is infeasible</tt><br>
<tt>Node 82 depth 36 unsatisfied 18 sum 7.22246 obj 97 guess
97.0002 branching on -1</tt><br>
<tt>Cbc0015I Node 82 Obj 97 Unsat 18 depth 36</tt><br>
<tt>Assertion failed!</tt><br>
<br>
<tt>Program: coin-or-cbc\build\bin\cbc.exe</tt><br>
<tt>File: Clp/src/ClpNonLinearCost.cpp, Line 1035</tt><br>
<br>
<tt>Expression: lowerValue<=upperValue</tt><br>
</blockquote>
<br>
I didn't understand from your message whether SOS_AS_CUTS is meant
to improve the linear relaxation or to help heuristics as well.
Feasibility pump still returns an infeasible solution. (Is it
because it runs before the cut generator? If so, is there a way to
run it afterwards instead? Would that help?) My tests were
inconclusive because, for some reason I don't understand, passing
the feasibility pump solution via mipstart is not equivalent to
running feasibility pump and the RINS heuristic kicks in the former
scenario but not the latter, regardless of SOS_AS_CUTS.<br>
<br>
Is there any hope of having heuristics work well in the presence of
SOS?<br>
<br>
In case you're inclined to play with the augmented model, here it
is: <a
href="https://drive.google.com/open?id=0B-MC30EQsgcseTBfLTZEMldfYlU">sos-2.lp</a>
(like sos.lp, but with a few extra constraints), <a
href="https://drive.google.com/open?id=0B-MC30EQsgcsc2YtTkhzcHc4cms">sos-2-orig.lp</a>
(with sos moved back to constraints, in case it's useful) and <a
href="https://drive.google.com/open?id=0B-MC30EQsgcsSTN2dHRfYVM0clk">sos-2-mipstart.txt</a>
(the solution provided by feasibility pump to sos-2-orig.lp).<br>
<br>
To sum up, these are the test cases I've mentioned above:<br>
<ol>
<li><tt>$ build-SOS_AS_CUTS/bin/cbc sos-2.lp</tt><br>
(fails a lowerValue<=upperValue assertion)<br>
<tt><br>
</tt></li>
<li><tt>$ build/bin/cbc -import sos-2-orig.lp -mipstart
sos-2-mipstart.txt -solve</tt><br>
(to my surprise, RINS never kicks in, despite this model not
having SOS; it does kick in if feasability pump is used instead
of the equivalent sos-2-mipstart.txt)<br>
<br>
</li>
<li><tt>$ build-SOS_AS_CUTS/bin/cbc sos-2.lp -mipstart
sos-2-mipstart.txt -solve<br>
</tt>(hoping that RINS would work well here, but fails fast due
to #1)<br>
<br>
</li>
<li><tt>$ build-SOS_AS_CUTS/bin/cbc sos.lp -mipstart
sos-2-mipstart.txt -solve<br>
</tt>(hoping that RINS would work well here, but same behaviour
as #2)<br>
</li>
</ol>
<br>
Cheers,<br>
Luís<br>
</body>
</html>