[Scip] Heuristics - Shift and Propagate

Jacob Spönemann Jacob.Spoenemann at rwth-aachen.de
Wed Nov 2 16:12:26 MET 2011


  Hi Stefan, hi Timo,

again, thanks a lot for your fast replies!

@Timo: I know that the Gurobi interface causes the problem. But when I 
started my implementation and evaluations Gurobi was the most powerful 
solver, which could be used for academic purposes (to my knowledge at 
that time), so I chose Gurobi.

Is the Gurobi interface still under development? I was wondering that 
ranged rows cannot be handled by lpi_grb.c, since the Gurobi interface 
provides functions GRBaddrangeconstr and GRBaddrangeconstrs which even 
do not require a transformation of lhs & rhs into rhs & range like that 
transformation which is required for the use of CPLEX. The additional 
range variables added by Gurobi seem to me to be "harmless".

Best regards,

Jacob

Am 02.11.2011 15:14, schrieb Timo Berthold:
> Hi Jacob.
>
> The solution that you are suggesting should work. There is even a less
> invasive one (which does not require you to change SCIP sources and
> recompile SCIP): You can change th parameter
> heuristics/crossover/uselprows to FALSE (which from SCIP 2.1 onwards is
> the default). That will execute SCIPcopyParamSettings() automatically. To
> be sure, do the same thing for the RENS heuristic, (if you are using
> aggressive heuristic settings, also for all other LNS heuristics).
>
> However, the problem itself is in the Gurobi LP interface (beta status!)
> which does not support ranged rows. Shiftandpropagate (and Crossover) are
> only the triggers. If similar problems occur, or if you wanted to use SCIP
> in an automated environment, where failures would be critical, I recommend
> to link against a different LP solver.
>
> Cheers,
> Timo
>
>
>
>
>>    Hi Stefan,
>>
>> thanks for the fast reply!
>>
>> I am using 2.0.1 and, if possible, want stay with it, since I already
>> did lots of evaluations with that version.
>>
>> The only plugin I found which uses a second SCIP instance seems to be
>> the heuristic "Crossover", which is called right before the execution of
>> "Shift and Propagate" (->  stack trace). So adding
>> SCIPcopyParamSettings() in heur_crossover.c right after
>> SCIP_CALL(SCIPcreate(&subscip)); could fix my problem?
>>
>> Unfortunately, the error occurs after more than 3 hours of solving (the
>> error does not occur in smaller instances of the underlying problem), so
>> testing bugfixes takes some time...
>>
>> Best regards,
>>
>> Jacob
>>
>> Am 02.11.2011 12:51, schrieb Stefan Heinz:
>>> Hi Jacob,
>>>
>>> which SCIP version are you using (I hope 2.1.0 ;-)). Can you send us
>>> additionally a back trace.
>>>
>>> We are assuming that this problem occurs in subscip where the settings
>>> of the master SCIP are not copied. Are you using within one of your
>>> plugins a second SCIP instance? If so you should copy the settings by
>>> using:
>>>
>>> SCIPcopyParamSettings()
>>> http://scip.zib.de/doc/html/scip_8h.html#ade1245b4b0ecd94c85251d9330ed85ef
>>>
>>>
>>> Best Stefan
>>>
>>> On 11/02/11 09:52, Jacob Spönemann wrote:
>>>> Hi all,
>>>>
>>>> I implemented a column generation algorithm using SCIP and Gurobi.
>>>>
>>>> I am running into problems when the heuristic "Shift and Propagate"
>>>> is executed (in the end convertSides in lpi_grb.c causes the error
>>>> because the Gurobi interface cannot handle ranged rows). I tried to
>>>> disable the heuristic by setting the frequency parameter to -1, but
>>>> nevertheless the heuristic is executed.
>>>>
>>>> I observed that the value of the frequency parameter is set to 0
>>>> during solution process. Is there any chance to prevent that?
>>>>
>>>> Best regards,
>>>>
>>>> Jacob
>>>>
>>>> Am 31.01.2011 04:29, schrieb Stephen J Maher:
>>>>> Hi Gregor,
>>>>>
>>>>> I have been using the updated file that you sent to me. It worked
>>>>> well.
>>>>>
>>>>> Unfortunately I am having another problem with the shift and
>>>>> propagate heuristic. I have disabled it by setting the frequency
>>>>> parameter to -1, however I am getting the error
>>>>>
>>>>> src/scip/heur_shiftandpropagate.c:1464: heurExecShiftandpropagate:
>>>>> Assertion `SCIPisFeasEQ(scip, lb, ub)' failed
>>>>>
>>>>> Is there a way for me to avoid this error?
>>>>>
>>>>> Thanks for your help,
>>>>>
>>>>> Steve
>>>>>
>>>>>
>>>>>
>>>>> Gregor Hendel wrote:
>>>>>> Hi Steve,
>>>>>>
>>>>>> I have changed the file heur_shiftandpropagate.c, s.t. it should
>>>>>> work now. In the attachment, you'll find the file. Just replace
>>>>>> the old version in<scip-base-dir>/src/scip by the new one. I'm not
>>>>>> able to test it on column generation codes, so
>>>>>> please inform me if this bugfix has fixed your problem sufficiently.
>>>>>>
>>>>>>> HI Gregor,
>>>>>>>
>>>>>>> I have run my code using the debugger gdb and it seems that the
>>>>>>> problem with this heuristic occurs when the rens heuristic is
>>>>>>> called. The problem still exists when I disable both, the rens and
>>>>>>> shift-and-propagate, heuristics. If I disable all of the
>>>>>>> heuristics the problem doesn't occur.
>>>>>>>
>>>>>>> I am adding variables dynamically. I have a variable pricer that
>>>>>>> adds variables representing network flows. I am also adding
>>>>>>> constraints of the problem through a version of benders
>>>>>>> decomposition. At each iteration I am removing all variables from
>>>>>>> the master problem and reinitialising using the optimal variables
>>>>>>> from the previous iteration.
>>>>>>>
>>>>>>> The problem is written as a MIP with the network flow variables
>>>>>>> being binary and there is a set of continuous variables as well.
>>>>>>>
>>>>>>> Thanks a lot for your help.
>>>>>> Thank you for helping us developing a more stable SCIP version.
>>>>>>
>>>>>> Best, gregor
>>>>>
>>>>> _______________________________________________
>>>>> Scip mailing list
>>>>> Scip at zib.de
>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>
>>>>
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de
>>>> http://listserv.zib.de/mailman/listinfo/scip
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>



More information about the Scip mailing list