[SCIP] Detect a feasible LP node with infeasible values

[Gerald Gamrath]

Dear Wen-Yang,

as long as there are unfixed integer variables, you are allowed to just 
return INFEASIBLE in your CONSENFOLP callback, because SCIP will then 
branch on one of the unfixed integer variables. If they are all fixed, 
your constraint handler may still return INFEASIBLE and register 
external branching candidates (e.g., for spatial branching). However, if 
you just return INFEASIBLE without any branching candidates available, 
SCIP will have no chance to resolve this infeasibility. Therefore, you 
should return SCIP_CUTOFF, meaning that the node with its current 
variable bounds (or fixings) contains no feasible solution.

The method you are looking for is SCIPgetNPseudoBranchCands(). This 
returns the number of unfixed integer variables (the candidates for 
pseudo branching, which is applied if there are no LP branching 
candidates).  SCIPgetNLPBranchCands() returns those LP branching 
candidates, which are just all integer variables with fractional value 
in the LP solution.

If you return SCIP_CUTOFF instead of SCIP_INFEASIBLE if there are no 
pseudo candidates, then SCIP will be able to solve the problem 
correctly. However, there are many ways how you can improve the solving 
behaviour:

1) In your current implementation, if a variable is locally fixed to a 
forbidden value, SCIP will just branch out all the other integer 
variables and whenever they are all fixed, you return SCIP_CUTOFF, so 
that the leaves of this subtree can finally be cut off. An easy fix for 
this would be to return SCIP_CUTOFF if the variable triggering the 
infeasibility is already fixed to the integer value.

2) In general, CONSENFOLP should try to resolve the infeasibility by 
branching or adding constraints, just returning SCIP_INFEASIBLE should 
be the last resort (or the starting point of your implementation since 
it already leads to a correct solver behaviour). In your case, if you 
detect that an unfixed variable has a forbidden LP value, you should 
probably branch on that variable, removing that infeasible value from 
both child node domains.

3) Finally, I would suggest to also implement the propagation callback 
of your constraint handler. This could detect infeasibility of a node if 
a variable is fixed to a forbidden value already before the node LP is 
solved. Moreover, it could tighten the variable domains, e.g. if one of 
the end points of the domain is forbidden.

Probably, you had already planned to implement at least some of that, 
but perhaps this gives you some new ideas.

Best,
Gerald

Am 18.02.2016 um 00:15 schrieb Wen-Yang Ku:
> Dear SCIP Community,
>
> I have developed a constraint handler to ensure that an integer 
> variable does not take a list of specific integer values as its 
> solution. In the CONSENFOLP function, I first check if the LP solution 
> of this integer variable is on the list. If it's on the list, then I 
> return SCIP_INFEASIBLE. However sometimes I will run into a situation: 
> "ERROR: LP was solved, all integers fixed, some constraint still 
> infeasible, but no branching could be created!". I looked at solver.c 
> and it seems that a feasible LP solution with all integer values fixed 
> has to be feasible. So I am wondering if there is a way to detect such 
> a LP node so I can cut it off and avoid the error. I currently tried 
> to detect such nodes with SCIPgetNLPBranchCands(scip)==0 and count the 
> number of the variables that are fixed to integers, but it gives me 
> more nodes than what I expected.
>
> Thank you very much.
>
> Best regards,
> Wen-Yang
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip