The Mixed Integer Linear Programming Solver

Getting Started: MILP Solver

The following example illustrates how you can use the OPTMODEL procedure to solve mixed integer linear programs. For more examples, see the section Examples: MILP Solver. Suppose you want to solve the following problem:

\[ \begin{array}{rlllllcrc} \mbox{min} & 2x_1 & - & 3x_2 & - & 4x_3 & & & \\ \mbox{s.t.} & & - & 2x_2 & - & 3x_3 & \geq & -5 & (\mbox{R1})\\ & x_1 & + & x_2 & + & 2x_3 & \leq & 4 & (\mbox{R2})\\ & x_1 & + & 2x_2 & + & 3x_3 & \leq & 7 & (\mbox{R3})\\ & & & x_1, & x_2, & x_3 & \geq & 0 & \\ & & & x_1, & x_2, & x_3 & \in \mathbb {Z} & & \\ \end{array} \]

You can use the following statements to call the OPTMODEL procedure for solving mixed integer linear programs:

proc optmodel;
   var x{1..3} >= 0 integer;

   min f = 2*x[1] - 3*x[2] - 4*x[3];

   con r1: -2*x[2] - 3*x[3] >= -5;
   con r2: x[1] + x[2] + 2*x[3] <= 4;
   con r3: x[1] + 2*x[2] + 3*x[3] <= 7;

   solve with milp / presolver = automatic heuristics = automatic;
   print x;
quit;

The PRESOLVER= and HEURISTICS= options specify the levels for presolving and applying heuristics, respectively. In this example, each option is set to its default value, AUTOMATIC, meaning that the solver automatically determines the appropriate levels for presolve and heuristics.

The optimal value of x is shown in Figure 8.1.

Figure 8.1: Solution Output

The OPTMODEL Procedure

[1] x
1 0
2 1
3 1



The solution summary stored in the macro variable _OROPTMODEL_ can be viewed by issuing the following statement:

%put &_OROPTMODEL_;

This statement produces the output shown in Figure 8.2.

Figure 8.2: Macro Output

STATUS=OK ALGORITHM=BAC SOLUTION_STATUS=OPTIMAL OBJECTIVE=-7 RELATIVE_GAP=0     
ABSOLUTE_GAP=0 PRIMAL_INFEASIBILITY=0 BOUND_INFEASIBILITY=0                     
INTEGER_INFEASIBILITY=0 BEST_BOUND=-7 NODES=1 ITERATIONS=4 PRESOLVE_TIME=0.00   
SOLUTION_TIME=0.00