[SCIP] Detect a feasible LP node with infeasible values

[Wen-Yang Ku]

Dear Gerald,

Just an update, I have figured out how to get the correct results. In  
the CONSENFOLP, if I branch on the variable that takes a forbidden  
value, i.e., using SCIPbranchVarHole() to exclude the forbidden value,  
then the result is correct. If I simply return SCIP_INFEASIBLE, then  
the result is incorrect (I got sub-optimal solutions). Again thanks  
for your help!

Best,
Wen-Yang


Quoting Gerald Gamrath <gamrath at zib.de>:

> 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