turn on suggestions

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

Showing results for

Find a Community

Topic Options

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

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-14-2017 08:45 AM

Hi,

We trying to solve the next optimization problem?

We have:

- Pij, i=1÷3, j=1÷30, Pij are positive
- Bi, i=1÷3, integer positive

The searching result is matrix of 3 x 30 of binary values Xij with next conditions:

Constraints:

- For each j =1÷30, Sum (by index of i=1÷3)Xij=1
- For each i =1÷3, Sum by index of (j=1÷3o)Xij≤Bi

Objective: Optimize:

- Maximize (Sum (by index of i=1÷3) Sum (by index of j=1÷30) Pij *Xij)

Is it possible to solve the problem by the lpsolve or milpsolve subroutine?

Is there another predefined subroutine in SAS/IML which can be used to solve this problem? We haven’t the SAS/OR.

Thank you in advance,

Boriana

Accepted Solutions

Solution

03-14-2017
11:12 AM

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Boriana

03-14-2017 10:17 AM

The key to this problem is understanding that the variables in your program need to be expressed as vectors, even though you are thinking of them as matrices,

Let's use a smaller matrix as an example. Instead of 3x30, consider a 3x4 matrix of probabilities called P. Then the binary solution vector X contains nrow(P)*ncol(P) elements. To make X into a vector, string out the elements of X rowwise, so that the first row comes first, then the second, then the third.

There are two linear constraints, the row constraints and the column constraints. The row constraints say that the sum of the i_th row of X is less than a specified b_i. The column constraints say that there is only one 1 in each column.

The following program solves a 3x4 example. I don't have time to explain it all, so study the MILP blog post and carefully study how I constructed the constraint matrices for rows and columns. If I wrote the program well and didn't make any errors, you should only need to input your probability matrix for P and specify the values of the B1 vector.

At the end of the program, the solution vector is reshaped into a matrix, for easy interpretation.

```
proc iml;
/* Probability matrix */
P = {0.5 0.5 0 0,
0 0.5 0.5 0,
0.5 0 0 0.5};
/* The binary solution vector X has nrow(P)*ncol(P) elements.
There are nrow(P) constraints on the row sums.
There are ncol(P) constraints on the column sums. */
/* information about variables */
colType = j(nrow(P)*ncol(P), 1, 'B'); /* binary */
/* objective function */
c = shape(P, 1); /* reshape into vector for objective function c*x */
/* linear constraints */
S = j(1, ncol(P), 1);
A1 = I(nrow(P)) @ S; /* constraint that sum across row <= B[i] */
print A1;
A2 = j(1,nrow(P),1) @ I(ncol(P)); /* constraint that sum of rows is 1 */
print A2;
A = A1 // A2; /* both constraints */
b1 = {2, 3, 2}; /* RHS of constraint for A1 */
b2 = j(ncol(P), 1, 1); /* RHS of constraint for A2 */
b = b1 // b2;
/* specify symbols for constraints:
'L' for less than or equal
'E' for equal
'G' for greater than or equal */
LEG1 = j(nrow(P),1, "L"); /* constraints for A1 */
LEG2 = j(ncol(P),1,"E"); /* constraints for A2 */
LEG = LEG1 // LEG2;
/* control vector for optimization */
ctrl = {-1, /* maximize objective */
1}; /* print level */
CALL MILPSOLVE(rc, objVal, result, relgap, /* output variables */
c, A, b, /* objective and linear constraints */
ctrl, /* control vector */
coltype, LEG);
X = shape(result, nrow(P), ncol(P));
print rc objVal, X;
```

All Replies

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Boriana

03-14-2017 09:37 AM

What you want is probably the MILPSOLVE (Mixed Integer Linear Program) subroutine well described in this article:

http://blogs.sas.com/content/iml/2017/01/18/milp-sas.html

Documentation:

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to draycut

03-14-2017 09:47 AM

I tried to do this with next construction

**proc** **iml**;

object = { **7** **19** **30**};

