STOR @ UNC Intro to Optimization Lu and Tran-Dinh

The only solution to the above equations is x2 = x3 = x4 = 16, so we find x→ =

(0, 16, 16, 16)T . We can check that x→ is feasible to (P). Hence, y→ is optimal to the
dual problem (D), and x→ is the only optimal solution to the primal problem (P).

5.3 Sensitivity Analysis

Sensitivity analysis in linear programming analyzes the effects of perturbation of
the input data on solutions of LPs. This section introduces sensitivity analysis tech-
niques for LPs. More details can be found in linear programming textbooks, e.g.,
[3, 7, 27].

5.3.1 Introduction
We consider the following LP in standard form:



 max z = cT x
 x
s.t. Ax = b, (5.5)



 x ↑ 0.

Here, the matrix A ↓ Rm↔n , vectors b ↓ Rm and c ↓ Rn are input data for this LP.
We can put them into a triple (A, b, c). In many situations the input data (A, b, c)
may not be accurate and may change over time.
Suppose that this LP has an optimal solution x→ with the optimal value z→ . The
following questions can be asked:

1. How do the optimal solution x→ and/or the optimal value z→ change if

• the objective coefficient vector c changes?

• the right-hand side vector b changes?
• the constraint coefficient matrix A changes?

2. How much can we change the input data (A, b, c) so that x→ remains an optimal
solution?

When the right hand side constant of the ith constraint of (5.5) changes from bi
to bi + ! , the optimal value of (5.5) changes accordingly. Under some conditions,
the change in the optimal value of (5.5) can be represented as a linear function of
! , for ! belonging to a certain interval that includes 0. The slope of such a linear
function is called the shadow price on this constraint, which represents the rate of

135/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

change in the optimal value as the right-hand side of this constraint changes from
its current value bi .
The following theorem makes precise the above claim. A proof can be found in
[3]. Again, this theorem can be extended to general linear programs.

Theorem 5.4. Suppose that the LP (5.5) has a nondegenerate optimal basic so-
lution x→ . Then its dual has a unique optimal solution y→ . Moreover, for each
i = 1, · · · , m, there exists an interval [li , ui ] with li < 0 < ui such that for each
! ↓ [li , ui ] the optimal value of the LP (5.5) with bi replaced by bi + ! is given
by z→ + y→i ! .

Below, we consider the following example for a simple illustration.



 max z = 500x1 + 450x2

 x


 s.t. 6x + 5x ↗ 60
1 2
(5.6)

 10x1 + 20x2 ↗ 150




 0 ↗ x1 ↗ 8, x2 ↑ 0.

This LP has a unique optimal solution x→ = ( 45 30 T →

7 , 7 ) with the optimal value z =
5142 67 .
If we increase the RHS of the first constraint by 1 unit, so that the first constraint
becomes 6x1 + 5x2 ↗ 61, how much does the optimal value change? If we solve
this LP graphically, we can find that the optimal solution after the change is still
determined by the following equations


6x1 + 5x2 = 61

10x1 + 20x2 = 150.

The new optimal solution is x̂→ = (6 57 , 4 17 ) and the new optimal value is ẑ→ = 5221 37 .
The change in the optimal value is ẑ→ ↘ z→ = 5221 37 ↘ 5142 67 = 78 47 .
To use this example to verify the above theorem, we can write the dual LP of
(5.6) as 

 min t = 60y1 + 150y2 + 8y3

 y



s.t. 6y1 + 10y2 + y3 ↑ 500



 5y1 + 20y2 ↑ 450



y ↑ 0.

Solving the dual LP we obtain y→1 = 78 47 , exactly the same value as ẑ→ ↘ z→ .

136/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

In the subsequent sections, we use the following example to describe a method

that uses information in the optimal tableau to conduct sensitivity analysis [21].
This method works whenever an optimal tableau for the original LP is available.

