[Scip] How to use OR clauses in constraints

[Gregor Hendel]

Dear Navid,

On 05/05/2014 05:22 PM, Navid Mohaghegh wrote:
> Hi All,
>
> I am new to SCIP and trying to implement a very simple example:
>
> Imagine we have Q,R,S and T integer variables ranging from 0 to 10.
>
> Our objective is to maximize Q + R + S + T
> And our constraint is: (q <= 4r + 20 && q >=  2r) || ( (q > 4r + 20 && (t < r || s < r))  
The partial constraints are either redundant or never satisfied:

   q <= 4r +20, q <= 10, r >= 0 => always satisfied, hence redundant
   q  > 4r +20, q <= 10, r >= 0 => never feasible

So, the only remaining constraint states q >= 2r, and the optimum is 35 ;)

I would use binary variables to indicate the satisfaction of a
constraint: Consider your portion t < r || s < r.
Since we never use strict inequalities, we formulate this as
t <= r-1 || s < = r-1.
Let d_t, d_s be binary variables indicating if t or s violate their
constraint.
With the help of the binary variables, you can reformulate:
t <= r - 1 + M d_t,
s <= r - 1 + M d_s,
d_s + d_t <= 1,

which grants you the satisfaction of at least one of the two constraints.

In your example, M = 10 is a good choice. In order to prevent numerical
troubles, you want to be as modest as possible choosing the M.

Best regards,
Gregor

>
> I am trying to use ZIMPL, but can't find how can I use OR in my constraints.
>
> Could you help me with this either directly in SCIP or ZIMPL?
>
> Thank you,
> Navid
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip