[SCIP] Constraint handler (especially TSP) documentation question

[Marc Pfetsch]

Dear Alexander!

On 06/05/2022 00.35, Alex Meiburg wrote:
> Hi, I'm following the TSP example, trying to understand the (somewhat 
> dizzying!) array of different callbacks for the constraint handler. I'm 
> particularly confused by the comment on line 359 of ConshdlrSubtour.cpp 
> (in SCIP version 8.0.0), in ENFOLP, where it says:
> 
> // if a subtour was found, we generate a cut constraint saying that 
> there must be at least two outgoing edges
> 
> immediately after a call to findSubtour. But as far as I can tell, 
> findSubtour only checks for a subtour, without actually adding any cuts. 

This is correct. The comment is misleading.

In this case, enforcing returns SCIP_INFEASIBLE. This means it relies on 
other components to handle infeasibility. This may lead into a dead end 
(= infinite loop) for which no resolution is possible. This happens if 
the LP solution is integral, but contains subtours (there could be 
another integral solution, which is feasible). In this case, one cannot 
branch on (fractional) variable to resolve infeasibility

Thus, I actually think that the implementation is wrong. It should 
rather add a cut as done in sepaSubtour.

> My understanding (and I would love it if someone could confirm or 
> correct me) is that:
> 
>   (1) ENFOPS, ENFOLP, and CHECK all *need* to check for feasibility and 
> return SCIP_FEASIBLE or SCIP_INFEASIBLE appropriately

Yes.

>   (2) ENFOPS and ENFOLP both *may* also add new 
> constraints/branch/change domains, and then return something else.

Yes, for a correct behavior they actually need to do something 
(branch/change domains ...) or be sure that another component handles this.

 > The
> difference between these two is that ENFOPS may be given variable 
> assignments that don't obey the current LP, and LP slack variables etc. 
> will not be defined.

Yes.

>   (3) SEPASOL and SEPALP both *need* to add constraints/cuts to separate 
> infeasible solutions.

No - they are allowed to add constraints/cuts, but do not need to. The 
enforcing methods need to do something (see above).

> SEPASOL is like ENFOPS in that won't necessarily 
> be given actual LP solutions.

Yes.

>   (4) The only *required* callbacks for a handler are ENFOLP, ENFOPS, 
> and and CHECK.

Yes.

> So the behavior of the TSP's ENFOLP example is acceptable, but a more 
> "complete" constraint handler would also add a cut there? The comment 
> was just a bit confusing.

Hmm, as mentioned above, it should actually add a cut.

> How important is it, performance-wise, to implement SEPASOL and SEPALP? 
> I assume that if I don't add *any* cuts ever in my constraint handler, 
> solving would be very very slow, so I add cuts in at least one of 
> {enfops, enfolp, sepasol, sepalp}. But, for example, if I add cuts in 
> ENFOPS and ENFOLP only, would I gain anything by also implementing 
> callbacks for SEPASOL and SEPALP? And vice versa -- if I implements 
> SEPASOL and SEPALP, what differences would I observe if I think also 
> added cuts in ENFOPS and ENFOLP?

There is no unique answer to this - it depends on your problem and in 
particular how expensive it is to produce cuts and solve the LPs.

For the TSP and subtour constraints it is very likely faster to separate 
cuts. If you have a more complicated constraint, then it might be more 
efficient to just implement enforcing and setting the parameters in such 
a way that enforcing is only called for integral solutions (a negative 
priority) and then produce a cut. Then SCIP will first make sure that 
the LP relaxation is integral before calling enforcing. This is often 
called "lazy cut approach" in the literature.

Best

Marc