The Linear Programming Solver

Getting Started: LP Solver

The following example illustrates how you can use the OPTMODEL procedure to solve linear programs. Suppose you want to solve the following problem:

$\begin{array}{rlllllcc} \mbox{max} & x_1 & + & x_2 & + & x_3 & & \\ \mbox{ subject to } & 3 x_1 & + & 2x_2 & - & x_3 & \leq & 1 \\ & -2x_1 & - & 3 x_2 & + & 2x_3 & \leq & 1 \\ & & & x_1, & x_2, & x_3 & \geq & 0 \\ \end{array}$

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

proc optmodel;
   var x{i in 1..3} >= 0;
   max f =    x[1] +   x[2] +   x[3];
   con c1:  3*x[1] + 2*x[2] -   x[3] <= 1;
   con c2: -2*x[1] - 3*x[2] + 2*x[3] <= 1;
   solve with lp / algorithm = ps presolver = none logfreq = 1;
   print x;
quit;

The optimal solution and the optimal objective value are displayed in Figure 6.1.

Figure 6.1: Solution Summary

The OPTMODEL Procedure

Problem Summary
Objective Sense	Maximization
Objective Function	f
Objective Type	Linear

Number of Variables	3
Bounded Above	0
Bounded Below	3
Bounded Below and Above	0
Free	0
Fixed	0

Number of Constraints	2
Linear LE (<=)	2
Linear EQ (=)	0
Linear GE (>=)	0
Linear Range	0

Constraint Coefficients	6

Performance Information
Execution Mode	Single-Machine
Number of Threads	1

Solution Summary
Solver	LP
Algorithm	Primal Simplex
Objective Function	f
Solution Status	Optimal
Objective Value	8

Primal Infeasibility	0
Dual Infeasibility	0
Bound Infeasibility	0

Iterations	5
Presolve Time	0.00
Solution Time	0.00

[1]	x
1	0
2	3
3	5

The iteration log displaying problem statistics, progress of the solution, and the optimal objective value is shown in Figure 6.2.

Figure 6.2: Log

NOTE: Problem generation will use 4 threads.

NOTE: The problem has 3 variables (0 free, 0 fixed).

NOTE: The problem has 2 linear constraints (2 LE, 0 EQ, 0 GE, 0 range).

NOTE: The problem has 6 linear constraint coefficients.

NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).

NOTE: The LP presolver value NONE is applied.

NOTE: The LP presolver formulated the dual of the problem.

NOTE: The presolved problem has 2 variables, 3 constraints, and 6 constraint

coefficients.

NOTE: The LP solver is called.

NOTE: The Primal Simplex algorithm is used.

Objective Entering Leaving

Phase Iteration Value Time Variable Variable

P 1 1 2.000000E+00 0 c1 x[1] (S)

P 1 2 1.500000E+00 0 c2 x[3] (S)

P 1 3 1.000000E+00 0 x[1] (S) x[2] (S)

P 1 4 0.000000E+00 0

P 2 5 8.000000E+00 0

NOTE: Optimal.

NOTE: Objective = 8.

NOTE: The Primal Simplex solve time is 0.00 seconds.