[Scip] How to use OR clauses in constraints

[Gregor Hendel]

Dear Navid

My apologies for the late reply. SCIP features a disjunction
<http://scip.zib.de/doc/html/cons__disjunction_8h.php> constraint
handler<http://scip.zib.de/doc/html/cons__disjunction_8h.php>. If you
build your model through the SCIP callable library,
you can group constraints together to form a disjunction by creating a
disjunction constraint and adding other constraints. Each feasible
solution satisfies at least one of the disjunction clauses.

Kind regards,
Gregor


On 05/06/2014 04:13 PM, Navid Mohaghegh wrote:
> 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
> <mailto: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 <mailto:Scip at zib.de>
>>> http://listserv.zib.de/mailman/listinfo/scip
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto: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/20140520/7fdd12e8/attachment.html>