<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Luis,<br>
<br>
Fixed the assertion fail.<br>
<br>
I don't think, for difficult problems, it is possible to get good
results by replacing constraints by branching rules.<br>
<br>
I think a better approach is to make the LP solver faster for
problems with many constraints.<br>
<br>
I have added driverFat.cpp to Cbc/examples. It is not tidied up,
but may improve things for you. For a previously posted lp -
test.lp with 998212 rows and 106780 columns it solved completely
in under three hours (okay - using four threads).<br>
<br>
One could probably do better if the driver was more intelligent on
strong branching - which would not take long to code. As it was,
I just turned that off.<br>
<br>
John Forrest<br>
On 28/10/16 15:51, Luís Borges de Oliveira wrote:<br>
</div>
<blockquote cite="mid:581365D4.9040503@siscog.pt" type="cite">
<meta http-equiv="Context-Type" content="text/html;
charset=windows-1252">
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">
<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 moz-do-not-send="true"
href="https://drive.google.com/open?id=0B-MC30EQsgcseTBfLTZEMldfYlU">sos-2.lp</a>
(like sos.lp, but with a few extra constraints), <a
moz-do-not-send="true"
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
moz-do-not-send="true"
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>
</blockquote>
<p><br>
</p>
</body>
</html>