Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Options

- RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Posted 11-12-2018 03:34 PM
(1178 views)

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 ;

3 REPLIES 3

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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;

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

📢

**ANNOUNCEMENT**

The early bird rate has been extended! Register by March 18 for just $695 - $100 off the standard rate.

Check out the agenda and get ready for a jam-packed event featuring workshops, super demos, breakout sessions, roundtables, inspiring keynotes and incredible networking events.** **

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.