Example 5.5. Consider the following LP:



 max z = 41x1 +25x2

 x


 s.t. 3x1 +2x2 +x3 = 10
(5.7)

 5x1 +3x2 +x4 = 16




 x1 , · · · , x4 ↑ 0.

Since (5.7) is canonical, we can apply the simplex method to solve it. The initial
tableau (called Tableau 1) in solving (5.7) is:

z x1 x2 x3 x4 RHS Basic var

1 -41 -25 0 0 0 z=0
0 3 2 1 0 10 x3 = 10
0 5 3 0 1 16 x4 = 16

After several simplex iterations, we arrive at the optimal tableau below (called
Tableau 2), which shows the optimal basic solution in which x1 and x2 are basic
variables. We say that {x1 , x2 } is an optimal basis.

z x1 x2 x3 x4 RHS Basic var

1 0 0 2 7 132 z = 132
0 1 0 -3 2 2 x1 = 2
0 0 1 5 -3 2 x2 = 2

5.3.2 Changes in the objective coefficients

We consider two cases:

• Case 1: The coefficient is associated with a nonbasic variable.

• Case 2: The coefficient is associated with a basic variable.

Case 1: Consider changing the coefficient for x3 in the objective function from 0
to ! . Note that x3 is a nonbasic variable in Tableau 2. Tableau 1 becomes Tableau
1a below:

137/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

z x1 x2 x3 x4 RHS Basic var

1 -41 -25 ↘! 0 0 z=0
0 3 2 1 0 10 x3 = 10
0 5 3 0 1 16 x4 = 16
Starting from Tableau 1a, we conduct the same EROs (elementary row operations)
that bring Tableau 1 to Tableau 2, to arrive at Tableau 2a below:

z x1 x2 x3 x4 RHS Basic var

1 0 0 2 ↘ ! 7 132 z = 132
0 1 0 -3 2 2 x1 = 2
0 0 1 5 -3 2 x2 = 2

Clearly, if ! ↗ 2, the current BFS (basic feasible solution) x = (2, 2, 0, 0)T remains
optimal, and the optimal value is z = 132. If ! > 2, then extra simplex iterations
are needed to find the new optimal solution.
Case 2: Now, consider changing the coefficient in the objective function for x1
from 41 to 41 + ! . Note that x1 is a basic variable in Tableau 2. Tableau 1 becomes
Tableau 1b below:

z x1 x2 x3 x4 RHS Basic var

1 ↘41 ↘ ! -25 0 0 0 z=0
0 3 2 1 0 10 x3 = 10
0 5 3 0 1 16 x4 = 16
Starting from Tableau 1b, we conduct the same EROs that bring Tableau 1 to
Tableau 2, to arrive at Tableau 2b below:

z x1 x2 x3 x4 RHS Basic var

1 ↘! 0 2 7 132 z = 132
0 1 0 -3 2 2 x1 = 2
0 0 1 5 -3 2 x2 = 2
Tableau 2b is not a valid simplex tableau, because the coefficient for x1 in row 0 is
nonzero. It needs to be zero since x1 is a basic variable in this tableau. We add !
times row 1 to row 0 to obtain Tableau 3b below:

138/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

z x1 x2 x3 x4 RHS Basic var

1 0 0 2 ↘ 3! 7 + 2! 132 + 2! z = 132 + 2!
0 1 0 -3 2 2 x1 = 2
0 0 1 5 -3 2 x2 = 2

In order for the current BFS to remain optimal, we need 2 ↘ 3! and 7 + 2! to be

nonnegative. Hence, when ↘7/2 ↗ ! ↗ 2/3, the current BFS x = (2, 2, 0, 0) remains
optimal, and the optimal value is z = 132 + 2! . If ! does not belong to the above
range, then extra iterations need to be conducted.

5.3.3 Changes in the right hand side coefficients

Now, consider changing the right hand side constant for the first constraint from 10
to 10 + ! . Tableau 1 becomes Tableau 1c below:

