[Scip] Branch-Price to Branch-cut-Price
Gerald Gamrath
gamrath at zib.de
Tue Jun 24 17:36:34 CEST 2014
Dear Christina, dear Ambros,
the CONSINITLP callback is made for putting the initial linear
relaxation of a constraint into the LP. It is normally called only once
per constraint, because the row was then added to the LP and more
involved linearizations (if any) are separated in later. Therefore, it
is not designed for what you want to do.
The rough scheme for solving the LP at a node is:
1) put initial constraints into LP (if not done yet)
2) solve the current (restricted) LP
3) generate new columns
4) if new columns added: goto 2, else: goto 5
5) generate cutting planes
6) if cuts added: goto 2, else: done.
The cuts that you generate are specific to the current LP solution or
based on the problem and what branching decision was added for the
current node? The CONSINITLP callback is called before the current
(restricted) LP is solved, so you actually don't have a valid LP
solution for the current node, yet. If there is some way to improve the
LP relaxation based on your last branching decision, then it would make
sense to add the rows at this point. However, how do you do the
branching? If you use a constraint handler to store branching decisions,
I would recommend to use the CONSINITLP callback of the branching
constraint to add the rows to the LP when the node is activated.
On the other hand, if you want to cut off suboptimal LP solutions, you
would need to generate cutting planes every time after 2). However, this
would mean that you spend time for cutting off suboptimal LP solutions,
and generate cuts at a side of the polyhedron which might be far away
from the optimal LP face at the current node. Therefore, SCIP waits
until the unrestricted LP was solved to optimality before starting the
separation process as this guarantees that cuts reduce the optimal face.
Currently, it is not possible to call a separator after 2). Do you have
strong arguments for doing it at that point? Then we can try to add some
code to allow this.
Best,
Gerald
On 20.06.2014 07:04, Ambros Gleixner wrote:
> Dear Cristina,
>
> I am guessing your constraint handler does not have any constraints
> and hence also no constraints marked as initial. In this case, in
> cons.c:2690 (SCIP 3.1), SCIP returns before calling the consinitlp
> callback:
>
> if( conshdlr->ninitconss == 0 || (!initkeptconss &&
> conshdlr->ninitconss == conshdlr->ninitconsskept) )
> return SCIP_OKAY;
>
> Could you analyze whether this is the case by adding some debug
> messages; if yes, then as a first workaround you could try to remove
> these lines.
>
> (A cleaner solution could be to generally allow calling the callback
> in case CONSHDLR_NEEDSCONS is set to FALSE, but this needs some more
> discussion.)
>
> Cheers,
> ambros
>
>
> Am 19.06.2014 11:20, schrieb Cristina Núñez del Toro:
>> Hello again,
>>
>> I finally implemented a constraint handler (instead of a separator) in
>> order to add cutting planes during the pricing loop.
>>
>> As you (Ambros) suggested me, I implemented the CONSINITLP callback.
>> However, when I do the execution, this callback never starts. I was
>> thinking that maybe I'm leaving out some starting parameter or putting
>> some variable in a incorrect way.
>> Is there a specific activation parameter that I must consider?
>>
>> I'm pretty sure the Constraint Handler is running during the execution
>> because I am able to add cutting planes after finishing the pricing by
>> using the CONSSEPALP callback, however my intention is to use CONSINITLP
>> instead of CONNSEPALP.
>>
>>
>>
>> Thank you for your help,
>>
>>
>>
>>
>> 2014-06-12 10:24 GMT+02:00 Cristina Núñez del Toro
>> <cristina.nunez at upc.edu <mailto:cristina.nunez at upc.edu>>:
>>
>> Hello Ambros,
>>
>> My idea is to cutt off already the suboptimal LP solutions just
>> before the pricing loop starts. What I want is to strengthen the LP
>> solution before looking for new columns. However, doing it during
>> the pricing loop may help as well. I will try the CONSINITLP
>> callback.
>>
>> Thank you.
>>
>>
>>
>> 2014-06-11 19:40 GMT+02:00 Ambros Gleixner <gleixner at zib.de
>> <mailto:gleixner at zib.de>>:
>>
>> Dear Cristina,
>>
>> as far as I know, you cannot call separators before pricing.
>> However, you can implement the CONSINITLP callback of a
>> constraint handler, which can add cutting planes during the
>> pricing loop.
>>
>> Maybe you can describe a bit better what you want to do exactly.
>> Would you want to cut off already the suboptimal LP solutions
>> during the pricing loops (is that possible?) or add cutting
>> planes that are independent of the solution?
>>
>> Cheers,
>> Ambros
>>
>>
>>
>> Am 06.06.2014 19:30, schrieb Cristina Núñez del Toro:
>>
>> Dear Mailing List,
>>
>> I am currently working on a Branch-and-Price algorithm. My
>> next step is
>> to strength the LP relaxation at nodes, so I implemented a
>> plug-in
>> separator in order to add cutting planes. My idea is to add
>> cutting
>> planes before start looking for new columns.
>>
>> However, I have noticed that at each node, the variable
>> pricer plug-in
>> is executed in the first place and then, when no more
>> columns are added,
>> the separator plug-in starts. Is there a way to change the
>> order of the
>> plug-in's execution? i.e., start first with the separator
>> and then, when
>> no more cuts can be added, execute the variable pricer?
>> Maybe I am
>> leaving outa callback ?
>>
>> Thanks in advance.
>>
>> --
>> ---
>> Cristina Nuñez
>>
>>
>> _________________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto:Scip at zib.de>
>> http://listserv.zib.de/__mailman/listinfo/scip
>> <http://listserv.zib.de/mailman/listinfo/scip>
>>
>>
>> --
>> ______________________________________________________________
>> Ambros M. Gleixner
>> Zuse Institute Berlin - Matheon - Berlin Mathematical School
>> http://www.zib.de/gleixner
>> _________________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto:Scip at zib.de>
>> http://listserv.zib.de/__mailman/listinfo/scip
>> <http://listserv.zib.de/mailman/listinfo/scip>
>>
>>
>>
>>
>> --
>> ---
>> Cristina Nuñez
>>
>>
>>
>>
>> --
>> ---
>> Cristina Nuñez
>
More information about the Scip
mailing list