Operations Research topics: SAS/OR,
SAS Optimization, and SAS Simulation Studio

Problem in formulating constraint

Reply
Contributor
Posts: 35

Problem in formulating constraint

Hi, I have a binary variable x(b) where b ranges from 1 to 5.

Now I have a constraint which says that summation of x(b) over all b is either 0 or 3.

However all the x(b)'s with value 1 need to be together.

For example I can have the following sequences:

0 0 0 0 0

0 0 1 1 1

0 1 1 1 0

1 1 1 0 0

However I cannot have the following sequences.

1 0 1 0 1

0 1 1 0 1
Any help in formulating this constraint will be greatly appreciated.

Respected Advisor
Posts: 3,147

Re: Problem in formulating constraint

Not sure if this is what you want, but it seems to me more of a data manipulation question:

data have;

input b1-b5;

cards;

0 0 0 0 0

0 0 1 1 1

0 1 1 1 0

1 1 1 0 0

1 0 1 0 1

0 1 1 0 1

0 1 1 1 1

0 0 1 1 0

;

data want;

  set have;

  array b b:;

if (find(cats(of b(*)),'111') >0 and sum(of b(*)) =3) or sum(of b(*))=0;

run;

Haikuo

Contributor
Posts: 35

Re: Problem in formulating constraint

Thanks for the reply Haikuo. Sorry if I didn't make my question more clear previously: x(b) is the desired output (of the optimization model), it's not the input.

SAS Employee
Posts: 448

Re: Problem in formulating constraint

Here's a way to do it by using PROC OPTMODEL in SAS/OR:

proc optmodel;

   num n = 5;

   var x {1..n} binary;

   var y binary;

   con ZeroOrThree:

      sum {j in 1..n} x = 3*y;

   /* exclude (1,...,0,...,1) */

   con Consecutive {j1 in 1..n-2, j2 in j1+1..n-1, j3 in j2+1..n}:

      x[j1] + (1 - x[j2]) + x[j3] <= 2;

Contributor
Posts: 35

Re: Problem in formulating constraint

Rob, this looks to be a great solution when there is only one '0' in the middle with '1's on both sides of it. However I forgot to mention another possible case which needs to be excluded (by using the constraint). In this case, there are multiple '0's in the middle with '1's on both sides of it. Example: 1 0 0 1 1

SAS Employee
Posts: 448

Re: Problem in formulating constraint

For each triple (j1,j2,j3) where j1 < j2 < j3, the constraints I suggested exclude x[j1] = 1, x[j2] = 0, x[j3] = 1, even if j1, j2, and j3 are not consecutive.  Your example 1 0 0 1 1 is excluded by the constraint indexed by (j1,j2,j3) = (1,2,4).  (It is also excluded by a few other triples.)

Contributor
Posts: 35

Re: Problem in formulating constraint

I have a constraint of the following form:

x(i)/A-x(i')/B+slack(i,i')-surplus(i,i')=0 for all i,i' such that i=1 to 99, i=2 to 100 and i<i'

However, the set to which i and i' belong is a string, not a number so I can't write "i in 1..100".

Will DO loop be better for this? If yes, can you help me with the syntax?

I couldn't find syntax for "Constraint DO loop" in Google.

SAS Employee
Posts: 37

Re: Problem in formulating constraint

The simplest solution, if you will manipulate the strings as numbers, and you can be sure that they will always be numbers, is to create a set of numbers mapped to the set of strings, like this example:

proc optmodel;

   set S = / '1' '2' '3' /;

   set SNUM = setof{si in S} input(si,best12.);

   num n{si in SNUM} = si;

   put n

  • =;
  • quit;

    Contributor
    Posts: 35

    Re: Problem in formulating constraint

    Thanks a lot. But how do I code the constraint:

    x(i)/A-x(i')/B+slack(i,i')-surplus(i,i')=0 for all i,i' such that i=1 to 99, i=2 to 100 and i<i'

    SAS Employee
    Posts: 37

    Re: Problem in formulating constraint

    The simplest way to index them might be to define this set:

    num n ; /* you will initialize n from data */

    set PAIRS = {i in 1 .. n,j in i + 1 .. n};

    Then index your variables and constraints on PAIRS, e.g.:

    con ScaledDifference{<i,iPrime> in PAIRS}: X/A + Slack[i,iPrime] - Surplus[i,iPrime] = X[iPrime]/B;

    SAS Employee
    Posts: 448

    Re: Problem in formulating constraint

    Alternatively, you can keep the string indices if you define PAIRS as:

    set PAIRS = {i in ISET, iprime in ISET: i < iprime};


    where ISET is the common, string-valued index set for i and iprime.

    Super User
    Posts: 9,769

    Re: Problem in formulating constraint

    data _null_;
    array x[5];
    n=dim(x);
    k=-1;
    nsubs=2**n;
    do i=1 to nsubs;
    rc=graycode(k,of x
  • ); if prxmatch('/^0*1{2,}0*$|^0+$/',cats(of x
  • )) and sum(of x
  • ) in (0 3) then put  x
  • ; end; run;
  • Xia Keshan

    Ask a Question
    Discussion stats
    • 11 replies
    • 678 views
    • 0 likes
    • 5 in conversation