z x1 x2 x3 x4 RHS Basic var

1 -41 -25 0 0 0 z=0
0 3 2 1 0 10 + ! x3 = 10 + !
0 5 3 0 1 16 x4 = 16
Starting from Tableau 1c, we conduct the same EROs that bring Tableau 1 to
Tableau 2, to arrive at Tableau 2c below:

z x1 x2 x3 x4 RHS Basic var

1 0 0 2 7 132+2! z = 132 + 2!
0 1 0 -3 2 2↘3! x1 = 2 ↘ 3!
0 0 1 5 -3 2+5! x2 = 2 + 5!
The right hand side column in Tableau 2c is obtained by noting that the column
under x3 changes from    
0 2
   
   
1 to ↘3
   
0 5

after the elementary row operations. So a column that starts with (0, ! , 0)T will
become (2! , ↘3! , 5! )T after the same EROs.
Consequently, whenever 2↘3! ↑ 0 and 2+5! ↑ 0 hold simultaneously, Tableau
2c shows an optimal solution. This happens when ↘2/5 ↗ ! ↗ 2/3. For each ! be-
longing to this range, {x1 , x2 } is an optimal basis, and an optimal solution is given
by x = (2 ↘ 3! , 2 + 5! , 0, 0), with the optimal value 132 + 2! .

139/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

5.4 Exercises
Exercise 5.1. Consider a primal-dual pair of LPs, where the primal problem is a
maximization problem. Using primal-dual rules to show that the vectors u and v
computed by u = xT (AT y ↘ c) and v = yT (b ↘ Ax) are always nonnegative, where
x is the vector of primal variables and y is the vector of dual variables.

Exercise 5.2. For each LP problem below, write down the corresponding dual LP
problem. Check if the dual problem is in a standard or in a canonical form (Explain
why?). Explain how do you conduct the sign of the variables and the constraints in
the dual problem?

1. 

 min z = x1 +2x2 ↘3x3 +x4

 x



 s.t. x1 ↘2x2 +3x3 +x4 ↗ 3,


 x2 +2x3 +2x4 ↑ ↘5,



 2x1 ↘3x2 ↘7x3 ↘4x4 = 2,




 x1 ↑ 0, x4 ↗ 0.
2. 

 max z = ↘x1 +2x3

 x


 s.t. x1 +x2 ↗ 1,

 ↘x1 +x3 = 2,




 x1 ↗ 0, x2 ↑ 0
3. 


 max z = cT x

 x

 s.t. Ax = b,

 Bx ↑ d,




 x ↑ 0,

where A ↓ Rm↔n , B ↓ R p↔n , c ↓ Rn , b ↓ Rm and d ↓ R p .

4. 

 min z = cT x

 x
 s.t. a ↗ Ax ↗ b,


 0 ↗ x ↗ u,

where A ↓ Rm↔n , c ↓ Rn , a, b ↓ Rm (a ↗ b) and u ↓ Rn (u ↑ 0).

140/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

Exercise 5.3. Using the duality theorem, verify if the following LP problems are
unbounded:
 

 max z = 2x1 + x2 
 min z = ↘4x1 + 2x2

 x 
 x

 

 s.t. x ↘ x ↗ 4,  s.t. ↘x + x ↑ 2,
1 2 1 2
(a) (b)
  x


 x1 ↘ x2 ↗ 2 

 ↘x 1 + 2↑1

 

 x1 ↑ 0, x2 ↑ 0.  x1 ↑ 0, x2 ↑ 0.

Explain your answer using the duality theory we studied in class, do not use simplex
methods or graphs.

Exercise 5.4. When modeling a portfolio selection problem, we obtain the follow-
ing LP problem:

max z = 0.043x1 + 0.027x2 + 0.025x3 + 0.022x4 + 0.045x5

