topic Re: Problem in formulating constraint in Mathematical Optimization, Discrete-Event Simulation, and OR

Problem in formulating constraint

abhik_giri — Wed, 12 Mar 2014 12:00:41 GMT

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.

Re: Problem in formulating constraint

Haikuo — Wed, 12 Mar 2014 13:42:26 GMT

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

Re: Problem in formulating constraint

abhik_giri — Wed, 12 Mar 2014 13:47:44 GMT

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.

Re: Problem in formulating constraint

RobPratt — Wed, 03 Jan 2018 21:17:24 GMT

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[j] = 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;

Re: Problem in formulating constraint

abhik_giri — Thu, 13 Mar 2014 09:12:36 GMT

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

Re: Problem in formulating constraint

RobPratt — Thu, 13 Mar 2014 15:03:19 GMT

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.)

Re: Problem in formulating constraint

abhik_giri — Fri, 17 Apr 2015 18:08:05 GMT

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.

Re: Problem in formulating constraint

LeoLopes — Fri, 17 Apr 2015 18:22:01 GMT

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;

Re: Problem in formulating constraint

abhik_giri — Fri, 17 Apr 2015 18:26:15 GMT

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'

Re: Problem in formulating constraint

LeoLopes — Fri, 17 Apr 2015 18:36:45 GMT

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;

Re: Problem in formulating constraint

RobPratt — Fri, 17 Apr 2015 19:55:57 GMT

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.

Re: Problem in formulating constraint

Ksharp — Sat, 18 Apr 2015 07:34:07 GMT

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

Re: Problem in formulating constraint

baralamit0 — Wed, 03 Jan 2018 11:13:22 GMT

Remember Permutation/Combination Chapter from +2 days ?

If {for i = 1 to 5} sum x(i) = 3 and x(i)'s are binary then there will be three 1's and two 0's.

Let me reframe the problem in the following way -

In how many ways three 1's and two 0's can be arranged in permutation so that 1's always come together ? We consider three 1's as a single unit(let's say =3) and proceed with the permutation. So it would be 3! total. [For the time being, lets forget as two 0's are actually the same, so total number of permutation would be 3!/2!. Actually I could not find out this option in SAS. Please update me if anybody gets it]

proc plan;
factors Block=6 ordered B=3 of 3 perm;
ods output Plan=results;
run;

This will produce the following output-

Block B1 B2 B3
1 1 2 3
2 1 3 2
3 2 1 3
4 2 3 1
5 3 1 2
6 3 2 1

Once you replace the value of B1/B2/B3 as follows you will find few duplication in blocks.

data results(keep=Digit);
set results;
format Digit1 Digit2 Digit3 $5.;
if B1 in (1,2) then Digit1='0'; else Digit1 = '1-1-1';
if B2 in (1,2) then Digit2='0'; else Digit2 = '1-1-1';
if B3 in (1,2) then Digit3='0'; else Digit3 = '1-1-1';
Digit = CATX ("-", OF  Digit1-Digit3);
run;

Results -

Digit
0-0-1-1-1
0-1-1-1-0
0-0-1-1-1
0-1-1-1-0
1-1-1-0-0
1-1-1-0-0

Dedupe it -

proc sort data=results nodupkey; by Digit; run;

And you get the desired results-

Digit
0-0-1-1-1
0-1-1-1-0
1-1-1-0-0

Use substr function to create 5 column from the Digit column.

Re: Problem in formulating constraint

RobPratt — Wed, 03 Jan 2018 23:02:05 GMT

Here's a way to do it with the CLP solver in PROC OPTMODEL:

proc optmodel;
   num n = 5;
   var x {1..n} binary;
   con ChooseThree:
      sum {j in 1..n} x[j] = 3;
   /* 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;

   solve with clp / findallsolns;
   print {s in 1.._NSOL_, j in 1..n} x[j].sol[s];
quit;

SAS Output

x.SOL
	1	2	3	4	5
1	0	0	1	1	1
2	0	1	1	1	0
3	1	1	1	0	0

Re: Problem in formulating constraint

lipury — Wed, 03 Jan 2018 22:57:57 GMT

I've attached PROC OPTMODEL code that uses the REIFY and GCC constraints with the CLP solver.

Re: Problem in formulating constraint

baralamit0 — Fri, 05 Jan 2018 22:28:22 GMT

PROC OPTMODEL comes with SAS-OR License. Which is bit costly and sometimes is not available.

Whereas Proc PLAN comes with the BASE SAS only.