[Scip] Constraint Handler / CONSENFOLP method

[Stefan Heinz]

Hi,

By the way SCIP comes with an example code for the TSP. See the 
"examples/TSP" directory. This example contains  the subtour elimination 
constraint handler. There you see what else you could do besides 
yielding feasible and infeasible.

Talking about that there is third and fourth callback you have to 
implement besides "conscheck" and "consenpfolp". These are 
"consenpfops", which does more or less the same as "consenfolp" in you 
case, and "conslock"  which should lock the variable w.r.t. rounding. 
See "src/scip/type_cons.h" for more details to these callbacks.

Best Stefan

On 10/20/11 20:54, Stefan Vigerske wrote:
> 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
>>
>