[SCIP] Separators and constraint handlers

[Ambros Gleixner]

Dear Teo,

The documentation is admittedly confusing here.  Of course you can use a 
separator for problem-specific cuts.  (Under the general condition that 
these cuts do not function as model constraints, but only tighten your 
formulation.)

What the documentation is trying to say: If the cuts are derived from 
constraints of one special type, then the sepa callback of that 
constraint handler is the recommended place, although implementing a 
separator plugin would also be possible.  But if "problem-specific" 
means something more general, using problem data or the combination of 
several constraints or the entire LP relaxation or ... then a separator 
plugin is needed.

I hope that clarifies things, we will adjust this section in the 
documentation.

Best,
Ambros


Am 19.06.2018 um 12:23 schrieb Teo Blast:
> 
> Hi,
> I am quite confused by the documentation about these C++ classes.
> The answer to the question "when should I use separators vs constraint 
> handlers" in the FAQ is as follows:
> 
> “This depends on whether you want to add constraints or only cutting 
> planes. The main difference is that constraints can be "model 
> constraints", while cutting planes are only additional LP rows that 
> strengthen the LP relaxation. A model constraint is a constraint that is 
> important for the feasibility of the integral solutions. If you delete a 
> model constraint, some infeasible integral vectors would suddenly become 
> feasible in the reduced model. A cutting plane is redundant w.r.t. 
> integral solutions. The set of feasible integral vectors does not change 
> if a cutting plane is removed. You can, however, relax this condition 
> slightly and add cutting planes that do cut off feasible solutions, as 
> long as at least one of the optimal solutions remains feasible. “
> 
> 
> I want to implement cutting planes, which are redundant w.r.t. integral 
> solutions,. Itwould thus seem that I need a separator.
> 
> However, the separator description reads:
> “Separators are used to generate general purpose cutting planes. 
> Constraint based cutting planes, the second type of cutting planes in 
> SCIP, are separated in the CONSSEPALP and CONSSEPASOL callback methods 
> of the constraint handlers, seeCONSSEPALP 
> <http://scip.zib.de/doc-5.0.1/html/CONS.php#CONSSEPALP>andCONSSEPASOL 
> <http://scip.zib.de/doc-5.0.1/html/CONS.php#CONSSEPASOL>. These cuts are 
> valid inequalities or even facets of the polyhedron described by a 
> single constraint or a subset of the constraints of a single constraint 
> class. In contrast, general purpose cuts do not require or exploit any 
> knowledge about the underlying problem structure but use only the 
> current LP relaxation and the integrality conditions.”
> 
> The cutting planes I want to implement are problem-specific (they are 
> facets of the problem's polyhedron), thus they are not "general purpose" 
> cutting planes. So they cannot be separated with a separator?
> Doesn't it contradict the FAQ answer?
> 
> Many thanks in advance !
> 
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
> 

-- 
Ambros Gleixner, Research Group Mathematical Optimization Methods at 
Zuse Institute Berlin, http://www.zib.de/gleixner