Topic
  • 6 replies
  • Latest Post - ‏2013-01-15T12:06:37Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts

Pinned topic Writing constraints for subsets of a set.

‏2013-01-06T11:15:47Z |
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 "1-3-4-2". and also i wanna construct these constraints for each ucitycity variable.

any idea how can i do this?
Updated on 2013-01-15T12:06:37Z at 2013-01-15T12:06:37Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Writing constraints for subsets of a set.

    ‏2013-01-06T18:34:54Z  
    In any programming language you can easily iterate over the set of all subsets of a ground set S by using bit-vectors. 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^n-1. 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; 
    } 
    }
    
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Writing constraints for subsets of a set.

    ‏2013-01-07T11:17:46Z  
    In any programming language you can easily iterate over the set of all subsets of a ground set S by using bit-vectors. 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^n-1. 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:
    <pre class="jive-pre"> 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 } </pre>
    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):
    <pre class="jive-pre"> {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; } } </pre>
    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?
    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?
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Writing constraints for subsets of a set.

    ‏2013-01-07T11:55:59Z  
    I 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:
    1. The elements in S are numbered 0 through c - 1 (the ordering is arbitrary but must be fixed).
    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 2014-03-24T22:43:11Z at 2014-03-24T22:43:11Z by iron-man
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Writing constraints for subsets of a set.

    ‏2013-01-07T12:51:02Z  
    I 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 <pre class="java dw" data-editor-lang="java" data-pbcklang="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:
    1. The elements in S are numbered 0 through c - 1 (the ordering is arbitrary but must be fixed).
    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.
    thanks very much. I'll check the tutorial.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Writing constraints for subsets of a set.

    ‏2013-01-11T15:15:47Z  
    thanks very much. I'll check the tutorial.
    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:
    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...
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Writing constraints for subsets of a set.

    ‏2013-01-15T12:06:37Z  
    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:
    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...
    Sorry, 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 2014-03-24T22:42:05Z at 2014-03-24T22:42:05Z by iron-man