[Scip] ENFOLP vs. SEPALP

Gerald Gamrath gamrath at zib.de
Wed Apr 17 18:06:45 MEST 2013


Hi Daniel,

you are right, SEPALP and ENFOLP are somehow similar.

1) If you want to generate cuts for tightening your LP relaxation, you
should do that in SEPALP. The LP of the node is solved to optimality,
after that SCIP tries to cut off that solution using the SEPALP
callbacks, if cuts are added, the LP is reoptimized, separation is
performed, etc., until the current LP solution is not cut off anymore or
some limit is reached. (SEPALP is not called on non-optimal LP solutions).
In contrast, when the solving of a node is finished and the LP solution
is not integral, the ENFOLP callback is called. It should resolve the
infeasibility, which can be done, e.g., by branching, reducing the
domain of a variable, or adding a cutting plane (or constraint). After
the first constraint handler which resolves the infeasibility, the
enforcement is stopped, and depending what the constraint handler did,
either the node is finished or reoptimized (if cuts were added or bounds
tightened).

2) When creating a row, you can specify whether it is valid only locally
or globally. If the cut is only valid locally, you can add it to the
sepastore via SCIPaddCut(). It is then added to the current node (if it
is selected by the sepastore, which filters the cuts).
If it is global, you can also add it to the sepastore via SCIPaddCut(),
but is is still only added locally. Therefore, you should also add it to
the cutpool via SCIPaddPoolCut(). The cutpool contains globally valid
cuts and is separated before the (more expensive) separation SEPALP
callbacks are called.

3) This is indeed a strange comment. The SEPALP callback separates
subtour elimination constraints, but the ENFOLP callback does not. On
the one hand, the SEPALP callback already removes all subtours if not
terminated by some limit. On the other hand, by returning INFEASIBLE,
the ENFOLP causes SCIP to branch on a non-fixed variable.

Best,
Gerald and Michael

On 16.04.2013 18:47, Daniel Karch wrote:
> Hi,
>
> I have a few questions about the SEPALP and ENFOLP callbacks of a
> constraint handler.
> I am still not completely sure when to use what ...
>
> 1. As far as I understand, SEPALP should add cutting planes to the LP
> while it is being solved,
> and ENFOLP uses cutting planes to cut off an optimal LP solution. Is
> that correct?
> Does that mean that SEPALP also works on non-optimal LP solutions?
>
> 2. When a cutting plane is added via SCIPaddCut, which nodes "know"
> about it? Suppose
> node 0 creates a branching with children 1 and 2, and node 1 is
> treated before node 2. If
> I add a cutting plane in the SEPALP or ENFOLP callback of node 2 which
> is violated also in
> node 3, will it be separated automatically, or will it be violated
> again in node2? I.e., do I have
> to add it as a pool cut if I want it to be separated in node 2?
>
> 3. In the TSP example, the following lines in the ENFOLP callback
>
>     // if a subtour was found, we generate a cut constraint saying
> that there must be at least two outgoing edges
>     if( found )
>       *result = SCIP_INFEASIBLE;
>
> suggest that you do not generate a cut after all, but return
> SCIP_INFEASIBLE instead. Why?
>
>
> Best,
>
>   Daniel
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20130417/b4652914/attachment.html


More information about the Scip mailing list