his problem is a type of a vehicle routing problem. city 1 is depot.
range city=(1..5);
dvar int xcitycity in 0..1; // if vehicle traverse from city i to city j equal to 1 otherwise 0
dvar int+ ucitycity; // total demanded product from city i to city j
these are the subset constraints which i couldn't write in closed format.
(u[1][2]!=0) => x[1][2]==1
x[1][3]+x[3][2]==2
x[1][4]+x[4][2]==2
x[1][5]+x[5][2]==2
x[1][3]+x[3][4]+x[4][2]==3
x[1][3]+x[3][5]+x[5][2]==3
x[1][4]+x[4][3]+x[3][2]==3
x[1][4]+x[4][5]+x[5][2]==3
x[1][5]+x[5][3]+x[3][2]==3
x[1][5]+x[5][4]+x[4][2]==3
x[1][3]+x[3][4]+x[4][5]+x[5][2]==4
x[1][3]+x[3][5]+x[5][4]+x[4][2]==4
x[1][4]+x[4][3]+x[3][5]+x[5][2]==4
x[1][4]+x[4][5]+x[5][3]+x[3][2]==4
x[1][5]+x[5][3]+x[3][4]+x[4][2]==4
x[1][5]+x[5][4]+x[4][3]+x[3][2]==4;
these constraints ensures that if there are some product going from city 1 to city 2 then a vehicle delivers this product directly by traversing 1 to 2; or traversing some intermediate cities between 1 and 2 like "1342". and also i wanna construct these constraints for each ucitycity variable.
any idea how can i do this?
Topic
This topic has been locked.
6 replies
Latest Post
 20130115T12:06:37Z by SystemAdmin
ACCEPTED ANSWER
Pinned topic Writing constraints for subsets of a set.
20130106T11:15:47Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20130115T12:06:37Z at 20130115T12:06:37Z by SystemAdmin

ACCEPTED ANSWER
Re: Writing constraints for subsets of a set.
20130106T18:34:54Z in response to SystemAdminIn any programming language you can easily iterate over the set of all subsets of a ground set S by using bitvectors. Let n denote the cardinality of S and for sake of simplicity assume that n is smaller than 32. Implement a loop that has i as loop variable and runs from 0 to 2^n1. In each iteration the binary representation i represents a subset of S as follows: If bit number j is set in the binary representation of i then element number j is contained in the subset.
Example:
Ground set S = { a, b, c } Iteration 1: i = 0, binary representation: 00000, subset = { } Iteration 2: i = 1, binary representation: 00001, subset = { a } Iteration 3: i = 2, binary representation: 00010, subset = { b } Iteration 4: i = 3, binary representation: 00011, subset = { a, b } Iteration 5: i = 4, binary representation: 00100, subset = { c } ... Iteration 8: i = 7, binary representation: 00111, subset = { a, b, c }
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.
Here is a very simple OPL model that implements this sort of enumeration (note that the model is infeasible):
{string } S = { "a", "b", "c" }; // The ground set. range I = 0 .. ftoi(2^card(S))  1; range J = 0 .. card(S)  1; // Index set for the ground set. dvar boolean x[J]; // Boolean variables, one for each element in the ground set. subject to { // For all subsets of S forall (i in I) { // Sum of all variables for this subset must be 1 (model is infeasible). sum (j in J: (i % ftoi(2^(j+1))) div ftoi(2^j) == 1) x[j] == 1; } }

ACCEPTED ANSWER
Re: Writing constraints for subsets of a set.
20130107T11:17:46Z in response to SystemAdminsir thanks for your help. unfortunately i am not familiar with bitvectors :( 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?
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?


ACCEPTED ANSWER
Re: Writing constraints for subsets of a set.
20130107T11:55:59Z in response to SystemAdminI just found this old OPL tutorial. 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?
The idea behind the bit vector approach is as follows:

A bit vector is just a vector (or array) of bits, for example
[1,0,0,1]
 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.
 If you now have a ground set S of cardinality c then any subset of this set can be represented by a bit array of length c as follows:
2. A bit array of length c represents a subset as follows: If the value at position k in the array is 1 then element number k 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. A bit vector is just a vector (or array) of bits, for example <pre class="java dw" dataeditorlang="java" datapbcklang="java" dir="ltr">[1,0,0,1] </pre>
 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.
 If you now have a ground set S of cardinality c then any subset of this set can be represented by a bit array of length c as follows:
2. A bit array of length c represents a subset as follows: If the value at position k in the array is 1 then element number k 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.Updated on 20140324T22:43:11Z at 20140324T22:43:11Z by ironman
ACCEPTED ANSWER
Re: Writing constraints for subsets of a set.
20130107T12:51:02Z in response to SystemAdminthanks very much. I'll check the tutorial.
ACCEPTED ANSWER
Re: Writing constraints for subsets of a set.
20130111T15:15:47Z in response to SystemAdmintutorial 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:
x[1]=1 
x[2]=1 
x[3]=1 
x[4]=1 
how can i write these logical constraints by using forall?
forall(i in 1..4)x[i]==1 doesn't works...
ACCEPTED ANSWER
Re: Writing constraints for subsets of a set.
20130115T12:06:37Z in response to SystemAdminSorry, I don't know a way of doing that. Maybe the people on the OPL Forum can give a better answer.
If all the x variables are boolean then you could write
sum (i in 1..4) x[i] >= 1
For boolean variables this is the same as
x[1] == 1  x[2] == 1  x[3] == 1  x[4] == 1
(both constraints are satisfied as soon as any of the x values is 1).Updated on 20140324T22:42:05Z at 20140324T22:42:05Z by ironman



A bit vector is just a vector (or array) of bits, for example