topic Re: proc optmodel - how to convert a conditional constraint into linear to be solved with milp in Mathematical Optimization, Discrete-Event Simulation, and OR

proc optmodel - how to convert a conditional constraint into linear to be solved with milp

acanaveras — Mon, 12 Nov 2018 20:34:58 GMT

Hi,

I have an assignment problem that I want to solve with milp. I use a two by two binary matrix as the variable to optimize.

My problem is that I need to add a constraint by which the sum of the rows is either 1 or bigger than 5. See the code below.

How can I convert the non linear constraint into linear ?

Thanks

proc optmodel presolver=none;

set <str> BG; /*Origins */

set <str> SITES init {}; /*Destinations*/

set <str> SITESREDUCED1 init {}; /*Destinations*/

num distance {BG,SITES}; /*Read Distance between Origins and Destinations */

read data SITES into SITES=[SITE] ;

read data Customers into BG=[SITE];

read data SITESREDUCED1 into SITESREDUCED1=[SITE];

read data SFDISTANCES

into BG=[SITE]

{j in SITES} < distance[SITE,j]=col(j) >; /* For all the origins read the distances to the destinations */

/* Declare Variables */

for {i in BG, j in SITES} distance[i,j] = round(distance[i,j]);

/*var Assign {BG, SITES} binary init 1; */

var Assign {BG, SITES} binary init 1;

num distancias {BG};

min DistanceS= SUM {i in BG, j in SITES} distance[i,j] * Assign [i,j]/SUM {i in BG, j in SITES} distance[i,j] ;

/* Per each column the node is assigned only two times (for itself and with another node) skipping the first column where the node is assigned once*/

con assign_rest_ll {j in SITESREDUCED1}:

sum {i in BG} Assign[i,j] = 2;

/*Lower Matrix is Zero*/

con simetry {i in BG, j in SITES}:

if i>j then Assign[i,j] = 0;

　/* Diagonal is 1*/

con assing_diag {i in BG}:

Assign[i,i] = 1;

/* This is the non linear constrain that I need to convert to linear */

con row_assignment_lb{i in BG}:

if sum {j in SITES} Assign [i,j] <=1 or >=5;

solve with milp / primalin allcuts=AGGRESSIVE RELOBJGAP=0.1 ;

Re: proc optmodel - how to convert a conditional constraint into linear to be solved with milp

RobPratt — Wed, 14 Nov 2018 15:04:08 GMT

Try this:

var IsSmall {BG} binary;
con row_assignment_lb1{i in BG}:
   sum {j in SITES} Assign [i,j] >= 0 * IsSmall[i] + 5 * (1 - IsSmall[i]);
con row_assignment_lb2{i in BG}:
   sum {j in SITES} Assign [i,j] <= 1 * IsSmall[i] + card(SITES) * (1 - IsSmall[i]);

If IsSmall[i] = 1, then the sum will be in [0,1]. If IsSmall[i] = 0, then the sum will be in [5,card(SITES)].

You also should do this:

con simetry {i in BG, j in SITES: i > j}:
   Assign[i,j] = 0;

Or use the FIX statement:

for {i in BG, j in SITES: i > j}
   fix Assign[i,j] = 0;

Or avoid those variables altogether as in this documentation example.

Re: proc optmodel - how to convert a conditional constraint into linear to be solved with milp

acanaveras — Wed, 14 Nov 2018 14:49:13 GMT

Rob,

Thanks for your reply.. but I need to apply the same concept for a 3 dimension matrix

Can you help me with this? This are the heuristics I want to apply:

- I need to cluster a set of points by proximity

- Objective - I can do this by minimizing the sum of distances from all origins to all destinations for all the clusters created

- Constraint - Clusters must have more than x points (in example is 5)

QUESTION: How can I specify that if an origin is in one group, then it cannot be in other groups. I have implemented this, (as you recommended, but the problem is that the limits are applied across the clusters.. I want to specify that if an origin is in one group... it cannot be in another group for any of the destinations. See bellow an attempt to use your recommendation... problem is that the limits 0-1 AND 4 TO card apply for the origin across all the groups.

proc optmodel;
set DEST = 1..&num_vars;
set GROUPS = 1..&num_groups;
set ORIG;
num dist {ORIG, DEST};
read data SFDISTANCES into ORIG=[_N_] {j in DEST} <dist[_N_,j]=col('x'||j)>;

/* Assign[i,g] = 1 if observation i assigned to group g, 0 otherwise */
var Assign {ORIG, DEST, GROUPS} binary;

Var IsOriginGroup{ ORIG,GROUPS} binary init 0;

con orig_assignment_lb1 {i in ORIG}:
sum {j in DEST, g in GROUPS} Assign [i,j,g] >= 0 * and {g in GROUPS} IsOriginGroup[i,g] + 4 * (1 - IsOriginGroup[i,g]);

con orig_assignment_lb2 {i in ORIG}:
sum {j in DEST, g in GROUPS} Assign [i,j,g] >= 1 * IsOriginGroup[i,g] + card(DEST) * (1 - IsOriginGroup[i,g]);

con Simetry {i in ORIG, j in DEST, g in GROUPS}:
Assign[i,j,g]=Assign[j,i,g];

con ASimetry {i in ORIG, g in GROUPS}:
Assign[i,i,g]= 0;

con NearlyEqual {g in GROUPS}:
sum {i in ORIG, j in DEST} Assign[i,j,g] >=4 ;

impvar GroupSum {g in GROUPS} = sum {i in ORIG,j in DEST} dist [i,j] * Assign[i,j,g];

min distance = sum {g in GROUPS} GroupSum[g];

solve with milp / primalin allcuts=AGGRESSIVE RELOBJGAP=0.1 maxtime=50 ;

create data Allocated_Demand from
[ORIG DEST GROUPS]={i in ORIG, j in DEST, G IN GROUPS: Assign[i,j,g] = 1};
print Assign;
print GroupSum;

Re: proc optmodel - how to convert a conditional constraint into linear to be solved with milp

RobPratt — Wed, 14 Nov 2018 22:28:16 GMT

I don't quite follow the logical implication you are trying to enforce. If you can express it in the form "if this variable = 1 then that variable = 0," I'll tell you how to enforce it with a linear constraint.

in the mean time, there are two issues with your latest code. First, you cannot use the AND operator here:

con orig_assignment_lb1 {i in ORIG}:
sum {j in DEST, g in GROUPS} Assign [i,j,g] >= 0 * and {g in GROUPS} IsOriginGroup[i,g] + 4 * (1 - IsOriginGroup[i,g]);

Second, it is unsafe to compare to 1 here because the binary variables are unlikely to be exactly 0 or 1:

create data Allocated_Demand from
[ORIG DEST GROUPS]={i in ORIG, j in DEST, G IN GROUPS: Assign[i,j,g] = 1};

It is safer to check Assign[i,j,g] > 0.5 instead.