[Scip] How to use OR clauses in constraints

[Navid Mohaghegh]

Hi Gregor,

Thank you very much for your reply.

Could you kindly let me know if SCIP can directly have an operator for OR? 

Below was just an example of many OR constraints that I have. So I like to know if SCIP can directly handle OR for me.

I like to avoid CNF approach (http://en.wikipedia.org/wiki/Conjunctive_normal_form) as much as possible.

Thank you,
Navid


On May 6, 2014, at 6:19 AM, Gregor Hendel <hendel at zib.de> wrote:

> 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
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140506/ee7a9269/attachment.html>