[SCIP] Disjunction constraints question

[Benjamin Müller]

Dear Rich,

the disjunction constraint handler does not rely on a big-M formulation 
to represent a disjunction. During the tree search, the constraint 
handler checks whether there is a violated disjunction

	C_1 v ... v C_K

and then generates K nodes N_1,...,N_K such that N_i contains the 
constraint C_i.

The advantage of this approach is that you don't need to add binary 
variables and linear constraints to model the disjunction. This might be 
beneficial if the LPs of a big-M formulation are expensive to solve. 
However, the downside of this approach is that SCIP's LP does not 
contain a linear relaxation for the disjunction (except that you use the 
relaxcons in SCIPcreateConsDisjunction). So the quality of your 
relaxation could be pretty poor, and thus you might need to branch much 
more compared to using a (big-M)-based formulation.

Best,
Benjamin


On 8/9/19 7:15 PM, Levinson, Richard J. (ARC-TI)[SGT, INC] wrote:
> Hello SCIP team,
> 
> 
> I am using disjunction constraints a lot and performance variability 
> which may go beyond the issue of simply reordering the decision 
> variables and constraints. Performance varies significantly with other 
> seemingly minor model reformulations.
> 
> 
> Some people have suggested this might be because they hypothesize that 
> the disjunction constraints use Big M which has weak linear relaxations.
> 
> 
> But I don't think it uses Big M. My understanding is that the way 
> disjuncts work is that each disjunct is added to the local search 
> problem which seems like a totally different approach than using Big 
> M, and also didn't see anything about Big M in my brief review of the 
> disjunct constraint source code.
> 
> 
> My questions are:
> 
>   * Does disjunction constraint handler rely in Big-M reformulation?
>   * Are there any particular search control options which are
>     particularly well (or poorly) suited for disjunction constraints?
> 
> 
> Thanks,
> 
>      Rich Levinson
> 
>      NASA Ames Research Center.
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
> 

-- 
______________________________
Benjamin Müller
Zuse Institute Berlin
Takustr. 7, 14195 Berlin
benjamin.mueller at zib.de
+49 30 841 85-195