1月 182017
 

This article shows how to solve mixed-integer linear programming (MILP) problems in SAS. In a mixed-integer problem, some of the variables in the problem are integer-valued whereas others are continuous. The objective function is a linear function of the variables and the variables can be subject to linear constraints.

Last month I discussed how to solve linear programming (LP) problems in SAS by using PROC OPTMODEL in SAS/OR or by using SAS/IML software. You can use these same tools to solve mixed-integer linear programming problems. The OPTMODEL procedure has the simpler syntax. The MILPSOLVE function in SAS/IML software provides similar functionality in a n interactive matrix language.

A mixed-integer linear programming problem example

The previous article solved a two-variable LP problem. If you constrain one of the variables to be an integer, you get a MILP problem, as follows:

  • Let x = {x1, x2} be the vector of unknown positive variables. The x1 variable is integer-valued; the x2 variable is continuous.
  • The objective function to maximize is 3*x1 + 5*x2. In vector form, the objective function is cTx where c = {3, 5}.
  • There are three linear constraints, which you can represent in matrix form. Define the 3 x 2 matrix of constraint coefficients A = {3  -2, 5  10, 4  2} and the right-hand-side vector b = {10, 56, 7}. Let LEG = {≤, ≤, ≥} be a "vector of symbols." ("LEG" is a mnemonic for "Less than," "Equal to," or "Greater than.") With this notation, the vector of constraints is written as Ax LEG b.
Feasible region for mixed-integer linear program problem  in SAS. The optimal solution is marked.

The graph shows the feasible region. The interior of the polygon satisfies the constraints. Because x1 must be an integer, the vertical stripes indicate the feasible values of the variables. The color of the stripes indicate the value of the objective function. The green star indicates the optimal solution, which is x = {5, 3.1}.

Mixed-integer linear programming by using the OPTMODEL procedure

The following statements show one way to formulate and solve the MILP problem by using the OPTMODEL procedure in SAS/OR software:

proc optmodel;
var x1 integer >= 0;           /* information about the variables */
var x2 >= 0;
max z = 3*x1 +  5*x2;         /* define the objective function */
con c1: 3*x1 + -2*x2 <= 10;   /* specify linear constraints */
con c2: 5*x1 + 10*x2 <= 56;
con c3: 4*x1 +  2*x2 >=  7;
solve with milp;              /* solve the MILP problem */
print x1 x2;
quit;
PROC O PTMODEL solution to a mixed-integer linear programming problem

The OPTMODEL procedure prints two tables. The first (not shown) describes the optimization algorithm and tells you that the optimal objective value is 30.5. The second table is the solution vector, which is x = {5, 3.1}.

Mixed-integer linear programming by using the MILPSOLVE subroutine in SAS/IML

The MILPSOLVE subroutine in the SAS/IML language uses matrices and vectors to specify the problem. The syntax for the MILPSOLVE subroutine is almost identical to the syntax for the LPSOLVE subroutine, so see the previous article for an explanation of each argument. The following SAS/IML program defines and solves the MILP problem:

proc iml;
/* information about variables (row of column, doesn't matter) */
colType = {I, C};  /*  C, B, or I for cont, binary, int */
LowerB =  {0, 0};  /* lower bound constraints on x */
UpperB = {10,10};  /* upper bound constraints on x */
 
/* objective function */
c = {3 5};        /* vector for objective function c*x */
 
/* linear constraints */
A = {3 -2,        /* matrix of constraint coefficients */
     5 10,
     4  2};
b = {10,          /* RHS of constraint eqns (column vector) */
     56,
      7};         
 
/* specify symbols for constraints:
   'L' for less than or equal
   'E' for equal
   'G' for greater than or equal */
LEG = {L, L, G}; 
 
/* 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, /*range*/, LowerB, UpperB); 
print rc objVal, result[rowname={x1 x2}];
Solution to linear programming problem by using the LPSOLVE function in SAS/IML software

In the call to MILPSOLVE, the first four arguments are output arguments. The return code (rc) is 0, which indicates that an optimal value was found. The value of the objective function at the optimal value is returned in objVal. The optimal values of the variables are returned in the result argument.

The MILPSOLVE subroutine was introduced in SAS/IML 13.1, which was shipped with SAS 9.4m1. For additional details about the MILPSOLVE subroutine, see the documentation.

tags: 13.1, Optimization

The post Solve mixed-integer linear programming problems in SAS appeared first on The DO Loop.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)