6110https://www.ibm.com/developerworks/community/forums/atom/replies?topicUuid=77777777-0000-0000-0000-000014925779Writing constraints for subsets of a set. Replies2013-01-15T12:06:37.574ZIBM Connections - Discussion Forumurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014929016Re: Writing constraints for subsets of a set.2013-01-15T12:06:37.574ZSystemAdmin110000D4XKactive2013-01-15T12:06:37.574Z2014-03-24T22:42:05.407Ziron-man270000AK5Mactive
Sorry, I don't know a way of doing that. Maybe the people on the <a class="jive-link-external" href="http://www.ibm.com/developerworks/forums/forum.jspa?forumID=2053">OPL Forum</a> can give a better answer. <br />
If all the <i>x</i> variables are boolean then you could write <br />
<pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">
sum (i in 1..4) x[i] >= 1
</pre>
<br />
For boolean variables this is the same as <br />
<pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">
x[1] == 1 || x[2] == 1 || x[3] == 1 || x[4] == 1
</pre>
<br />
(both constraints are satisfied as soon as any of the <i>x</i> values is 1).
none, view_forum, view_categoryurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014928085Re: Writing constraints for subsets of a set.2013-01-11T15:15:47.935ZSystemAdmin110000D4XKactive2013-01-11T15:15:47.935Z
tutorial was really helpful. i get the idea :) i wanna ask you something else about logical constraints. is there a way using "or-||" between each constraint which are constructed by forall stament. for example:<br />
x[1]=1 ||<br />
x[2]=1 ||<br />
x[3]=1 ||<br />
x[4]=1 ||<br />
<br />
how can i write these logical constraints by using forall? <br />
<br />
forall(i in 1..4)x[i]==1|| doesn't works...
none, view_forum, view_categoryurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014925952Re: Writing constraints for subsets of a set.2013-01-07T12:51:02.466ZSystemAdmin110000D4XKactive2013-01-07T12:51:02.466Z
thanks very much. I'll check the tutorial.
none, view_forum, view_categoryurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014925926Re: Writing constraints for subsets of a set.2013-01-07T11:55:59.231ZSystemAdmin110000D4XKactive2013-01-07T11:55:59.231Z2014-03-24T22:43:11.843Ziron-man270000AK5Mactive
I just found this <a class="jive-link-external" href="http://www.kt.agh.edu.pl/~cholda/wp-content/uploads/2012/09/opl_tutorial.pdf">old OPL tutorial</a>. On page 9 in model lines 13 through 16 it defines the set of all subsets of some ground set. It uses the very same technique that I proposed. The model has more or less detailed explanations in this tutorial. Could you check and see if that helps you understanding things better? <br />
<br />
The idea behind the bit vector approach is as follows: <br />
<ul class="jive-dash">
<li>
A bit vector is just a vector (or array) of bits, for example
<pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">
[1,0,0,1]
</pre>
</li>
<li>
A (short) bit vector can be represented as the binary representation of a natural number. For example, the above bit vector can be viewed as binary number 1001 which is the decimal number 9.
</li>
<li>
If you now have a ground set <i>S</i> of cardinality <i>c</i> then any subset of this set can be represented by a bit array of length <i>c</i> as follows:
</li>
</ul>1. The elements in <i>S</i> are numbered 0 through <i>c</i> - 1 (the ordering is arbitrary but must be fixed). <br />
2. A bit array of length <i>c</i> represents a subset as follows: If the value at position <i>k</i> in the array is 1 then element number <i>k</i> is contained in this subset, otherwise not. So the bit array tells you which elements are contained in the subset and which are not. The only thing you need to do is to test whether an element in the bit array is set or not.
none, view_forum, view_categoryurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014925913Re: Writing constraints for subsets of a set.2013-01-07T11:17:46.645ZSystemAdmin110000D4XKactive2013-01-07T11:17:46.645Z
sir thanks for your help. unfortunately i am not familiar with bit-vectors :( i couldn't get the the idea to use it in my problem. do you have any more suggestion or can you make more explanation?<br />
PS: do you have any other opl code which iterate over subsets or any other source for bit vector which i can look up and learn?
none, view_forum, view_categoryurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014925821Re: Writing constraints for subsets of a set.2013-01-06T18:34:54.643ZSystemAdmin110000D4XKactive2013-01-06T18:34:54.643Z
In any programming language you can easily iterate over the set of all subsets of a ground set <i>S</i> by using bit-vectors. Let <i>n</i> denote the cardinality of <i>S</i> and for sake of simplicity assume that <i>n</i> is smaller than 32. Implement a loop that has <i>i</i> as loop variable and runs from 0 to 2^n-1. In each iteration the binary representation <i>i</i> represents a subset of <i>S</i> as follows: If bit number <i>j</i> is set in the binary representation of <i>i</i> then element number <i>j</i> is contained in the subset.<br />
Example:<br />
<pre class="jive-pre">
<code class="jive-code jive-java">
Ground set S = <span style="color: navy">
{</span> a, b, c <span style="color: navy">
}</span> Iteration 1: i = 0, binary representation: 00000, subset = <span style="color: navy">
{</span><span style="color: navy">
}</span> Iteration 2: i = 1, binary representation: 00001, subset = <span style="color: navy">
{</span> a <span style="color: navy">
}</span> Iteration 3: i = 2, binary representation: 00010, subset = <span style="color: navy">
{</span> b <span style="color: navy">
}</span> Iteration 4: i = 3, binary representation: 00011, subset = <span style="color: navy">
{</span> a, b <span style="color: navy">
}</span> Iteration 5: i = 4, binary representation: 00100, subset = <span style="color: navy">
{</span> c <span style="color: navy">
}</span> ... Iteration 8: i = 7, binary representation: 00111, subset = <span style="color: navy">
{</span> a, b, c <span style="color: navy">
}</span></code>
</pre>
<br />
Testing whether a bit is set is usually done using the bitwise and operator. If your programming language does not support this operator then you can implement a test using integer division and modulus.<br />
Here is a very simple OPL model that implements this sort of enumeration (note that the model is infeasible):<br />
<pre class="jive-pre">
<code class="jive-code jive-java">
<span style="color: navy">
{</span>string<span style="color: navy">
}</span> S = <span style="color: navy">
{</span> <span style="color: red">
"a"</span>, <span style="color: red">
"b"</span>, <span style="color: red">
"c"</span> <span style="color: navy">
}</span>; <span style="color: darkgreen">
// The ground set.</span> range I = 0 .. ftoi(2^card(S)) - 1; range J = 0 .. card(S) - 1; <span style="color: darkgreen">
// Index set for the ground set.</span> dvar <span style="color: navy">
<b>
boolean</b></span> x[J]; <span style="color: darkgreen">
// Boolean variables, one for each element in the ground set.</span> subject to <span style="color: navy">
{</span> <span style="color: darkgreen">
// For all subsets of S</span> forall (i in I) <span style="color: navy">
{</span> <span style="color: darkgreen">
// Sum of all variables for this subset must be 1 (model is infeasible).</span> sum (j in J: (i % ftoi(2^(j+1))) div ftoi(2^j) == 1) x[j] == 1; <span style="color: navy">
}</span> <span style="color: navy">
}</span></code>
</pre>
none, view_forum, view_category