[Cbc] Segfault solving a problem containing SOSs

[Luís Borges de Oliveira]

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/20161028/cead47f7/attachment.html>