Linear optimisation problem, limitation problem

[Boriana]

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

[RobPratt · Accepted solution]

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]

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]

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]

Or you could perform Genetic Algorithm in IML .