[Scip] Constraint Handler / CONSENFOLP method

[Stefan Vigerske]

Hi,

> I implemented a very short version of a constraint handler for the traveling salesman problem. Hereby, I implemented the "conscheck" method (which just says a solution is feasible or not) and the "consenfolp" method.
>
> Now to point of my question: Is it sufficient, just to return feasible or infeasible, in the enfolp method, again (especially not adding the violated inequalities, for saving programming effort - I just have to solve small instances)? If enfolp just returns feasible/infeasible, is the final solution still guaranteed to be optimal? What happens in detail (at the node) in the (mathematical) branch and bound tree, when a solution is recognised as infeasible?

You can return infeasible in the result pointer, if you are sure that 
SCIP knows how to proceed then :-).

That is, if there are still unfixed binary or integer variables left, 
then SCIPs branching rules will be applied to branch on one of these 
variables.
If all discrete variables are fixed and there are no continuous 
variables, then SCIP will cutoff the node.

If all discrete variables are fixed and there are still continuous 
variables (I guess not your case), then SCIP would not know how to 
proceed and the behavior is "not defined".

If you only declare the current solution as infeasible and there are no 
fractional variables in the current node, then SCIP will choose one of 
the unfixed variables for branching. However, since the branching rules 
do not know your constraints, it may do a useless branch that does not 
change anything on the infeasiblity of your constraints. Thus, you may 
still want to implement an own branching rule in the ENFOLP/ENFOPS 
callbacks. Or you could register the variables in the violated 
constraints as "external branching candidates" (SCIPaddExternBranchCand) 
and still return infeasible in the result pointer. If there are no 
fractional discrete variables, then SCIP should try branching on one of 
the external branching candidates before looking at all unfixed discrete 
variables.

Stefan

>
> Best Regards
>
> Martin Tieves
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>


-- 
Stefan Vigerske
Humboldt University Berlin, Numerical Mathematics
http://www.math.hu-berlin.de/~stefan