x 

 Cash: x1 + x 2 + x 3 + x 4 + x 5 ↗ 10,





 Government: x2 + x3 + x4 ↑ 4,


s.t. Quality: 0.6x1 + 0.6x2 ↘ 0.4x3 ↘ 0.4x4 + 3.6x5 ↗ 0,





 Maturity: 4x1 + 10x2 ↘ x3 ↘ 2x4 ↘ 3x5 ↗ 0,



 x ↑ 0.

(a) Write down the dual problem of this LP.

(b) Verify that x→ = (2.1818, 0, 7.3636, 0, 0.4545)T is a feasible solution of the pri-
mal problem rounding up to 4 digits after the decimal point.
(c) Using the complementarity slackness theory to check if x→ is an optimal solu-
tion of the primal LP. If x→ is optimal, compute an optimal solution for the dual
problem.

Note that all the computation must be done approximately up to 4 digits after the
decimal point.

Exercise 5.5. Consider the following pair of primal and dual LPs:


 min z = 35x1 +30x2 +60x3 +50x4 +27x5 +22x6

 x


 s.t x1 +2x3 +2x4 +x5 +2x6 ↑ 9,
(Primal)

 x2 +3x3 +x4 +3x5 +2x6 ↑ 19,




 x ↑ 0.

141/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh


 max v = 9y1 +19y2

 y





 s.t y1 ↗ 35,





 y2 ↗ 30,



2y1 +3y2 ↗ 60,
(Dual)



 2y1 +y2 ↗ 50,





 y1 +3y2 ↗ 27,





 2y1 +2y2 ↗ 22,



y ↑ 0.

(a) Suppose that x→ = (0, 0, 0, 0, 5, 2)T is feasible solution of the primal problem,
verify that this vector x→ is an optimal solution to the primal LP using the
complementary slackness condition.
(b) Find the set of all optimal solutions of the dual LP. Does the primal LP have a
unique optimal solution, or multiple optimal solutions?
(c) Now suppose that the right hand side constants of the first two primal con-
straints are changed to 11 and 23 respectively (from the current values of 9 and
19). Does the dual optimal solution(s) you found in (b) remain optimal after
the change? If so, use it to find the set of all optimal solutions to the primal LP.

Exercise 5.6. Consider the following LP problem:



 max z = 3x1 +7x2 +5x3

 x


 s.t x1 +x2 +x3 +s1 = 50,

 2x1 +3x2 +x3 +s2 = 100,




 x1 , x2 , x3 , s1 , s2 ↑ 0.

After using the simplex method to solve it, we obtain the following tableau, in
which x3 and x2 are basic variables. For each question below, you should briefly
write down the details of your answer to support your claim.

z x1 x2 x3 s1 s2 RHS Basic var

1 3 0 0 4 1 300 z = 300
0 0.5 0 1 1.5 -0.5 25 x3 = 25
0 0.5 1 0 -0.5 0.5 25 x2 = 25
max z; x, s ↑ 0

142/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