coef = { **0.0756** **0.0782** **0.0241**,

**0.2657** **0.1985** **0.1728**,

**0.1269** **0.1101** **0.0609**,

**0.3941** **0.5391** **0.6155**,

**0.2516** **0.1239** **0.1977**,

**0.1269** **0.1405** **0.0609**,

**0.4798** **0.3912** **0.3524**,

**0.2262** **0.2216** **0.2696**,

**0.3540** **0.1645** **0.2696**,

**0.0367** **0.0728** **0.0808**,

**0.7796** **0.6506** **0.7071**,

**0.7618** **0.3593** **0.3524**,

**0.4556** **0.2055** **0.1863**,

**0.7796** **0.6242** **0.5432**,

**0.7870** **0.4469** **0.4759**,

**0.0298** **0.0498** **0.0241**,

**0.0137** **0.0498** **0.0241**,

**0.5738** **0.2264** **0.1224**,

**0.8033** **0.7063** **0.5289**,

**0.0367** **0.0970** **0.0474**

};

b ={ **1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**,

**1**};

rowsense = {L,L};

cntl = -**1**;

call milpsolve(rc,objv,x,relgap,object,coef,b,cntl,,rowsense);

print objv, x, relgap;

**quit**;

But it doesn't work. What I should change?

It is written that the output is vector. I want to 3 x 30 dimension matrix.

Solution

03-14-2017
11:12 AM

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Boriana

03-14-2017 10:17 AM

The key to this problem is understanding that the variables in your program need to be expressed as vectors, even though you are thinking of them as matrices,

Let's use a smaller matrix as an example. Instead of 3x30, consider a 3x4 matrix of probabilities called P. Then the binary solution vector X contains nrow(P)*ncol(P) elements. To make X into a vector, string out the elements of X rowwise, so that the first row comes first, then the second, then the third.

There are two linear constraints, the row constraints and the column constraints. The row constraints say that the sum of the i_th row of X is less than a specified b_i. The column constraints say that there is only one 1 in each column.

The following program solves a 3x4 example. I don't have time to explain it all, so study the MILP blog post and carefully study how I constructed the constraint matrices for rows and columns. If I wrote the program well and didn't make any errors, you should only need to input your probability matrix for P and specify the values of the B1 vector.

At the end of the program, the solution vector is reshaped into a matrix, for easy interpretation.

```
proc iml;
/* Probability matrix */
P = {0.5 0.5 0 0,
0 0.5 0.5 0,
0.5 0 0 0.5};
/* The binary solution vector X has nrow(P)*ncol(P) elements.
There are nrow(P) constraints on the row sums.
There are ncol(P) constraints on the column sums. */
/* information about variables */
colType = j(nrow(P)*ncol(P), 1, 'B'); /* binary */
/* objective function */
c = shape(P, 1); /* reshape into vector for objective function c*x */
/* linear constraints */
S = j(1, ncol(P), 1);
A1 = I(nrow(P)) @ S; /* constraint that sum across row <= B[i] */
print A1;
A2 = j(1,nrow(P),1) @ I(ncol(P)); /* constraint that sum of rows is 1 */
print A2;
A = A1 // A2; /* both constraints */
b1 = {2, 3, 2}; /* RHS of constraint for A1 */
b2 = j(ncol(P), 1, 1); /* RHS of constraint for A2 */
b = b1 // b2;
/* specify symbols for constraints:
'L' for less than or equal
'E' for equal
'G' for greater than or equal */
LEG1 = j(nrow(P),1, "L"); /* constraints for A1 */
LEG2 = j(ncol(P),1,"E"); /* constraints for A2 */
LEG = LEG1 // LEG2;
/* control vector for optimization */
ctrl = {-1, /* maximize objective */
1}; /* print level */
CALL MILPSOLVE(rc, objVal, result, relgap, /* output variables */
c, A, b, /* objective and linear constraints */
ctrl, /* control vector */
coltype, LEG);
X = shape(result, nrow(P), ncol(P));
print rc objVal, X;
```

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Rick_SAS

03-16-2017 11:12 AM

Thank you for the solution.

It is worked!!!

We have to applie for the large number of customers.

When I check the same with this data I receive the next:

ERROR: The number of variables or constraints exceeds 500 limit, which will require a SAS/OR product license.

ERROR: Either the SAS/OR product with which MILPSOLVE is associated is not licensed for your system or the product license has expired. Please contact your SAS installation representative.

Is it possible to extend this size of constraints by setting for SAS/IML?

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Boriana

03-16-2017 11:35 AM

The documentation for the MILSOLVE call says "For complete functionality the SAS/OR product must also be installed, otherwise the maximum number of variables and maximum number of constraints is restricted to 500."

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Rick_SAS

03-16-2017 11:38 AM

Thank you again.