Operations Research topics: SAS/OR,
SAS Optimization, and SAS Simulation Studio

Linear optimisation problem, limitation problem

Accepted Solution Solved
Reply
Occasional Contributor
Posts: 6
Accepted Solution

Linear optimisation problem, limitation problem

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


Accepted Solutions
Solution
‎04-12-2017 03:50 AM
SAS Employee
Posts: 448

Re: Linear optimisation problem, limitation problem

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


All Replies
Solution
‎04-12-2017 03:50 AM
SAS Employee
Posts: 448

Re: Linear optimisation problem, limitation problem

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.

Occasional Contributor
Posts: 6

Re: Linear optimisation problem, limitation problem

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?

SAS Employee
Posts: 448

Re: Linear optimisation problem, limitation problem

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.

Super User
Posts: 9,775

Re: Linear optimisation problem, limitation problem

Or you could perform Genetic Algorithm in IML .

☑ This topic is solved.

Need further help from the community? Please ask a new question.

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