[Scip] ENFOLP vs. SEPALP

Gerald Gamrath gamrath at zib.de
Thu Apr 18 18:22:25 MEST 2013


Hi Daniel,

you are right, if the SEPALP does not hit any limit, the ENFOLP should
never find a violated cut.

The ENFOLP is the more important callback, it checks whether the final
LP solution at a node is feasible. If all constraints handlers return
feasible, the solution is accepted as a primal solution. Normally, if a
constraint handler detects infeasibility, it resolves the infeasibility
by branching. The integrality constraint handler, for example, will
issue branching when it detects a fractional discrete variable. So some
infeasibilities cannot be resolved by adding cutting planes in advance.
It might also be possible that you only want to generate a certain type
of cuts in the SEPALP callback, and only do the more expensive cut
generation of another kind of cuts only later.

But you are right, the option to add a cutting plane in the ENFOLP
callback is almost never used, because you will do this already in
SEPALP. In priciple, you could also implement a branch-and-cut algorithm
by using only the ENFOLP callback to separate cuts, but this creates a
lot of overhead compared to generating the cuts in the price and cut
loop and would also ignore the sepastore which filters the cuts.

Best,
Gerald

On 18.04.2013 17:32, Daniel Karch wrote:
> Hi Gerald and Michael,
>
> 2013/4/17 Gerald Gamrath <gamrath at zib.de <mailto:gamrath at zib.de>>
>
>
>     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).
>
>
> Okay, in my understanding of branch and cut, a node's LP is solved to
> optimality. If some constraint C is violated that was not represented
> in the initial LP formulation,
> a cut is generated that cuts off the LP solution (and does not cut off
> any solution that satisfies the constraint C). Then, the LP is
> reoptimized, until constraint C is not
> violated any more. Suppose that I added all those cutting planes in
> SEPALP. How can the ENFOLP callback find that the LP solution is
> infeasible then?
> For example, you say that
>
> > 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.
>
> Does that mean that ENFOLP can *only* find a subtour if the limit in
> SEPALP was reached?
> I am really confused about the similarities/differences of SEPALP and
> ENFOLP. If they are so similar, are both really needed?
> I feel like I am missing something here ...
>
> Anyways, thanks for the explanation.
>
> Best regards,
>
>   Daniel
>
>

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


More information about the Scip mailing list