[Cbc] Segfault solving a problem containing SOSs

[John Forrest]

Luis,

Fixed the assertion fail.

I don't think, for difficult problems, it is possible to get good 
results by replacing constraints by branching rules.

I think a better approach is to make the LP solver faster for problems 
with many constraints.

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).

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.

John Forrest
On 28/10/16 15:51, Luís Borges de Oliveira wrote:
> Hello John,
>
> On 26-10-2016 13:03, John Forrest wrote:
>> 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.
>>
>> 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.
>>
>> 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.
>
> 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.)
>
> 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:
>
>     Node 81 depth 35 unsatisfied 19 sum 25.2824 obj 97 guess 97.0002
>     branching on -1
>     Cbc0015I Node 81 Obj 97 Unsat 19 depth 35
>     Cbc0039I On closer inspection - solution discarded
>     Cbc0021I On closer inspection node is infeasible
>     Node 82 depth 36 unsatisfied 18 sum 7.22246 obj 97 guess 97.0002
>     branching on -1
>     Cbc0015I Node 82 Obj 97 Unsat 18 depth 36
>     Assertion failed!
>
>     Program: coin-or-cbc\build\bin\cbc.exe
>     File: Clp/src/ClpNonLinearCost.cpp, Line 1035
>
>     Expression: lowerValue<=upperValue
>
>
> 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.
>
> Is there any hope of having heuristics work well in the presence of SOS?
>
> In case you're inclined to play with the augmented model, here it is: 
> sos-2.lp 
> <https://drive.google.com/open?id=0B-MC30EQsgcseTBfLTZEMldfYlU> (like 
> sos.lp, but with a few extra constraints), sos-2-orig.lp 
> <https://drive.google.com/open?id=0B-MC30EQsgcsc2YtTkhzcHc4cms> (with 
> sos moved back to constraints, in case it's useful) and 
> sos-2-mipstart.txt 
> <https://drive.google.com/open?id=0B-MC30EQsgcsSTN2dHRfYVM0clk> (the 
> solution provided by feasibility pump to sos-2-orig.lp).
>
> To sum up, these are the test cases I've mentioned above:
>
>  1. $ build-SOS_AS_CUTS/bin/cbc sos-2.lp
>     (fails a lowerValue<=upperValue assertion)
>
>  2. $ build/bin/cbc -import sos-2-orig.lp -mipstart sos-2-mipstart.txt
>     -solve
>     (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)
>
>  3. $ build-SOS_AS_CUTS/bin/cbc sos-2.lp -mipstart sos-2-mipstart.txt
>     -solve
>     (hoping that RINS would work well here, but fails fast due to #1)
>
>  4. $ build-SOS_AS_CUTS/bin/cbc sos.lp -mipstart sos-2-mipstart.txt -solve
>     (hoping that RINS would work well here, but same behaviour as #2)
>
>
> Cheers,
> Luís


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20161103/bfbddcdc/attachment.html>