BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.
Boriana
Obsidian | Level 7

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 positiveConstraints:

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

  • 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 there another predefined subroutine in SAS/IML which can be used to solve this problem? We haven’t the SAS/OR.

The suggested solution from Rick_SAS was to convert this to linear optimization programing.

You can see here the solution.

Linear optimization in SAS/IML

In real situation we for j index we have 30000, not only 30. The matrix became too large. It is not possible to solve it by SAS/IML. The limitation there is 200 constraints, which is too few.
We haven’t SAS/OR yet.
My question concerns the limitation of constraints and the size of matrix in SAS/OR? Is it possible to work with matrix size of 90000 x 30000. How many constraints there can have?
Is it possible to solve this task with another procedure, not with linear programing in SAS/OR?

Thanks,

Boriana

1 ACCEPTED SOLUTION

Accepted Solutions
RobPratt
SAS Super FREQ

You can formulate and solve the problem with PROC OPTMODEL in SAS/OR:

 

proc optmodel;
   set ISET = 1..3;
   set JSET = 1..30000;
   num p {ISET, JSET} = rand('UNIFORM');
   num b {ISET} = card(JSET)*rand('UNIFORM');
   var X {ISET, JSET} binary;
   max Z = sum {i in ISET, j in JSET} p[i,j] * X[i,j];
   con Con1 {j in JSET}:
      sum {i in ISET} X[i,j] = 1;
   con Con2 {i in ISET}:
      sum {j in JSET} X[i,j] <= b[i];

   /* call (default) MILP solver */
   solve;

   /* call LP solver with (default) dual simplex algorithm */
   solve with lp relaxint;

   /* call LP solver with network simplex algorithm */
   solve with lp relaxint / algorithm=ns;
quit;

Because the problem has a pure network structure, the third solve performs the best, solving in less than a second.  Due to total unimodularity of the resulting constraint matrix, you can relax the integrality of x and an optimal solution will automatically take integer values.

 

You can also model the problem in terms of a bipartite directed network, where the left side consists of the i nodes, each with a supply of at most b[i], and the right side consists of the j nodes, each with a demand of exactly 1.  The (binary) variable x[i,j] represents the flow from node i to node j.  You can negate the link weights (because you want to maximize) and call the minimum-cost network flow algorithm either via the network solver in PROC OPTMODEL or via PROC OPTNET, also in SAS/OR.

View solution in original post

4 REPLIES 4
RobPratt
SAS Super FREQ

You can formulate and solve the problem with PROC OPTMODEL in SAS/OR:

 

proc optmodel;
   set ISET = 1..3;
   set JSET = 1..30000;
   num p {ISET, JSET} = rand('UNIFORM');
   num b {ISET} = card(JSET)*rand('UNIFORM');
   var X {ISET, JSET} binary;
   max Z = sum {i in ISET, j in JSET} p[i,j] * X[i,j];
   con Con1 {j in JSET}:
      sum {i in ISET} X[i,j] = 1;
   con Con2 {i in ISET}:
      sum {j in JSET} X[i,j] <= b[i];

   /* call (default) MILP solver */
   solve;

   /* call LP solver with (default) dual simplex algorithm */
   solve with lp relaxint;

   /* call LP solver with network simplex algorithm */
   solve with lp relaxint / algorithm=ns;
quit;

Because the problem has a pure network structure, the third solve performs the best, solving in less than a second.  Due to total unimodularity of the resulting constraint matrix, you can relax the integrality of x and an optimal solution will automatically take integer values.

 

You can also model the problem in terms of a bipartite directed network, where the left side consists of the i nodes, each with a supply of at most b[i], and the right side consists of the j nodes, each with a demand of exactly 1.  The (binary) variable x[i,j] represents the flow from node i to node j.  You can negate the link weights (because you want to maximize) and call the minimum-cost network flow algorithm either via the network solver in PROC OPTMODEL or via PROC OPTNET, also in SAS/OR.

Boriana
Obsidian | Level 7

Do you know if there are any limitation of this procedure? For the number of constraints, for size of datasets? Does it depend from RAM of the computer?

RobPratt
SAS Super FREQ

There is a hard limit of 2^31 - 1 = 2,147,483,647 variables, constraints, or nonzero coefficients.  Other than that, the only limit depends on the amount of memory you have provided to SAS.

Ksharp
Super User

Or you could perform Genetic Algorithm in IML .

sas-innovate-2024.png

Join us for SAS Innovate April 16-19 at the Aria in Las Vegas. Bring the team and save big with our group pricing for a limited time only.

Pre-conference courses and tutorials are filling up fast and are always a sellout. Register today to reserve your seat.

 

Register now!

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.

Discussion stats
  • 4 replies
  • 1031 views
  • 3 likes
  • 3 in conversation