1. Write down the basic optimal solution obtained from this simplex tableau, and
the corresponding optimal value of this LP. Explain if this LP has a unique or
multiple solutions.
2. Suppose that the objective function changes to max z = (3 + ∀ )x1 + 7x2 + 5x3 .
How does this change affect the simplex tableau in which x3 and x2 are basic
variables? For what range of ∀ does that tableau show an optimal solution?
Write down an optimal solution and the optimal value for all ∀ belonging to
that range. Does ∀ = 4 belong to that range? Find an optimal solution and the
optimal value for ∀ = 4.
3. Suppose that the objective function changes to max z = 3x1 + (7 + ∀ )x2 + 5x3 .
Write down the new simplex tableau in which x3 and x2 are basic variables. For
what range of ∀ does that tableau show an optimal solution? Write down an
optimal solution and a formula for the optimal value for ∀ in that range. Does
∀ = 4 belong to that range? Find an optimal solution and the optimal value for
∀ = 4.
4. Suppose that the objective function changes to max z = 3x1 +7x2 +(5+∀ )x3 +
# s1 . Write down the new simplex tableau in which x3 and x2 are basic vari-
ables. For which ∀ and # does that tableau show an optimal solution? Write
down an optimal solution and a formula for the optimal value for ∀ belonging
to that range. Does (∀ ,# ) = (2, 2) belong to that range?
5. Let the objective function be the original function. Suppose that the right hand
side constant of the first constraint changes from 50 to 50+∀ . For what range
of ∀ does the basis {x3 , x2 } continue to be optimal? What is the optimal value
when ∀ belongs to this range?
6. Let the objective function be the original function. Suppose that the right hand
side constant of the second constraint changes from 100 to 100+∀ . For what
range of ∀ does the basis {x3 , x2 } continue to be optimal? What is the optimal
value when ∀ belongs to this range?

Exercise 5.7. Consider the following linear program:

143/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh


 max z = 3x1 + x2 + 4x3 + x4

 x



 6x1 + 3x2 + 5x3 + 4x4 ↗ 25


 3x1 + 2x2 + 3x3 + x4 ↗ 15



 3x1 + 4x2 + 5x3 + 2x4 ↗ 20




 x1 ↑ 0 x2 ↑ 0 x3 ↑ 0 x4 ↑ 0 .

By adding three slack variables x5 , x6 and x7 to the first, second, and third con-
straints, we convert the above LP into canonical form. Then we apply the simplex
method to it and obtain the following simplex tableau, in which the value in the
RHS entry of row 0 is missing. For each question below, you should briefly write
down the details of your answer to support your claim.

z x1 x2 x3 x4 x5 x6 x7 RHS Basic Var

1 0 2 0 1 1/5 0 3/5 ? z =?
0 1 ↘1/3 0 2/3 1/3 0 ↘1/3 5/3 x1 = 5/3
0 0 0 0 ↘1 ↘2/5 1 ↘1/5 1 x6 = 1
0 0 1 1 0 ↘1/5 0 2/5 3 x3 = 3

1. What is the value of the RHS entry in row 0 of the above tableau? Justify your
answer.
2. Suppose that the objective coefficient of x3 (currently 4) changes to 4 + ∀ .
For what range of ∀ does the current optimal basis {x1 , x6 , x3 } continue to be
optimal? What is the optimal value for ∀ in this range?
3. Let the objective function be the original function. Suppose that the right hand
side constants for the first and second constraints change to 25 + ∀ and 15 +
∀ simultaneously (for example if ∀ = 1 then the RHS constants in the first
two constraints become 26 and 16 respectively). For what range of ∀ does the
current optimal basis {x1 , x6 , x3 } continue to be optimal? What is the optimal
value for ∀ in this range?

144/263
Chapter 6

Software for Linear Programming

6.1 Overview
Computer software for linear programming is perhaps the most well developed
area in optimization software, and is substantially reliable in practice. This chapter
briefly presents an overview on computer software for LPs. We distinguish between
two types of computer software.

• LP solvers: Roughly speaking, an LP solver is a computer program that im-

plements one or many solution methods to solve LPs in a given form. There
are at least two kinds of methods that are often implemented in an LP solver:
simplex methods and interior-point methods. Nowadays, the list of LP solvers
is getting longer and longer. For instance, CPLEX or linprog are LP solvers.
• Optimization modeling languages: Optimization modeling languages pro-
vide interfaces between model developers and optimization solvers. Modeling
languages are “developed with the aim of allowing users to express LP and
other optimization problems in a natural, algebraic form similar to the original
mathematical expressions,” as put in [8]. Data and models can be separated,
making it easy to audit and adapt the models. The model developers do not
have to arrange data into matrices or vectors, as this task will be done by the
compiler. The compiler will translate the model into an acceptable format and
pass it to a solver, which receives the problem and solves it. An optimiza-
tion modeling software is often connected to various solvers ((either built-in or
third-party solvers)) that handle different types of problems.

145
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

Modeling languages are good choices for model developers who deal with opti-
mization problems of moderate to large-scale sizes and do not intend to write more
codes than just the models. By using a modeling language in this course, we can fo-
cus on how to build the mathematical models for various types of problems, rather
than spending too much effort on coding-specific issues. We do need to master the
basics of a modeling language to be able to use it at an introductory level.
Let us start discussing some common LP solvers before using GAMS as a mod-
eling language to illustrate the various applications. While many LP solvers are
available, we focus on LP solvers that are readily accessible to most users.

6.2 LP solvers
We discuss Excel in Microsoft Office, linprog in Matlab, CPLEX, and some
other LP solvers.

6.2.1 Excel
Let us start with Excel, a Microsoft’s software program. The Solver add-in of Mi-
crosoft Excel is an easy-to-use tool and is widely used in business worldwide. We
illustrate how to use this tool with a small example.
Problem description: A company produces two types of picture frames: each type-
1 frame uses 2 hours of labor and 1 ounce of metal and brings $2.25 in profit, and
each type-2 frame uses 1 hour of labor and 2 ounces of metal and brings $2.60 in
profit. Each week 4000 labor hours and 5000 ounces of metal are available, and the
company aims to maximize its weekly profit with an optimal production plan.
Problem modeling: To model the problem as a linear program, we use xi to denote
the number of type i picture frames produced weekly for i = 1, 2, and formulate the
following LP: 

 max z = 2.25x1 + 2.60x2

 x


 s.t. 2x1 + x2 ↗ 4000,
(6.1)

 x1 + 2x2 ↗ 5000,




 x ↑ 0.
Solving this LP by Excel: When using Excel Solver for the first time, it is often
necessary to activate it. The procedure depends on the version of Excel, and it often
involves accessing the “Add-Ins” menu in Excel “Options” to select the “Solver

146/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

Add-In” to be active. Once activated, one can set up the problem in Excel as shown
in Figure 6.1.
We enter data of the problem into the cells B5, C5, B7, C7, B8, C8, F7 and
F8, and use cells B10 and C10 to store an arbitrarily chosen starting solution
(0, 0). We use cell D5 to store the objective value, which is given by the for-
mula =SUMPRODUCT(B5:C5,$B$10:$C$10). The $ signs are to anchor lo-
cations of cells B10 and C10 when copying this formula to cells below. We use
cells D7 and D8 for values of the left hand sides of the labor and metal constraints
respectively, given by formulas =SUMPRODUCT(B7:C7,$B$10:$C$10) and
=SUMPRODUCT(B8:C8,$B$10:$C$10) respectively. The ↗ signs in E7 and
E8 are for display purposes and will be ignored by Excel Solver.

Fig. 6.1 Model and solve the picture frame production problem in Excel.

To start using the Excel Solver in Excel 2010, click Solver under the Data menu
to open the Solver Parameters window.

• In the Set Objective box, enter the cell which contains the formula for com-
puting the objective value (cell D5 for the example).
• Select max in the line below since we want to maximize the profit. For the
By Changing Variable Cells, select the cells which contain the values of the
decision variables (cells B10:C10 for the example).
• Next, add constraints one by one: select the cell that contains the left hand side
formula as the Cell Reference, choose <=, >=, or = based on the type of
constraint, and enter the cell that contains the right hand side in the Constraint
box.

147/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

• Following that, check the box of making unconstrained variables non-negative,

and select Simplex LP as the solving method.
• Finally, click Solve, and the Solver Results box will tell us if Solver finds a so-
lution. If Solver finds a solution, ensure that “Keep Solver Solution” is marked
and click OK.

The optimal solutions for the decision variables will be placed in the Changing
Cells.

Fig. 6.2 Completed Excel Solver dialog box.

Final remarks: As we can see, the Excel Solver is easy and intuitive. With the wide
availability of Excel, the Solver add-in is extensively used for simple optimization
tasks. However, in general, it is not convenient to use Excel Solver for large-scale
optimization models. It is hard to model complicated algebraic constraints using
Excel Solver, and its computational performance is not as competitive as software
specialized in optimization. Moreover, any dimensional or structural changes in the
data would demand a major revision of the Solver parameters.

148/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

6.2.2 Matlab’s LP solver

Matlab provides several routines for optimization in the Optimization Toolbox. It
is often integrated in Matlab when we install it. More information about Matlab
can be found at [Link] The LP solver, called linprog, in
the Optimization Toolbox of Matlab can solve relatively large-scale LPs. It accepts
matrices and vectors as inputs. To see how we can input data of an LP, from the
Command Window of Matlab, type

>> help linprog

for instructions on how to use this function. Below, we use linprog to solve the
above picture frame example. We can use the following commands in the Com-
mand Window of Matlab:

>> c = [-2.25; -2.60];

>> A = [2 1; 1 2];
>> b = [4000;5000];
>> lb = zeros(2,1);
>> [x, z] = linprog(c, A, b, [], [], lb)

The first to the third lines enter the input data for c, A and b, respectively. The fourth
line give a lower bound on x, which is 0. This imposes that x ↑ 0. The last command
calls linprog to minimize the linear objective function specified by the vector c,
subject to linear constraints defined by the matrix A and the right hand side vector b
and the lower bound lb on the variables. The empty matrices [] in the inputs indicate
that there are no equality constraints. The outputs will be x = (1000, 2000) with the
optimal value z = ↘7450 as we can see below:

x =
1.0e+03 *
0.999999982545405
2.000000004206820
z =
-7.449999971664894e+03

We note that linprog also provides several options so that we can choose differ-
ent methods, accuracy and monitor outputs to meet our expectation.

149/263
STOR @ UNC Intro to Optimization Lu and Tran-Dinh

As illustrated by the above example, in order to use Matlab for solving LPs, one
needs to arrange the input data (A, b, c) into matrices and vectors. For nonlinear
optimization problems that involve nonlinear objective functions or constraints, one
needs to define Matlab functions and pass them as function arguments in the inputs.
For large-scale problems with complicated constraints, specifying the matrices and
vectors can become a cumbersome task that makes it inconvenient to audit the
codes or adapt the codes in response to changes in the model. However, this can be
done by providing an interface on top of the solver to do this preprocessing step.
Matlab provides several tools and routines to do such a task.

6.2.3 Other LP solvers

There are many other solvers for LPs. Below is a non-exhaustive list of LP solvers
due to H. Mittelmann (see [Link]

• CPLEX: CPLEX is a high-performance mathematical programming solver for

linear programming, mixed integer programming, and quadratic programming.
The name came from Simplex method implemented in C. This software pro-
gram is currently owned by IBM, and is still active. CPLEX has a long history
of development. It was founded by Robert E. Bixby and was sold commercially
in 1988 by CPLEX Optimization Inc. More information about this solver can
be found at [Link]
optimizer/[Link]. CPLEX is available free of charge for academic use and
for students.
• Gurobi: The Gurobi Optimizer is a new mathematical programming solver
and is able to handle all major problem types, including linear programming.
More information can be found here: [Link] Gurobi is avail-
able free of charge for academic use and for students. Gurobi is named from its
founders: Zonghao Gu, Edward Rothberg and Robert Bixby (also the father of
CPLEX). Gurobi is very fast and can solve really big problems.
• Mosek: MOSEK is a tool for solving mathematical optimization problems
such as LPs, quadratic programming, conic problems and mixed integer pro-
gramming. MOSEK ApS was established in 1997 by Erling D. Andersen
and Knud D. Andersen from Denmark. This software program is available at
[Link] and is free-of-charge for academic use.

150/263