Mathematical Programmingfor All
Pano Santos, PhD

Dedication
These video classes are
dedicated to thememory of Saul I. Gass
(1926-2013), a mentor
and friend.

GoalsGoals• These video classes are designed for an audience with limited or no backgroundin mathematical programming, and includes: Data Scientists, Computer Scientists,
Systems/IT Engineers, and Business Analysts.

• These video classes are designed for an
audience with limited or no background inmathematical programming, and include• Data Scientists,• Computer Scientists,• Systems/IT Engineers,• Business Analysts.

Goals• These video classes are designed for an audience with limited or no backgroundin mathematical programming, and includes: Data Scientists, Computer Scientists,
Systems/IT Engineers, and Business Analysts.
• The students taking this class will learn the foundations of Linear Programming(LP) and Mixed Integer Linear Programming (MIP).

• The students taking this class will learn thefoundations of:• Linear Programming (LP)• Mixed Integer Linear Programming (MIP).

Goals• These video classes are oriented to “students” with no or little background inmathematical programming, Data Scientists, Computer Scientists, Systems/IT
Engineers, and Business Analysts.
• The students taking this class will learn the foundations of Linear Programming(LP) and Mixed Integer Linear Programming (MIP).
• You will learn how to formulate practical problems as Mixed Integer Linear
Problems for: industrial, government, and military applications.

• You will learn how to formulate practicalproblems as Mixed Integer Linear Problems
for industrial, government, and military
applications.

Goals• These videoclasses 2,100
are orientedcompanies
to “students” with nofrom
or little backgroundOver
approx.in
mathematical programming, Data Scientists, Computer Scientists, Systems/IT
Engineers, and Business Analysts.

50
industries use Gurobi for their mathematicalprogramming applications• The students taking this class will learn the foundations of Linear Programming(LP) and Mixed Integer Linear Programming (MIP).
• You will learn how to formulate practical problems as Mixed Integer Linear
Problems for: industrial, government, and military applications.

Over 2,100 companies from approx. 50
industries use Gurobi for their mathematicalprogramming applications

Prerequisites

Prerequisites• Linear algebra and calculus• Both at the college level• Familiarity with mathematical notation.
𝑒 = 𝑚𝑐 2• Basic knowledge of Python

Remarks

These mathematical optimization models shall capture the key
features of an optimization problem (effective), and they should
be solvable in a reasonable amount of time (efficient).

• In spite of the pragmatic
nature of these videos, it
is important to cover
theoretical aspects ofLinear Programming andInteger Programming
problems in order tobuild and tune up
efficient mathematicaloptimization models.

• These series of introduction tomathematical programming videos
will have three main chapters.
• Linear programming overview.
• Mixed integer linear programming overview.
• Mathematical programming model building overview.

• The durationof each video
will be in therange of 10
min to 15 min.

Mathematical Programming
Background and relevanceOrigin of Mathematical
Programming

Origin of Mathematical Programming• The origin of mathematical programming is theinvention of linear programming in 1947, shortly
after World War II.

• “Mathematical programming enables stating
general goals and to lay out a path of detailed
decisions to make in order to “best” achievethese goals when faced with a practical situationof great complexity”. –George Dantzig• Mathematical programming entails• the formulation of real-world problems in detailed
mathematical terms (models).
• the development of techniques for solving thosemodels (algorithms).
• and the use of SW and HW to develop
applications.

Mathematical Programming Remarks• It should be pointed out that mathematical programming is different
from computer programming.
• Mathematical programming is ‘programming’ in the sense of‘planning’.

Mathematical Programming Remarks• The common feature that mathematical programming models haveis that they all involve optimization.
• This is why mathematical programmingis often called mathematical optimization.

Mathematical Programming Remarks• In these video classes, we focus
on two special types ofmathematical programming
models.
• Linear Programming (LP)models.
• Mixed Integer linear
Programming (MIP) models.

Mathematical Programming Remarks• Mathematical programming is a declarative approach where themodeler formulates a mathematical optimization problem that
captures the key features of a complex decision problem.
• Mathematical optimization formulations can then be solved bystandard LP algorithms and MIP algorithms.

Mathematical Programming Remarks• Gurobi users formulate mathematical optimization problems
that are solved by the Gurobi callable library.
• The mathematics and computer science behind Gurobi
technology are leading edge.
• Gurobi has the best performance in the market.

Mathematical Programming Remarks•

Gurobi users formulate mathematical optimization problems that are solved by the Gurobi callable library.

•

The mathematics and computer science behind Gurobi technology are leading edge, that is why Gurobi solver has
the best performance in the market.

Mathematical Programming Remarks• The particular implementation of the mathematics and computerscience in the Gurobi Optimizer is quite complex.
• The user does not need to worry about how to solve theoptimization problem at hand, this is done automatically by Gurobi
behind the scenes.

• The user only needs to have an efficient LP or MIP model that
captures the main characteristics of the optimization problem andthe required data for the model.

1. Introduction to linear programming andmixed integer linear programming
models - The furniture factory problem.
• Illustrative example prevalentthroughout the video series.
• Introduction to general formulations forlinear programming and mixed integer
programming problems.

2. Furniture factory problem Graphical Solution• How to graphically solve the furnitureproblem when formulated as a linear
programming model.
• Introduction to important concepts
related to the theory of linear
programming.

3.Overview - Simplex method
to solve linear programming
problems.
• How the simplex method works.
• Key concepts of the theory of linear
programming.

4.Modeling and solving thefurniture factory problem
with the Gurobi python
API.
• How to use the Gurobi Python API
to formulate the furniture problem
as a linear programming problem
and solve it using the Gurobi
callable library

5. Sensitivity analysis of LP
problems with the Gurobi
python API.
• How linear programming models havean economic interpretation and theimpact on the objective function value
derived from marginal changes on a
resource capacity value.

6. Multiple optimal solutions,modeling opportunity with
the Gurobi python API.

7. Unbounded solutions,modeling opportunity with the
Gurobi python API.

• How a linear programming problem
can have multiple solutions.

• How a linear programming problem can be
unbounded which means that the objectivefunction value can be arbitrarily large.

• How having multiple solutions
presents an opportunity to improve
the linear programming problem
formulation.

• How an unbounded linear programming
problem presents an opportunity to improve
the linear programming problem
formulation.

8.Infeasible solutions, modelingopportunity with the Gurobi python
API.
• How a linear programming problem can beinfeasible, lacking a solution that can satisfy
all the constraints of the problem.
• How an infeasible linear programming
problem presents an opportunity to improve
the linear programming problem formulation.

9.Maximize or minimize
objective function.
• How to tackle maximization andminimization linear programming
problems.

10. Unconstrained decisionvariables.
• How Gurobi automatically handles
unconstrained decision variables.

11. Initial basic solution.
• How to determine an initialsolution of a linear programming
problem in order to start thesimplex method. This is done
automatically by Gurobi.

12. Presolve.
• An example of how Presolve
reduces the size of a linear
programming problem. Gurobi by
default calls Presolve tosignificantly reduce the size of an
LP problem.

13. Matrix sparsity.
• An important characteristic oflinear programming problems
that is related to the number of
non-zero coefficients associatedwith the variables in the problem
formulation.

14. Duality in linear
programming.
• One of the most importantconcepts in linear programmingthat allows the efficientcharacterization of optimal
solutions of a linear programming
problem.

15. Optimality conditions inlinear programming.
• Discussion of duality andestablish sufficient andnecessary conditions of optimal
solutions of a linear programming
problem.

16. Dual simplex method.
• A variation of the simplex methodthat is frequently used to solve
mixed integer linear programming
problems.

Introduction to linear programming
The Furniture Factory problem

The Furniture Factory Problem
A data scientist is in charge ofdeveloping the Weekly Production
Plan of two key products that thefurniture factory makes: chairs
and tables.
The data scientist using machinelearning techniques predicts thatthe selling price of a chair is $45
and the selling price of a table is$80 dollars.

The Furniture Factory Problem
A data scientist is in charge of developing the weekly
production plan of two key products that the furniturefactory makes: chairs and tables.
The data scientist using machine learning techniques
predicts that the selling price of a chair is $45 and theselling price of a table is $80 dollars.

• There are two critical resourcesin the production of chairs andtables:• Mahogany (measured in board
square-feet) and labor(measured in work hours).
• There are 400 units ofmahogany available at the
beginning of each week.
• There are 450 units of labor
available during each week.

The Furniture Factory Problem=5

10hrs.

A data scientist is in charge of developing the weekly production
plan of two key products that the furniture factory makes: chairs
and tables.
The data scientist using machine learning techniques predicts
that the selling price of a chair is $45 and the selling price of atable is $80 dollars.
• There are two critical resources in the production of chairs
and tables:• Mahogany (measured in board square-feet) and labor(measured in work hours).
• There are 400 units of mahogany available at the beginningof each week.
• There are 450 units of labor available during each week.

= 20

15 hrs.

• The data scientist estimates that• One chair requires 5 units ofmahogany and 10 units of labor.
• One table requires 20 units ofmahogany and 15 units of labor.
• The marketing department has
told the data scientist that ALL
the production of chairs andtables can be sold.

The Furniture Factory Problem

Problem statement:
What is the Production Plan
that maximizes total revenue?

A data scientist is in charge of developing the weekly
production plan of two key products that the furniturefactory makes: chairs and tables.
The data scientist using machine learning techniques
predicts that the selling price of a chair is $45 and theselling price of a table is $80 dollars.

• There are two critical resources in the productionof chairs and tables:• Mahogany (measured in board square-feet) andlabor (measured in work hours).
• There are 400 units of mahogany available at the
beginning of each week.
• There are 450 units of labor available during eachweek.
• The data scientist estimates that• One chair requires 5 units of mahogany and 10 unitsof labor.
• One table requires 20 units of mahogany and 15
units of labor.
• The marketing department has told the data
scientist that all the production of chairs and tables
can be sold.

The Furniture Factory Problem… 2

DATA

CHAIR

TABLE

CAPACITY

5 units

20 units

400 units

10 hours

15 hours

450 hours

$45

$80

x1, x2 ≥ 0

The data of the furnitureproblem can be summarized in
the following table:• To determine a Production Plan, we
need to decide how many chairs
and tables to make in order tomaximize total revenue, whilesatisfying resources constraints.
• This problem has two decisionvariables:• x1: number of chairs to produce.
• x2: number of tables to produce.
• The number of chairs and tables to
produce should be a non-negative
number. That is, x1, x2 ≥ 0.

The Furniture Factory Problem… 2• If we would know the value of the amountof chairs to produce (x1), then since eachchair generates $45, the total revenue
generated by the production of chairs
can be determined by the term 45x1
(45*x1).
• Similarly, the total revenue generated by the
production of tables can be determined by theterm 80x2 (80*x2).
• Consequently, the total revenue generated by
the production plan can be determined by thefollowing equation.

• Revenue = 45x1 + 80x2

The data of the furniture problem can besummarized in the following table:

DATA

CHAIR

TABLE

CAPACITY

5 units

20 units

400 units

10 hours

15 hours

450 hours

$45

$80

The Furniture Factory Problem… 2• The Production Plan is constrained by the amount of
resources available.

The data of the furniture problem can besummarized in the following table:• How do we ensure that the production plan does notconsume more mahogany than the amount ofmahogany available?
DATA• If we decide to produce x1 number of chairs, then the
total amount of mahogany consumed by the productionof chairs is 5x1 (5*x1).
• Similarly, if we decide to produce x2 number of tables,
then the total amount of mahogany consumed by the
production of tables is 20x2 (20*x2).

• Hence, the total consumption of mahogany by the
production plan determined by the values of x1 and x2
is (5x1 + 20x2). However, the consumption of mahoganyby the production plan cannot exceed the amount ofmahogany available. We can expressed these ideas in
the following constraint:

5x1 + 20x2 ≤ 400

CHAIR

TABLE

CAPACITY

5 units

20 units

400 units

10 hours

15 hours

450 hours

$45

$80

The Furniture Factory Problem… 2• The production plan is constrained by the amount of
resources available.

The data of the furniture problem can besummarized in the following table:• In similar fashion, we can formulate the constraint forlabor resources.
• The total amount of labor resources consumed by the
production of chairs is 10 labor units multiplied by the
number of chairs produced, that is 10x1 (10*x1).
• The total amount of labor resources consumed by the
production of tables is 15 labor units multiplied by the
number of tables produced, that is 15x2 (15*x2).

• Therefore, the total consumption of labor resources by
the production plan determined by the values of x1 andx2 is (10x1 + 15x2). This labor consumption cannot
exceed the labor capacity available. Hence, thisconstraint can be expressed as follows:

10x1 + 15x2 ≤ 450.

DATA

CHAIR

TABLE

CAPACITY

5 units

20 units

400 units

10 hours

15 hours

450 hours

$45

$80

The Furniture Factory Problem… 2• The furniture problem formulation as a linear
programming (LP) problem is

The data of the furniture problem is

1.0 . Max revenue = 45𝑥1 + 80𝑥2
DATA

2.0

5𝑥1 + 20𝑥2 ≤ 400

CHAIR

TABLE

CAPACITY

5 units

20 units

400 units

10 hours

15 hours

450 hours

$45

$80

Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 Non − negativity

Introduction linear programmingand mixed integer linear
programming problems
Key components of mathematical programming models

𝑥1 is the decision variable representing the number ofchairs to produce. The index 1 refers to the productchair.

Key components of linear
programming model
1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

𝑥2 is the decision variable representing the number oftables to produce. The index 2 refers to the producttable.

We can create a set of products mapping each productwith the index associated with each decision variable.
Then, the set products = {1: chair, 2: table} maps eachindex with its corresponding product.

Similarly, we can create a set for resources as follows:
resources = {1: mahogany, 2: labor} where the index 1
maps to the resource mahogany, and the index 2 maps
to the resource labor.

5𝑥1 + 20𝑥2 ≤ 400

Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 Non − negativity

This LP model has several types of parameters representing
known quantities (data) that characterize the problem.
• Prices can be defined over the set of products, e.g. b1 = 45 meansthat the price of a chair is $45, and b2 = 80 means that the price of atable is $80.
• Resources capacity can be defined over the set of resources, e.g. K1= 400, means that the availability of mahogany is 400 units/week, andK 2 = 450 means that the availability of labor is 450 units/week.
• Technology coefficients describe the consumption of resources whenbuilding a product. For example,
a1,1 = 5 means that five units of mahogany are consumed whenbuilding one chair,
a1,2 = 20 means that twenty units of mahogany are consumed whenbuilding one table,
a2,1 = 10 means that ten units of labor are consumed when building
one chair,a2,2 = 15 means that fifteen units of labor are consumed when building
one table.

Key components of linear
programming model… 2
1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

5𝑥1 + 20𝑥2 ≤ 400

Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 Non − negativity• Matrix of technology coefficients

DATA

CHAIR

TABLE

a11 = 5a12 = 20

a21 = 10a22 = 15Mahogany

Labor

Key components of linear programming model… 3
1.0 . Max revenue = 45𝑥1 + 80𝑥2

2.0

5𝑥1 + 20𝑥2 ≤ 400

Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 Non − negativity
This LP model has two types of constraints limiting the number of chairs and tables that canbe produced.
These constraints are defined over the set of resources, and represent that the consumption ofeach resource by a Production Plan cannot exceed the amount available of the resource.
The objective function is to maximize total revenue generated by the optimal Production Plan.

Linear Programming model components
SummaryLinear Programming model components
Summary

Abstraction and generalizationof furniture problem
Original
Parametrized
LP problem
LP problem
formulation
formulation

1.0 . Max revenue = 45𝑥1 + 80𝑥2

1.0 . Max (b1 = 45)𝑥1 + (𝑏80)𝑥2 capacity
2 =of mahogany
2.0 5𝑥1 + 20𝑥2 ≤ 400 Units
2.0
𝑎1,1 = 5 𝑥1 + (𝑎1,2 =Labor20)𝑥𝐾1 = 400
2 ≤hourscapacity
3.0 . 10𝑥1 + 15𝑥2 ≤ 450

3.0 . (𝑎2,2 = 10)𝑥
= 15)𝑥2 ≤ 𝐾2 = 450− negativity
𝒙 , 𝒙1 +≥(𝑎𝟎2,2Non𝟏𝟐𝒙𝟏 , 𝒙𝟐 ≥ 𝟎Parametrization of input data
Parametrization of input data of an LP problem allows
one to separate the data from the model. That is, one
can change the values of the data without changing themodel.

Abstraction and generalization of furniture problem… 2
Parametrized LP problem formulation

Prices

1.0
2.0

𝑀𝑎𝑥 𝑏1 𝑥1 + 𝑏2 𝑥2
𝑎1,1 𝑥1 + 𝑎1,2 𝑥2 ≤ 𝐾1

3.0

𝑎2,1 𝑥1 + 𝑎2,2 𝑥2 ≤ 𝐾2

Technology
coefficients

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

2

𝑏1 𝑥1 + 𝑏2 𝑥2 = ෍ 𝑏𝑗 𝑥𝑗
𝑗=1
Resources
capacity2෍ 𝑎𝑖,𝑗 𝑥𝑗 ≤ 𝐾𝑖 (𝑖 = 1,2)𝑗=1

𝑥𝑗 ≥ 0, (𝑗 = 1,2)

Parametrized LP problem formulation

Abstraction and generalization offurniture problem… 2

1.0
2.0

𝑀𝑎𝑥 𝑏1 𝑥1 + 𝑏2 𝑥2
𝑎1,1 𝑥1 + 𝑎1,2 𝑥2 ≤ 𝐾1

General LP problem formulation

3.0

𝑎2,1 𝑥1 + 𝑎2,2 𝑥2 ≤ 𝐾2
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

Objective function
coefficients

2𝑛
Objective
Function

Constraints

Technology
coefficients

𝑀𝑎𝑥 ෍
𝑗=1

𝑏𝑗 𝑥𝑗

𝑏1 𝑥1 + 𝑏2 𝑥2 = ෍ 𝑏𝑗 𝑥𝑗

Decision
Variables

𝑗=1

RHS: righthand side

σ𝑛𝑗=1 𝑎𝑖,𝑗 𝑥𝑗 ≤ 𝐾𝑖 (𝑖 = 1 . . 𝑚)
𝑥𝑗 ≥ 0 (𝑗 = 1. . 𝑛)n = (2) number of decision variables (products)
m = (2) number of constraints (resources)2
Set of indicesfor Constraints

Set of indicesfor Variables෍ 𝑎𝑖,𝑗 𝑥𝑗 ≤ 𝐾𝑖 (𝑖 = 1,2)𝑗=1

𝑥𝑗 ≥ 0, (𝑗 = 1,2)

Linear, integer, binary, mixed programming models
Linear programming problems
Objective function examples:• maximize total revenue• minimize total cost.

Constraint examples:• ≤ constraints are typically considered forcapacity constraints where you don’t want
to exceed capacity available.
• ≥ constraints are used to model demandrequirements where you want to ensure thatat least certain level of demand is satisfied.
• = constraints are used when you want tomatch exactly certain activities with a given
requirement. For example, a job position
can only be filled with one resource, andyou have a set of possible qualified
resources to assign to the job.

𝑛

𝑀𝑎𝑥 (𝑀𝑖𝑛) ෍
𝑗=1

𝑏𝑗 𝑥𝑗

σ𝑛𝑗=1 𝑎𝑖,𝑗 𝑥𝑗 ≤ =, ≥ 𝐾𝑖 (𝑖 = 1 . . 𝑚)
𝑥𝑗 ≥ 0 (𝑗 = 1. . 𝑛)

Linear, integer, binary, mixed programming models
Linear programming
Integer
programmingproblems
problems
Objective function examples:• maximize total revenue• minimize total cost.

Constraint examples:• ≤ constraints are typically considered forcapacity constraints where you don’t want
to exceed capacity available.
• ≥ constraints are used to model demandrequirements where you want to ensure thatat least certain level of demand is satisfied.
• = constraints are used when you want tomatch exactly certain activities with a given
requirement. For example, a job position
can only be filled with one resource, andyou have a set of possible qualified
resources to assign to the job.

𝑛

𝑀𝑎𝑥 (𝑀𝑖𝑛) ෍
𝑗=1

𝑏𝑗 𝑥𝑗

σ𝑛𝑗=1 𝑎𝑖,𝑗 𝑥𝑗 ≤ =, ≥ 𝐾𝑖 (𝑖 = 1 . . 𝑚)
𝑥𝑗 ≥ 0 𝑎𝑛𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 (𝑗 = 1. . 𝑛)

Linear, integer, binary, mixed programming models
BinaryIntegerprogramming
programmingproblems
problems
Objective function examples:• maximize total revenue• minimize total cost.

Constraint examples:• ≤ constraints are typically considered forcapacity constraints where you don’t want
to exceed capacity available.
• ≥ constraints are used to model demandrequirements where you want to ensure thatat least certain level of demand is satisfied.
• = constraints are used when you want tomatch exactly certain activities with a given
requirement. For example, a job position
can only be filled with one resource, andyou have a set of possible qualified
resources to assign to the job.

𝑛

𝑀𝑎𝑥 (𝑀𝑖𝑛) ෍
𝑗=1

𝑏𝑗 𝑥𝑗

σ𝑛𝑗=1 𝑎𝑖,𝑗 𝑥𝑗 ≤ =, ≥ 𝐾𝑖 (𝑖 = 1 . . 𝑚)
𝑥𝑗 𝑖𝑛 {0,1} (𝑗 = 1. . 𝑛)

Linear, integer, binary, mixed programming models
BinaryMixed integer
programming
linear programming
problems
problems
Objective function examples:• maximize total revenue• minimize total cost.

Constraint examples:• ≤ constraints are typically considered forcapacity constraints where you don’t want
to exceed capacity available.
• ≥ constraints are used to model demandrequirements where you want to ensure thatat least certain level of demand is satisfied.
• = constraints are used when you want tomatch exactly certain activities with a given
requirement. For example, a job position
can only be filled with one resource, andyou have a set of possible qualified
resources to assign to the job.

𝑛

𝑀𝑎𝑥 (𝑀𝑖𝑛) ෍
𝑗=1

𝑏𝑗 𝑥𝑗

σ𝑛𝑗=1 𝑎𝑖,𝑗 𝑥𝑗 ≤ =, ≥ 𝐾𝑖 (𝑖 = 1 . . 𝑚)
𝑥𝑗 ≥ 0 (𝑗 = 1. . 𝑛)
𝑥𝑗 ≥ 0 𝑎𝑛𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑗
𝑥𝑗 𝑖𝑛 0,1 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑗Solving MIP Problems
In Mixed Integer linear Programming it is possible to have equivalent formulations of a problem• But the performancea MIP solver
can be drastically different.
In Mixed
Integerof linear
Programming
it is possible to have equivalent
formulations
a problem• This is why when of
formulating
a MIP model, its very important to understand how the MIP algorithms behind the MIP
solver behave.
Hence,thewe willpresent a limited discussionofthe solution
process
associatedwith Linear Programmingand Mixed•• ButperformanceofaMIP
solvercanbedrasticallydifferent.
Integer Linear Programming.

• This is why when formulating a MIP model, its very important tounderstand how the MIP algorithms behind the MIP solver behave.
• Hence, we will present a limited discussion of the solution process
associated with Linear Programming and Mixed Integer Linear
Programming.

Solving MIP Problems
In Mixed Integer linear Programming it is possible to have equivalent formulations of a problem• But the performance of a MIP solver can be drastically different.
• This is why when formulating a MIP model, its very important to understand how the MIP algorithms behind the MIP
solver behave.
• Hence, we will present a limited discussion of the solution process associated with Linear Programming and Mixed
Integer Linear Programming.

Furniture Factory Problem
Graphical interpretation and solution of an LP problem

LP formulation of furniture problem

1.0 . Max revenue = 45𝑥1 + 80𝑥2

2.0

5𝑥1 + 20𝑥2 ≤ 400

Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

Non − negativity

Graphical solution of Furniture Problem … 1

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

5𝑥1 + 20𝑥2 ≤ 400 Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

0𝑥1 Chairs

Non − negativity

Graphical solution of Furniture Problem … 2

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

5𝑥1 + 20𝑥2 ≤ 400 Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

𝑥2
Tables0𝑥1 Chairs

Non − negativity

Graphical solution of Furniture Problem … 3

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

5𝑥1 + 20𝑥2 ≤ 400 Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

𝑥2
TablesTherefore, moving from left to right is the direction for x1 ≥ 0

0

𝑥1 Chairs

Non − negativity

Graphical solution of Furniture Problem … 4

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

5𝑥1 + 20𝑥2 ≤ 400 Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

Therefore, moving from low to high is the direction for x2 ≥ 0
𝑥2
Tables0𝑥1 Chairs

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

Non − negativity

Graphical solution of Furniture Problem … 5

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

5𝑥1 + 20𝑥2 ≤ 400 Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

𝑥2
TablesTherefore, any build plan in this quadrant satisfies theconstraints x1, x2 ≥ 0. For example:(x1=0, x2=40)(x1=40, x2=30)(x1=0, x2=30)(x1=0, x2=10)(x1=10, x2=0)(x1=0, x2=0)(x1=40, x2=0)(x1=80, x2=0)

𝑥1 Chairs

Non − negativity

Graphical solution of Furniture Problem … 6• 5x1 + 20x2 ≤ 400 (mahogany constraint)• 5x1 + 20x2 = 400 (mahogany equation)• Expressing x2 in terms of x1• 20x2 = 400 – 5x1• x2 = 400/20 –(5/20)x1• Hence, x2 = 20 –(1/4)x1• If (x1 = 0) then (x2 = 20)• If (x1 = 1) chairs, then x2 = 20 –(1/4)(x1 = 1) = 19.75 tables• Mahogany tradeoff tables for chairs is (1/4 = 0.25)➗

Graphical solution of Furniture Problem … 7• Let’s graph the equation

x2 = 20 –(1/4)x1
𝑥2
TablesSlope = -1/4
(x1=0, x2=20)

5𝑥1 +20𝑥2 = 400 Mahogany(x1=80, x2=0)(x1=0, x2=0)

𝑥1 Chairs

Graphical solution of Furniture Problem … 8• Mahogany constraint:

5x1 + 20x2 ≤ 400.
• (slack variable) h1 ≥ 0:
amount of unusedmahogany for Production
Plan (x1, x2)

𝑥2
Tables• Equation representing
mahogany constraint

5x1 + 20x2 + h1 = 400(x1=0, x2=20)

5𝑥1 +20𝑥2 = 400 Mahogany
1010(x1=0, x2=0)(x1=80, x2=0)

𝑥1 Chairs

Graphical solution of Furniture Problem … 8• Consider Production Plan(x1=10, x2=10)• Value of slack variable

𝑥2

h1 =
400 – 5(x1=10) –20(x2=10)=150

Tables(x1=0, x2=20)

5𝑥1 +20𝑥2 = 400 Mahogany
10(x1=10, x2=10), h1=150
10(x1=0, x2=0)(x1=80, x2=0)

𝑥1 Chairs

Graphical solution of Furniture Problem … 9• 10x1 + 15x2 ≤ 450 (labor constraint)• 10x1 + 15x2 = 450 (labor equation)• Expressing x2 in terms of x1• x2 = 30 –(2/3)x1• If (x1 = 0) then (x2 = 30)• If (x1 = 1) chair, then x2 = 30 –(2/3)(x1 = 1) = 29.333 tables• Labor tradeoff tables for chairs is (2/3 = 0.667)➗

Graphical solution of Furniture Problem … 10

• Let’s graph the equation

x2 = 30 –(2/3)x1
𝑥2
Tables(x1=0, x2=30)

Slope = -2/31045(x1=0, x2=0)(x1=80, x2=0)

𝑥1 Chairs

Graphical solution of Furniture Problem … 11

• Labor constraint

10x1 + 15x2 ≤ 450• (slack variable) h2 ≥ 0:
amount of unused labor for
production plan (x1, x2)

𝑥2
Tables• Equation representing labor
constraint

10x1 + 15x2 + h2 = 450(x1=0, x2=30)

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)

5𝑥1 +20𝑥2 = 400 (Mahogany)

10(x1=10, x2=0)(x1=0, x2=0)(x1=45, x2=0)(x1=80, x2=0)

𝑥1 Chairs

Graphical solution of Furniture Problem … 11

• Production Plan(x1=10, x2=10)• Slack variable valueh2 =450 – 10(x1=10) –15(x2=10) = 200𝑥2
Tables10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=30)(x1=0, x2=20)(x1=10, x2=10), h2=200

5𝑥1 +20𝑥2 = 400 (Mahogany)

10(x1=10, x2=0)(x1=0, x2=0)(x1=45, x2=0)(x1=80, x2=0)

𝑥1 Chairs

Graphical solution of Furniture Problem … 12

2.0

5𝑥1 + 20𝑥2 ≤ 400 Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

𝑥2
Tables(x1=0, x2=30)

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)

10Feasible Region(x1=10, x2=0)(x1=0, x2=0)

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=45, x2=0)(x1=80, x2=0)

𝑥1 ≥ 0ChairsNon − negativity

Graphical solution of Furniture Problem … 13

2.0

5𝑥1 + 20𝑥2 ≤ 400 Units of mahogany capacity

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor hours capacity

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

Non − negativity

𝑥2
Tables(x1=0, x2=30)• In the theory of linear
programming thefeasible region iscalled a polyhedron.

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)

Polyhedron(x1=10, x2=0)(x1=0, x2=0)

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=45, x2=0)(x1=80, x2=0)

𝑥1 ≥ 0ChairsGraphical solution of Furniture Problem … 14x2 =revenue/80 –(45/80)x1

𝑥2
Tables(x1=0, x2=30)• The objective function:
revenue = 45x1 + 80x2

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)

5𝑥1 +20𝑥2 = 400 (Mahogany)

Feasible Region(x1=45, x2=0)(x1=80, x2=0)

𝑥1 ≥ 0ChairsGraphical solution of Furniture Problem … 14

• If (x1=0, x2=0), thenrevenue is $0.00.

𝑥2
Tables(x1=0, x2=30)

x2 =revenue/80 –(45/80)x1

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)

5𝑥1 +20𝑥2 = 400 (Mahogany)

Feasible Region

Slope = -45/80(x1=0, x2=0)
revenue = $ 0(x1=45, x2=0)

Revenue = 45x1 + 80x2

(x1=80, x2=0)

𝑥1 ≥ 0ChairsGraphical solution of Furniture Problem … 15

= 45(x1=0) + 80(x2=10)= $800

Tables10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)(x1=0, x2=10)
revenue = 800(x1 = 0, x2 = 10)• Generates a revenue𝑥2(x1=0, x2=30)• Production Plan

5𝑥1 +20𝑥2 = 400 (Mahogany)

Feasible Region(x1=45, x2=0)(x1=0, x2=0)
revenue = $ 0

Revenue = 45x1 + 80x2

(x1=80, x2=0)

𝑥1 ≥ 0ChairsGraphical solution of Furniture Problem … 15𝑥2

• Mahogany slack variable:

h1 =400 – 5(x1=0) –20(x2=10)=200

Tables• Labor slack variable:h2 =450 – 10(x1=0) –15(x2=10) = 150(x1=0, x2=30)• 200 units of unusedmahogany capacity

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)(x1=0, x2=10)
revenue = 800

5𝑥1 +20𝑥2 = 400 (Mahogany)

Feasible Region

Revenue = 45x1 + 80x2

(x1=45, x2=0)(x1=80, x2=0)

𝑥1 ≥ 0Chairs• 150 units of unused labor
capacityGraphical solution of Furniture Problem … 16

• How far can we increase theproduction of tables?
• Production Plan𝑥2

(x1=0, x2=20)

Tables

Revenue =45(x1 = 0) + 80(x2=20) =$1,600(x1=0, x2=40)(x1=0, x2=30)

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)
revenue = 1600(x1=0, x2=10)
revenue = 800(x1=0, x2=0)
revenue = 0

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=45, x2=0)(x1=80, x2=0)

𝑥1 ≥ 0ChairsGraphical solution of Furniture Problem … 16

• Can we continue increasing
the production tables?
• Production plan𝑥2

(x1=0, x2=21)

Tables

Revenue =45(x1 = 0) + 80(x2=21) =$1,680• Mahogany slack variable

h1 = 400 – 5(x1=0) –20(x2=21)= -20 !!!
Infeasible(x1=0, x2=30)

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)
revenue = 1600

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=0, x2=0)
revenue = 0(x1=45, x2=0)

Revenue = 45x1 + 80x2

(x1=80, x2=0)

𝑥1 ≥ 0ChairsGraphical solution of Furniture Problem … 17𝑥2
Tables(x1=0, x2=30)

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)
revenue = 1600

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=0, x2=0)
revenue = 0(x1=45, x2=0)

Revenue = 45x1 + 80x2

(x1=80, x2=0)

𝑥1 ≥ 0Chairs• What else we can do?

Graphical solution of Furniture Problem … 17𝑥2
Tables(x1=0, x2=30)

10𝑥1 +15𝑥2 = 450 (Labor)(x1=0, x2=20)
revenue = 1600

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=0, x2=0)
revenue = 0(x1=45, x2=0)

Revenue = 45x1 + 80x2

(x1=80, x2=0)

𝑥1 ≥ 0Chairs• Mahogany equationx2 =20 –(1/4)x1

Graphical solution of Furniture Problem … 18
𝑥2
Tables• How much can we keepincreasing the productionof chairs while keeping the
production of tables ashigh as we can?
• If we build 10 chairs, then:x2 =20 –(1/4)(x1=10)= 17.5 tables.

(x1=0, x2=30)(x1=0, x2=20)
revenue = 1600

10𝑥1 +15𝑥2 = 450 (Labor)(x1=10, x2=17.5)
revenue = 1850

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=0, x2=0)
revenue = 0(x1=45, x2=0)

Revenue = 45x1 + 80x2

(x1=80, x2=0)

𝑥1 ≥ 0Chairs• Mahogany slack variable
h1 =400 – 5(x1=10) –20(x2=17.5) = 0

Graphical solution of Furniture Problem … 18

• Production plan(x1=10, x2=17.5)• Revenue =45(x1=10) + 80(x2=17.5)= $1,850𝑥2
Tables• Labor slack variableh2 =450 – 10(x1=10) –15(x2=17.5) = 87.5
(x1=0, x2=30)(x1=0, x2=20)
revenue = 1600

10𝑥1 +15𝑥2 = 450 (Labor)(x1=10, x2=17.5)
revenue = 1850

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=0, x2=0)
revenue = 0(x1=45, x2=0)(x1=80, x2=0)

𝑥1 ≥ 0ChairsGraphical solution of Furniture Problem … 19𝑥2
Tables(x1=0, x2=30)(x1=0, x2=20)
revenue = 1600

• This happens when theequation that defines the
mahogany constraintintersects with theequation that defines thelabor constraint. The
associated production plan
is found by solving thesesystem of equations.

10𝑥1 +15𝑥2 = 450 (Labor)(x1=24, x2=14)
revenue = 2200

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=0, x2=0)
revenue = 0(x1=45, x2=0)• Observe that when the
production plan moving
along the mahoganyequation hits the labor
equation, we cannot move
any further.

(x1=80, x2=0)

𝑥1 ≥ 0Chairs• STOP, labor constraint
limits production plan.

Graphical solution of Furniture Problem … 19

Mahogany

5𝑥1 +20𝑥2 = 400
Labor

𝑥2

10𝑥1 +15𝑥2 = 450

Tables• Production Plan:• 24 chairs• 14 tables.
(x1=0, x2=30)(x1=0, x2=20)
revenue = 1600

• Revenue =45(x1=24) +80(x2=14) = $2,200

10𝑥1 +15𝑥2 = 450 (Labor)(x1=24, x2=14)
revenue = 2200

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=0, x2=0)
revenue = 0(x1=45, x2=0)(x1=80, x2=0)

𝑥1 ≥ 0ChairsGraphical solution of Furniture Problem … 19

Production Plan

(x1 =24, x2=14) is
optimal𝑥2
Tables

Efficient Production Plan
Mahogany slack variable

h1 = 400 – 5(x1=24) –20(x2=14)= 0
Labor slack variable(x1=0, x2=30)(x1=0, x2=20)
revenue = 1600

h2 = 450 – 10(x1=24) –15(x2=14) = 0

10𝑥1 +15𝑥2 = 450 (Labor)(x1=24, x2=14)
revenue = 2200

5𝑥1 +20𝑥2 = 400 (Mahogany)(x1=0, x2=0)
revenue = 0(x1=45, x2=0)(x1=80, x2=0)

𝑥1 ≥ 0ChairsBreakFundamental theorem of linear programming ..
𝑥2
Tables10𝑥1 +15𝑥2 = 450 (Labor)
20

5𝑥1 +20𝑥2 = 400 (Mahogany)

Polyhedron(0,0)

𝑥1 ≥ 045

𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 45𝑥1 +80𝑥2

Chairs• Definitions:• A solution of an LP
problem is a set of valuesof the decision variables
that satisfies all theconstraints of the problem
defined by the polyhedron.
• A corner point solution isa vertex of the polyhedrondefining the feasible
region of the LP problem.
• An optimal solution is asolution of the LP problem
that cannot be improved.
• Theorem:• If a linear programming
problem has an optimal
solution, there is at least
one optimal solution that isa corner point solution.

Fundamental theorem of linear programming .. 2 • Theorem:• If a linear programming
problem has an optimal
solution, there is at least
one optimal solution that isa corner point solution.

𝑥2
Tables• Initial corner point solution
P1 =(0 chairs, 0 tables)(Labor)Polyhedron

P1(Mahogany)
45(Revenue)𝑥1 ≥ 0ChairsFundamental theorem of linear programming .. 2 • Theorem:• If a linear programming
problem has an optimal
solution, there is at least
one optimal solution that isa corner point solution.

𝑥2
Tables• Initial corner point solution
P1 =(0 chairs, 0 tables)• Adjacent corner point
solution
P2 =(0 chairs, 20 tables)(Labor)P2

Polyhedron

P1(Mahogany)
45(Revenue)𝑥1 ≥ 0ChairsFundamental theorem of linear programming .. 2 • Theorem:• If a linear programming
problem has an optimal
solution, there is at least
one optimal solution that isa corner point solution.

𝑥2
Tables• Initial corner point solution
P1 =(0 chairs, 0 tables)• Adjacent corner point
solution
P2 =(0 chairs, 20 tables)(Labor)• Adjacent corner point
solution
P3 =(24 chairs, 14 tables)

P2
P3

Polyhedron

P1(Mahogany)𝑥1 ≥ 045(Revenue)

ChairsFundamental theorem of linear programming .. 2 • Theorem:• If a linear programming
problem has an optimal
solution, there is at least
one optimal solution that isa corner point solution.

𝑥2
Tables• Initial corner point solution
P1 =(0 chairs, 0 tables)• Adjacent corner point
solution
P2 =(0 chairs, 20 tables)(Labor)• Adjacent corner point
solution
P3 =(24 chairs, 14 tables)

P2
P3

Polyhedron

P1(Mahogany)𝑥1 ≥ 045(Revenue)

ChairsFundamental theorem of linear programming .. 3

• New oportunity toincrease revenue

𝑥2
Tables30(Labor)P2
P3

Polyhedron

P1• Significant increase in
the price (b1) of chairs.

(Mahogany)
45

Revenue = 𝑏1 𝑥1 +80𝑥2

𝑥1 ≥ 0ChairsFundamental theorem of linear programming .. 3𝑥2
Tables30(Labor)P2
P3

Polyhedron
P4
P1

45

Revenue = 𝑏1 𝑥1 +80𝑥2(Mahogany)𝑥1 ≥ 0Chairs• The new Production Plan
P4 = (45 chairs, 0 tables)is optimalFundamental theorem of linear programming .. 4 • Theorem:
Vertex𝑥2
Tables• If a linear programming
problem has an optimal
solution, there is at least
one optimal solution that isa corner point solution.

Equations(0,0)

x1 = 0 and x2 = 0(0,20)

x1= 0 and 5x1 +20x2= 400 (mahogany)(24,14) 5x1 + 20x2 = 400 (mahogany) and 10x1 +15x2 = 450 (labor)(45,0)

30

10x1 + 15x2 = 450 (labor) and x2=0

(Labor)Revenue = 𝑏1 𝑥1 +𝑏2 𝑥2

P2

P3

Polyhedron(Mahogany)
P4

P1

45

80

𝑥1 ≥ 0ChairsFundamental theorem of linear programming .. 5 • Theorem:
Vertex𝑥2
Tables• If a linear programming
problem has an optimal
solution, there is at least
one optimal solution that isa corner point solution.

Equations(0,0)

x1 = 0 and x2 = 0(0,20)

x1= 0 and 5x1 +20x2= 400 (mahogany)(24,14) 5x1 + 20x2 = 400 (mahogany) and 10x1 +15x2 = 450 (labor)(45,0)

10x1 + 15x2 = 450 (labor) and x2=0
Infeasible points(0,30)
30(Labor)Equationsx1 = 0 and labor equation(80, 0) mahogany and x2 = 0
Revenue = 𝑏1 𝑥1 +𝑏2 𝑥2

P2

P3

Polyhedron(Mahogany)
P4

P1

45

80

𝑥1 ≥ 0ChairsEnumeration approach
Enumeration of solutions of the system of equations for the furniture problem
Points of interest

Vertex of the polyhedron

Objective function value. Revenue = 45x1 + 80x2

(0,0)

Yes (feasible)

0 = 45*0 + 80*0(0,20)Yes (feasible)

1600 = 45*0 + 80*20(24,14)

Yes (feasible)

2200 = 45*24 + 80*14 Optimal!!

(45,0)Yes (feasible)

2025 = 45*45 + 80*0(0,30)No (infeasible)

2400 = 45*30 + 80*30(80,0)No (infeasible)

3600 = 45*80 + 80*0

How many solutions can we have?
• Let’s ask the question: How many points of interest an LP problem
would have with n variables and n constraints?
Num of variables

Num of constraints

Num of points of interest

10

10

184,756

50

50

100

100

~ 𝟏𝟎𝟓𝟖150

150~ 𝟏𝟎𝟖𝟖500

500~ 𝟏𝟎𝟐𝟗𝟗

𝟖𝟖~ 𝟏𝟎~ 𝟏𝟎𝟐𝟗Is there a way that
we canThis number
istraverse
largervertices in thethan the numberof atoms
polyhedron in a(~ 1080) inmore
the efficient
known
way?

universe !!

An LP with 500 variables and constraints is considered a very small LP problem.

Is there a way that we can traverse vertices in thepolyhedron in a more efficient way?

Simplex Method !!!

Simplex method
Overview

Linear Programming

Furniture problem LP problem formulation
1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

𝑥2

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor

Tables30

5𝑥1 + 20𝑥2 ≤ 400 Mahogany

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎(Labor)P2

Polyhedron(Mahogany)
P1

45(Revenue)80

𝑥1 ≥ 0ChairsNon − negativity

Linear Programming

Furniture problem LP problem formulation
1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

𝑥2

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor

Tables30

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎(Labor)P2

Polyhedron(Mahogany)
P1

5𝑥1 + 20𝑥2 ≤ 400 Mahogany

45(Revenue)80

𝑥1 ≥ 0ChairsNon − negativity

Linear Programming

Furniture problem LP problem formulation
1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

𝑥2

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor

Tables30

𝒙𝟏 , 𝒙𝟐 ≥ 𝟎(Labor)P2

Polyhedron(Mahogany)
P1

5𝑥1 + 20𝑥2 ≤ 400 Mahogany

45

80(Revenue)𝑥1 ≥ 0ChairsNon − negativity

Linear Programming/Simplex Method
We call the formulation of an LP problem the original LP problem

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

5𝑥1 + 20𝑥2 ≤ 400

Mahogany

3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎

Non − negativity

Linear Programming/Simplex Method
The original LP problem in a standard form is:

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0

5𝑥1 + 20𝑥2 + ℎ1 = 400

mahogany

3.0 . 10𝑥1 + 15𝑥2 + ℎ2 = 450 Labor

𝒙𝟏 , 𝒙𝟐 , ℎ1, ℎ2 ≥ 𝟎

Non − negativity

Original LP problem.
1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0 5𝑥1 + 20𝑥2 ≤ 400 mahogany
3.0 . 10𝑥1 + 15𝑥2 ≤ 450 Labor
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 Non − negativity

Linear Programming/Simplex Method .. 2𝑥2
TablesFurniture problem standard form

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0 5𝑥1 + 20𝑥2 + ℎ1 = 400 Mahogany
3.0 . 10𝑥1 + 15𝑥2 + ℎ2 = 450 Labor
𝒙𝟏 , 𝒙𝟐 , 𝒉𝟏, 𝒉𝟐 ≥ 𝟎 Non − negativity

h1 = 400 –5(x1=0) -20(x2=0) = 400
h2 = 450 –10(x1=0) -15(x2=0) = 450
x1=0, x2=0, h1 = 400, h2 = 45030(x1=0, x2=0) initial solution
Revenue = 0

Feasible solution(Labor)20

Polyhedron(Mahogany)
(0,0)

45

(Revenue)80

𝑥1 ≥ 0ChairsLinear Programming/Simplex Method .. 2

Furniture problem standard form

𝑥2
Tablesx1=0, x2=0, h1 = 400, h2 = 450

Feasible solution

h1, h2 Basic variables
x1, x2 Non basic variables
x1=0, x2=0, h1 = 400, h2 = 450 Basic Feasible solution
30(Labor)20

Polyhedron(Mahogany)
(0,0)

45

(Revenue)80

𝑥1 ≥ 0Chairs

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0 5𝑥1 + 20𝑥2 + ℎ1 = 400 Mahogany
3.0 . 10𝑥1 + 15𝑥2 + ℎ2 = 450 Labor
𝒙𝟏 , 𝒙𝟐 , 𝒉𝟏, 𝒉𝟐 ≥ 𝟎 Non − negativity

Linear Programming/Simplex Method .. 3𝑥2
TablesFurniture problem standard form

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0 5𝑥1 + 20𝑥2 + ℎ1 = 400 Mahogany
3.0 . 10𝑥1 + 15𝑥2 + ℎ2 = 450 Labor
𝒙𝟏 , 𝒙𝟐 , 𝒉𝟏, 𝒉𝟐 ≥ 𝟎 Non − negativity

A basic solution is defined by the values of the basic
and non basic variables.
Production Plan (x1=0, x2=30)
h1 = 400 –5(x1=0) -20(x2=30) = -200
h2 = 450 –10(x1=0) -15(x2=30) = 0
x1=0, x2=30, h1 = -200, h2 = 0 Basic infeasible solution

30(Labor)20

Polyhedron(Mahogany)
(0,0)

45

80

𝑥1 ≥ 0ChairsLinear Programming/Simplex Method .. 4𝑥2

1.0 . Max revenue = 45𝑥1 + 80𝑥2
2.0 5𝑥1 + 20𝑥2 + ℎ1 = 400 Mahogany
3.0 . 10𝑥1 + 15𝑥2 + ℎ2 = 450 Labor
𝒙𝟏 , 𝒙𝟐 , 𝒉𝟏, 𝒉𝟐 ≥ 𝟎 Non − negativity

LP problem in a canonical form with respect to thebasic variables (h1, h2) :Tables

30

Furniture problem standard form

1.0
2.0
3.0

𝑀𝑎𝑥 𝑧 = 45𝑥1 + 80𝑥2 + 0ℎ1 + 0ℎ2ℎ1 = 400 − 5𝑥1 − 20𝑥2 Unused mahoganyℎ2 = 450 − 10𝑥1 − 15𝑥2 Unused labor
Non-negativity
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0(Labor)20

Polyhedron(Mahogany)
(0,0)

45

(Revenue)80

𝑥1 ≥ 0ChairsReduced costs:
Objective funcion
coefficients of non basic
variables (x1, x2)

Linear Programming/Simplex Method .. 5

Furniture problem canonical form

Current basic feasible solution:
h1=400 and h2=450, x1=0 and x2=0
Revenue: z=0𝑥2
TablesMake tables, x2 > 0

x2 enter the basis(Labor)20

Polyhedron(Mahogany)
(0,0)

45

(Revenue)

𝑀𝑎𝑥 𝑧 = 45𝑥1 + 80𝑥2 + 0ℎ1 + 0ℎ2ℎ1 = 400 − 5𝑥1 − 20𝑥2 Mahogany

3.0ℎ2 = 450 − 10𝑥1 − 15𝑥2 Labor
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0

Max {45,80} =80 Table price

30

1.0
2.0

80

𝑥1 ≥ 0ChairsNon-negativity

Linear Programming/Simplex Method .. 5

Furniture problem canonical form

How many tables (x2) can we make?
𝑥2

h1 = 400 – 20x2
h2 = 450 – 15x2

Tables(Labor)20

Polyhedron(Mahogany)
(0,0)

45

(Revenue)

𝑀𝑎𝑥 𝑧 = 45𝑥1 + 80𝑥2 + 0ℎ1 + 0ℎ2ℎ1 = 400 − 5𝑥1 − 20𝑥2 Mahogany

3.0ℎ2 = 450 − 10𝑥1 − 15𝑥2 Labor
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0

400/20 = 20 tables
450/15 = 30 tables

30

1.0
2.0

80

𝑥1 ≥ 0ChairsNon-negativity

Linear Programming/Simplex Method .. 5

Furniture problem canonical form

If x2 =30, h1 = 400 – 20(x2=30) = -200!!!!
𝑥2

Min ratio test {400/20 = 20, 450/15 = 30} = 20 tables

Tablesh1 leaves the basis
Pivoting: Express problem canonical form (x2, h2)

30(Labor)20

Polyhedron(Mahogany)
(0,0)

45

(Revenue)80

𝑥1 ≥ 0Chairs1.0
2.0

𝑀𝑎𝑥 𝑧 = 45𝑥1 + 80𝑥2 + 0ℎ1 + 0ℎ2ℎ1 = 400 − 5𝑥1 − 20𝑥2 Mahogany

3.0ℎ2 = 450 − 10𝑥1 − 15𝑥2 Labor
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0

Non-negativity

Linear Programming/Simplex Method (Pivoting) .. 6

1.0

𝑀𝑎𝑥 𝑧 = 45𝑥1 + 80𝑥2 + 0ℎ1 + 0ℎ2

2.0ℎ1 = 400 − 5𝑥1 − 20𝑥2

3.0

ℎ2 = 450 − 10𝑥1 − 15𝑥2
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0

In equation 2.0, express x2 in terms of x1 and h1

2.0

𝑥2 = 20 − 1ൗ4 𝑥1 − 1ൗ20 ℎ1

Linear Programming/Simplex Method (Pivoting) .. 6
In equation 2.0, express x2 in terms of x1 and h1
2.0

𝑥2 = 20 − 1ൗ4 𝑥1 − 1ൗ20 ℎ1

We substitute the value of x2 in equation (3.0)
3.0 ℎ2 = 450 − 10𝑥1 − 15(𝑥2 = 20 − 1ൗ4 𝑥1 − 1ൗ20 ℎ1 )= 150 − 25ൗ4 𝑥1 + 3ൗ4 ℎ1
Substitute the value of x2 in (1.0), the objective function
1.0

𝑧 = 45𝑥1 + 80 20 − 1ൗ4 𝑥1 − 1ൗ20 ℎ1 + 0ℎ1 + 0ℎ2= 1600 + 25𝑥1 + 0𝑥2 − 4ℎ1 + 0ℎ2

1.0
2.0
3.0

𝑀𝑎𝑥 𝑧 = 45𝑥1 + 80𝑥2 + 0ℎ1 + 0ℎ2ℎ1 = 400 − 5𝑥1 − 20𝑥2
ℎ2 = 450 − 10𝑥1 − 15𝑥2
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0

Linear Programming/Simplex Method .. 7
Furniture LP problem in a canonical form with respect to the basic variables (x2, h2).

𝑥2

1.0 𝑀𝑎𝑥 𝑧 = 1600 + 25𝑥1 + 0𝑥2 − 4ℎ1 + 0ℎ2
2.0𝑥2 = 20 − 1ൗ4 𝑥1 − 1ൗ20 ℎ1 Production of tables

Tables3.030ℎ2 = 150 − 25ൗ4 𝑥1 + 3ൗ4 ℎ1 Unused labor capacity
Non-negativity
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0(Labor)20

Pivoting
Polyhedron(Mahogany)
(0,0)

45

(Revenue)

80(Revenue)=1600

𝑥1 ≥ 0ChairsLinear Programming/Simplex Method (Pivoting) .. 8

1.0 𝑀𝑎𝑥 𝑧 = 1600 + 25𝑥1 + 0𝑥2 − 4ℎ1 + 0ℎ2
2.0𝑥2 = 20 − 1ൗ4 𝑥1 − 1ൗ20 ℎ1 Production of tables
3.0ℎ2 = 150 − 25ൗ4 𝑥1 + 3ൗ4 ℎ1 Unused labor capacity
Non-negativity
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0
Simplex method: iteration 2
Step1: x1 enters the basis.

Step2: minimum ratio test, 𝑚𝑖𝑛{20 ∕ (1 ∕ 4)=80 ,150 ∕ (25 ∕ 4)=24 }=24. h2 leaves
the basis
Step3: Pivoting express problem in canonical form with respect to (x2, x1)

Linear Programming/Simplex Method (Pivoting) .. 9In equation 3.0, express x1 in terms of h1 and h2

1.0 𝑀𝑎𝑥 𝑧 = 1600 + 25𝑥1 + 0𝑥2 − 4ℎ1 + 0ℎ2
2.0𝑥2 = 20 − 1ൗ4 𝑥1 − 1ൗ20 ℎ1
3.0ℎ2 = 150 − 25ൗ4 𝑥1 + 3ൗ4 ℎ1
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0

3.0

𝑥1 = 24 + 3Τ25 ℎ1 − 4Τ25 ℎ2

We substitute the value of x1 in equation (2.0)
2.0 𝑥2 = 14 − 2ൗ25 ℎ1 + 1ൗ25 ℎ2

Substitute the value of x1 in (1.0), the objective function𝑧 = 2200 + 0𝑥1 + 0𝑥2 − 1ℎ1 − 4ℎ2

Linear Programming/Simplex Method (Pivoting) .. 10
Furniture LP problem in a canonical form with respect to the basic variables (x2, x1).

1.0 𝑀𝑎𝑥 𝑧 = 2200 + 0𝑥1 + 0𝑥2 − 1ℎ1 − 4ℎ2𝑥2
Tables

2.0 𝑥2 = 14 − 2ൗ25 ℎ1 + 1ൗ25 ℎ2 Production of tables
3.0 𝑥1 = 24 + 3Τ25 ℎ1 − 4Τ25 ℎ2 Production of chairs
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0

30(Labor)Pivoting
20

Polyhedron(Mahogany)
(0,0)

45

80

(Revenue)(Revenue)=2200

𝑥1 ≥ 0ChairsNon-negativity

Linear Programming/Simplex Method.. 11

1.0 𝑀𝑎𝑥 𝑧 = 2200 + 0𝑥1 + 0𝑥2 − 1ℎ1 − 4ℎ2

Simplex method: iteration 3.

𝑥2
Tables

2.0 𝑥2 = 14 − 2ൗ25 ℎ1 + 1ൗ25 ℎ2
3.0

Step 1: reduced costs (h1, h2) ≤ 0. Recall that the
reduced costs are the coefficients of the non basic.

𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0

Objective value cannot increase. STOP
Basic feasible solution (x1=24, x2=14, h1=0, h2=0), is
optimal.

30(Labor)20

Polyhedron(Mahogany)
(0,0)

45

80

(Revenue)=2200

𝑥1 = 24 + 3Τ25 ℎ1 − 4Τ25 ℎ2

𝑥1 ≥ 0ChairsSummary of simplex method for the maximization case
1. Transform the original LP problem into the standard form. Consider an initial basic feasible
solution.
2. Express the LP problem in a canonical form with respect to the current basic feasible
solution.
3. If the reduced costs of all the non basic variables are ≤ 0, STOP –the current basic feasible
solution is optimal. Else, choose a non basic variable with the largest positive reduced costto enter the basis.
4. Consider the column vector of the non basic variable entering the basis. If all thecoefficients of this column vector are positive, the entering non basic variable can bearbitrarily large, hence the LP problem is unbounded.
i. Assume that the column vector has at least one negative component.
ii. Apply the minimum ratio test over the equations where the entering non basic variable
has negative coefficients to determine the basic variable that will leave the basis.
iii.(Pivoting) Go to 2.) to determine the new basic solution.

Modeling and solving LP problems
Gurobi Python API

Furniture Problem: solved with Gurobi … 1

This command imports the Gurobi functions and classes.
The Model() constructor creates a model object f . The name of this new model is ‘Furniture’.
This new model f initially contains no decision variables, constraints, or objective function.
This method adds a decision variable to the model object f, one by one; i.e. x1 and then x2.
The argument of the method gives the name of added decision variable. The default values
are applied here; i.e. the decision variables are of type continuous and non-negative, with noupper bound.
This method adds the objective function to the model object f. The firstargument is a linear expression (LinExpr) and the second argument defines
the sense of the optimization.
A linear expression object (LinExpr) consists of a constant term, plus a sum
This method adds a constraint to the model object f and considers a linearof coefficient-variables pairs that capture the linear terms.
expression (LinExpr) as the left-hand-side of the constraints, the sense of
the constraint, and its capacity value. The last argument gives the name of
the constraint.

Furniture Problem: solved with Gurobi … 2This method runs the optimization engine to solve the LP problem in the model object f

Minimum and maximum absolute value of the matrix of technology coefficients.
Minimum and maximum absolute value of the objective function coefficients.
Minimum and maximum absolute value of the upper and lower bound values.
Minimum and maximum absolute value of the RHS values.

Simplex method iteration information.
An optimal solution was found.

This method retrieves a list of all variables in the model object f
The print function displays the decision variable names and solution value

The print function displays the objective function value of the model object f

Optimal Production PlanFurniture Problem (abstracted): solved with Gurobi .. 1

Parametrized furniture LP
problem formulation

Furniture Problem: Parametrized solved with Gurobi .. 2

The multidict function returns a list which maps
each resource (key) to its capacity value.

This multidict function returns a list which maps
each product (key) to its price value.

This dictionary has a 2-tuple as a key, mapping theresource required by a product with its quantity per.

Furniture Problem: Parametrized solved with Gurobi .. 3The Model() constructor creates a model
object f .

This method adds decision variables to themodel object f, and returns a Gurobi
tupledict object (make) that contains thevariables recently created.
The first argument (products) provides theindices that will be used as keys to accessthe variables in the returned tupledict. The
last argument gives the name ‘make’ to thedecision variables. The decision variables
are of type continuous and non-negative,
with no upper bound.

Furniture Problem: Parametrized solved with Gurobi .. 4This method adds constraints to the model object f.

Furniture Problem: Parametrized solved with Gurobi .. 5

This method adds the objective function to the model object f.
The first argument is a linear expression which is generated
by the (prod) method. The (prod) method is the product of theobject (revenue) with the object (make) for each product p in
the set (products). The second argument defines the sense of
the optimization.

Furniture Problem: Parametrized solved with Gurobi .. 6

Furniture Problem: Parametrized solved with Gurobi .. 7

This method runs the optimization engine
to solve the LP problem in the model
object f

Optimal Production PlanFinal Remarks• The simplex
methoditerates offrom
one basic
feasiblesolutiongeometric
interpretationa basic
feasiblesolutionis thattoitanother,is aalwaysto improvethe valueof the solution,
furtherof thesolutiontrying
to a setof equations
that definesa corneruntil
pointnot(vertex)improvements
be done. the feasible region of an LP problem.
polyhedron thatcan
determines𝑥2
Tables30(Labor)Pivoting
20

Pivoting

Polyhedron(Mahogany)
(0,0)

45

80

(Revenue)=2200

𝑥1 ≥ 0ChairsSensitivity analysis of LP problems
Gurobi Python API

Furniture Problem: economic interpretation
Economic interpretation in Linear Programming models• Solving LP problems provides more information than only the values of the decisionvariables and the value of the objective function.

• Associated with an LP optimal solution there are shadow prices(a.k.a. dual variables, or marginal values) for the constraints.
• The shadow price of a constraint associated with the optimal solution, represents
the change in the value of the objective function per unit of increase in the righthand side value of that constraint.
• There are shadow prices associated with the non-negativity constraints. Theseshadow prices are called the reduced costs.

Furniture Problem: economic interpretation .. 2
• For example, suppose the labor capacity is increased from 450 hours to 451 hours.
What is the increase in the objective function value from such increase?
• Since the constraints on mahogany capacity (2.0) and labor capacity (3.0) define theoptimal solution, we can solve the following system of equations

5𝑥1 +20𝑥2 = 400 Mahogany capacity
10𝑥1 + 15𝑥2 = 451 Labor capacity• The new values of the decision variables are: chairs (x1) = 24.16, tables (x2) = 13.96• The new value of the objective function (revenue) is = $2,204• The shadow price associated with the labor capacity is $2,204 - $2,200 = $4. Thatis, we can get $4 of increased revenue per hour of increase in labor capacity.
• Remark: The shadow price value of $4 remains constant over a range of valuechanges of the mahogany capacity. The calculation of this range is beyond thescope of this course.

Furniture Problem: economic interpretation .. 3
• Similarly, we can compute the shadow price of the mahogany constraint by solving
the following system of equations

5𝑥1 +20𝑥2 = 401 Mahogany capacity
10𝑥1 + 15𝑥2 = 450 Labor capacity• The new values of the decision variables are: chairs (x1) = 14.08, tables (x2) = 23.88• The new value of the objective function (revenue) is = $2,201• The shadow price associated with the mahogany capacity is $2,201 - $2,200 = $1.
That is, we can get $1 of increased revenue per unit of increase in mahogany
capacity.
• Remark: The shadow price value of $1 remains constant over a range of valuechanges of the labor capacity.

Furniture Problem: simplex method revisited
The LP problem in a canonical form with respect to the optimal basic variables (x1, x2) is

𝑀𝑎𝑥 𝑧 = 2200 + 0𝑥1 + 0𝑥2 − 1ℎ1 − 4ℎ2
2.0 𝑥2 = 14 − 2ൗ25 ℎ1 + 4ൗ25 ℎ2
3.0 𝑥1 = 24 + 3Τ25 ℎ1 − 4Τ25 ℎ2
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0
andh2 are thethe valueslack ofvariables
associatedwithmahogany• Remarks: Recall
notice that ifh1weincreaseh1 (unused
capacityof themahogany)
by capacity
one theconstraint
andwilllabortotal revenue
be capacity
reduced constraint,
by $1. If werespectively.
increase the value of h2 (unused capacity of labor) by
one the total revenue will be reduced by $4.
• The interpretation of the slack variables is the amount of resource capacity not consumed byof chairsshow
and ustables.
• the
Ourproduction
previous analysis
that the shadow price of mahogany is $1 and the one of labor is$4 !!!!
• The optimal solution is• Revenue = $2,200, chairs (x1) = 24, tables (x2)= 14• Conclusion: The simplex method automatically give us the shadow prices of the resources.
• Slack variable (h1) of mahogany constraint = 0, and• Slack variable (h2) of labor constraint = 0

Furniture Problem: solved with GurobiThis method adds constraints to the model object f. We store the constraints generated in
an object called (res).

For each resource constraint in the dictionary (res), check if its associated shadow price isgreater than zero. Then print the resource constraint name and the resource constraint shadow
price.
Recall that the object(res) stores all theinformation related to theconstraints of the model f.

Furniture Problem: economic interpretation .. 4
• Is it profitable to make a third product, like desks?
• Assume that the price of the desk is $110,• and the desk consumes 15 units of mahogany and 25 units of labor• The previous python code has parametrized the Furniture LP model, i.e. the model
formulation does not depend on the data of the problem. Therefore, we just generate a
new set of data that includes the new product information

Furniture Problem: economic interpretation .. 5
• The new LP model isFurniture Problem: economic interpretation .. 6

It is not profitable to produce
desks. The optimal solution
remains the same.

The shadow prices of theresources remain the same.

Furniture Problem: economic interpretation .. 7
• Notice that we can use the shadow price information of the resources to check if it is worth it tomake desks.
• The shadow price of the mahogany capacity constraint is $1• The shadow price of the labor capacity constraint is $4• Let’s compute the opportunity cost of making one desk and compare it with the price of adesk. If this opportunity cost is greater than the price, then it is not worth it to make desks.
• The opportunity cost can be computed by multiplying the units of mahogany capacity that
one desk built consumes by the shadow price of mahogany capacity, and multiplying thehours of labor capacity that one desk built consumes by the shadow price of labor capacity:• That is, ($1)*15 (units of mahogany) + ($4)*25 (hours of labor) = $115 > $110
• Therefore, investing resources to produce desks, otherwise used to produce chairs and tables,
is not profitable.

Multiple optimal solutions
Gurobi Python API

Furniture Problem

New business conditions• The data scientist in charge of
production planning for thefurniture factory uses machinelearning to predict that themarket price of a chair is now$50 and the market price of atable is $75.
• The equation of the objectivefunction under these new
business conditions is:revenue = 50x1 + 75x2.

Furniture Problem

New business conditions• In this case, the production
plan P1 of building 24 chairs
and 14 tables and the plan P2of building 45 chairs and 0
tables are both optimal.

Furniture problem standard form
𝑥2

1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 50𝑥1 + 75𝑥2
Units of mahogany capacity
2.0 5𝑥1 + 20𝑥2 + ℎ1 = 400
3.0 10𝑥1 + 15𝑥2 + ℎ2 = 450 Labor hours capacity
𝑥1 , 𝑥2 , ℎ1 , ℎ2 ≥ 0 Non-negativity

Tables30• The production plan P1 isdefined by the mahogany andlabor constraints. The
associated optimal basic
feasible solution is x1=24,
x2=14, h1=0, h2=0.

(Labor)P1

20(x1=24,x2=14)

Polyhedron(Mahogany)
(0,0)

80

(x1=45,P2
x2=0)(Revenue= 50X1 + 75 X2)

𝑥1 ≥ 0Chairs• The production plan P2 isdefined by the labor and a
non-negativity constraint (x2 =0), i.e. no tables
are built. The associatedoptimal basic feasible solution
is x1=45, x2=0, h1=175, h2=0.

Modified Furniture Problem: solved with Gurobi … 1

priceParametrized furniture LP
problem formulationPrice

New data, same model formulation

Modified Furniture Problem: solved with Gurobi … 2

Gurobi found one of the optimal solutions ... P2

Notice that the shadow price of the resource mahogany
for this alternative optimal solution is zero,… the marginal value of mahogany for this optimal
solution is zero.

Reduced cost of the non basic variable (tables) is zero.
This means that if we produce more tables (and produce
less chairs) the revenue generated remains the same.

Furniture Problem: simplex method revisited .. 1
New (original) LP problem

𝑀𝑎𝑥 𝑧 = 50𝑥1 + 75𝑥2
𝑠. 𝑡. 5𝑥1 + 20𝑥2 ≤ 400
10𝑥1 + 15𝑥2 ≤ 450
𝑥1, 𝑥2 ≥ 0

The LP problem in a standard form is
𝑀𝑎𝑥 𝑧 = 50𝑥1 + 75𝑥2 + 0ℎ1 + 0ℎ2
𝑠. 𝑡. 5𝑥1 + 20𝑥2 + ℎ1 = 400
10𝑥1 + 15𝑥2 + ℎ2 = 450
𝑥1, 𝑥2, ℎ1, ℎ2 ≥ 0

LP problem in canonical form with respect to the
optimal basic variables (x1, h1) found by Gurobi:

𝑀𝑎𝑥 𝑧 = 2,250 + (0𝑥1 + 0ℎ1) + (0𝑥2 − 5ℎ2)
Non basic variablesℎ1 = 175 − 25ൗ2 𝑥2 + 1ൗ2 ℎ2 (2.0)
𝑥1 = 45 − 3ൗ2 𝑥2 − 1ൗ10 ℎ2(3.0)
𝑥1, 𝑥2, ℎ1, ℎ2 ≥ 0
The reduced cost of non basic variable x2 is zero,hence if we increase its value, the optimal objectivefunction value does not change. Let’s decide whichbasic variable should become non basic (value ofzero) by computing the minimum ratio test:
𝑚𝑖𝑛 175Τ 25Τ2 = 14 , 45Τ 3Τ2 = 30 = 14;
therefore h1 will become non basic variable. Hence,
we pivot on constraint (2.0) and the column ofvariable x2.

Furniture Problem: simplex method revisited .. 2
LP problem in canonical form with respect to the basic variables (x1, x2):
𝑀𝑎𝑥 𝑧 = 2,250 + 0ℎ1 − 5ℎ2
𝑥2 = 14 − 2ൗ25 ℎ1 + 1ൗ25 ℎ2
𝑥1 = 24 − 3ൗ25 ℎ1 − 4ൗ25 ℎ2
𝑥1, 𝑥2, ℎ1, ℎ2 ≥ 0

(2.0)
(3.0)

Modeling Opportunity
From the mathematical model point of view, we have two alternative optimal solutions S1= (x1 =24, x2 =14, h1=0,
h2= 0) and S2 = (x1 =45, x2 =0, h1= 175, h2 = 0), both with a maximum total revenue of $2,250.
The data scientist points out that from the business perspective, the “optimal” solution S1 is preferred to the“optimal” solution S2, because the latter solution wastes 175 units of mahogany.

The data scientist decides to modify the LP model by now interpreting the slack variables as the amount ofwasted resources, and defines the new decision variables:
x3 is the amount of unused mahogany and x4 is the amount of unused labor.
The data scientists uses machine learning to predict that the per unit inventory carrying cost of mahogany is $1 ,and the unused per hour labor cost is $2. Then, the new LP model formulation is:Furniture Problem: simplex method revisited .. 2
Modeling Opportunity
From the mathematical model point of view, we have two alternative optimal solutions S1= (x1 =24, x2 =14, x3 = x4 = 0) and S2 = (x1 =45, x2 =0, x3 = 175, x4 = 0), both with a maximum total
revenue of $2,250.
The data scientist notice that from the business perspective, the “optimal” solution S1 is preferred to “optimal” solution S2, because with the latter solution is wasting 175 units of mahogany.
The data scientist decides to modify the LP model by now interpreting the slack variables as the amount of wasted resources, and defines the new decision variables:
x3 is the amount of unused mahogany and x4 is the amount of unused labor.

The data scientists using machine learning estimates that the per unit inventory carrying cost of mahogany is $1 , and the unused per hour labor cost is $2. Then, the new LP model formulation is:

𝑀𝑎𝑥 𝑧 = 50𝑥1 + 75𝑥2 − 1𝑥3 − 2𝑥4
𝑠. 𝑡. 5𝑥1 + 20𝑥2 + 𝑥3 = 400
10𝑥1 + 15𝑥2 + 𝑥4 = 450
𝑥1, 𝑥2, 𝑥3, 𝑥4 ≥ 0

New Furniture Problem: solved with Gurobi … 1

price

Price
Price

New Furniture Problem: solved with Gurobi … 2

We add a cost parameter to the resources
multidict to penalize the waste of resources.

New Furniture Problem: solved with Gurobi … 3

We add a new type of decision variable tomeasure the unused resource capacity.

priceNew Furniture Problem: solved with Gurobi … 4

The optimal solution is now making 14 tables and 24 chairs with a
total objective function value of $2,250.
Notice that the solution of making 0 tables and 45 chairs is no longer
optimal since the objective function value is($50*45 = $2,250) – ($1*175 = $175) = $2,075.
That is, the alternative solution (chairs = 45, tables =0) is no longer
optimal.

Unbounded LP problem
Gurobi Python API

Furniture Problem

New business conditions• The operations manager of thefurniture factory tells the data
scientist that she is negotiatingwith the supplier of mahogany
to obtain an unlimited amountof mahogany as long as thefactory procures at least 400
units of mahogany per week.
• In addition, the operations
manager is negotiating withthe union to obtain extra
workforce as long as thefactory hires at least 450 hoursof labor per week.

Furniture Problem

New business conditions

The new LP problem formulations is:• Notice that the polyhedrondefined by the feasible regionis unbounded.

1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 45𝑥1 + 80𝑥2

𝑥2

2.0
3.0

TablesConstraint (3.0)
Labor

5𝑥1 + 20𝑥2 ≥ 400 Mahogany constraint
10𝑥1 + 15𝑥2 ≥ 450 Labor constraint
𝑥1 , 𝑥2 ≥ 0

Feasible• Clearly, the maximum of theobjective function isunbounded, since the revenue
that we can make can bearbitrarily large by increasing
the number of chairs (x1)and/or the number of tables(x2) as much as we want.
Recall, that we had assumed
that we sell everything that we
produce.

Region

RevenueConstraint (2.0)
Mahogany𝑥1
Chairs• Conclusion: With unlimited
mahogany and labor, revenue
is unlimited.

Unbounded Furniture Problem: solved with Gurobi .. 1

The Gurobi solver could not find an optimal solution and declares the
problem either infeasible or unbounded.

Unbounded Furniture Problem: solved with Gurobi .. 2
Since an optimal solution does not exist, the objective function
value and the value of the decision variables is void. In this case,
we get an error when trying to print these values.

To avoid the error, we need to check the status of the LP model,
and only print the solution values if an optimal solution was found.

Unbounded Furniture Problem: solved with Gurobi .. 3
We changed the sense of the optimization tocheck if the model has a feasible solution.

The Gurobi solver now finds a minimum optimal solution. Hence,the LP problem is feasible and for the revenue maximization
problem, it is unbounded.

New business conditions• The data scientist recognizedthat it is unrealistic to assume
that an infinite amount ofchairs and tables can be sold.
• The data scientist using
predictive analytics techniques
has determined that at most
200 chairs and 150 tables canbe sold.

New furniture problem

New business conditions

𝑥2

Tables

1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 45𝑥1 + 80𝑥2

150

2.0

5𝑥1 + 20𝑥2 ≥ 400 Mahogany constraint

3.0

10𝑥1 + 15𝑥2 ≥ 450 Labor constraint

0 ≤ 𝑥1 ≤ 200

Feasible Region
Constraint (3.0)
Labor

Constraint (2.0)
Mahogany

Revenue equation:
Revenue = 45x1 + 80x2

𝑥1 200Chairs0 ≤ 𝑥2 ≤ 150

Unbounded Furniture Problem: solved with Gurobi ..4

Adding the upper bounds to the multidict for products

Unbounded Furniture Problem: solved with Gurobi .. 5

Adding the upper bounds to the multidict for
products

Unbounded Furniture Problem: solved with Gurobi .. 6

Unbounded Furniture Problem: solved with Gurobi .. 7

As expected, Gurobi solver now finds
an optimal solution.
The optimal number of chairs to makeis equal to the chairs upper bound andthe optimal number of tables to make isequal to the tables upper bound.
The optimal objective function value isa total revenue of $21,000

Infeasible LP problem
Gurobi Python API

Minimum Optimal Solution

New business conditions• The data scientist receives a
memo from the CEO of thefurniture company saying thatthe new board of directors of
the company requires a total
revenue of at least $4,500 per
week.

Furniture Problem

New business conditions

The new LP problem formulations is:𝑥2
TablesConstraint (4.0)
Board of directors

Constraint (3.0)
Labor

Feasible Region

1.0 𝑀𝑎𝑥 𝑅𝑒𝑣𝑒𝑛𝑢𝑒 = 45𝑥1 + 80𝑥2
2.0
5𝑥1 + 20𝑥2 ≤ 400 Mahogany constraint
3.0
10𝑥1 + 15𝑥2 ≤ 450 Labor constraint
4.0
45𝑥1 + 80𝑥2 ≥ 4500 Board of directors constraint
𝑥1 , 𝑥2 ≥ 0(4.0) Board of directors constraint

Constraint (2.0)
Mahogany(0,0)

Profit equation:
Profit = 45x1 + 80x2

𝑥1 ≥ 0Chairs• Evidently, there are no points
that satisfy all the constraints
simultaneously. Hence this LP
problem is infeasible.

Infeasible Furniture Problem: using with Gurobi .. 1

Defining a new parameter to capture the minimum revenue value that the board of directors may impose.

Adding a new constraint to the f model to ensure that the minimum revenue impose by the Board is satisfied.

Infeasible Furniture Problem: solved with Gurobi .. 2

Infeasible Furniture Problem: solved with Gurobi .. 3

We check the status of the f model tosee if Gurobi found an optimal solution.
If true, then we print the optimal solution
and the associated objective function
value.

Infeasible Furniture Problem: solved with Gurobi .. 3

We set an objective with zero
value. Then run the Gurobi solver
to find any feasible solution.

We check the status of the fmodel to see if it is infeasible. If
true, then we print that we have
proven that the model is
infeasible.

Infeasible Furniture Problem

Addressing infeasibility• There is a Board of Director
meeting and the data scientist
cannot tell the Board that theirrequirement of having a total
revenue of at least $4,500 per
week is Infeasible !!!
• The data scientist knows that thecause of infeasibility is thelimited capacity available ofresources that does not allow
the production of chairs andtables to reach the minimum
level of total revenue.
• The data scientist calls the
supplier of mahogany and talks
with the labor union and theyagree to increase the supply at acost. An extra unit of mahogany
will cost $20 and one hour ofovertime of labor will cost $30.

Furniture Problem: addressing infeasibility .. 2

Furniture Problem: addressing infeasibility .. 2

We include in the resources multidict the extra costof adding resource capacity.
Create a new decision variable to measure the extra
resource capacity to meet the Board constraint.

We add a decision variable (extra) to the RHS of each resource constraint to add the extra capacity to satisfy the Board constraint.

We subtract the cost of the extra capacity to meet the Board constraint .

Furniture Problem: addressing infeasibility .. 3

Furniture Problem: addressing infeasibility .. 3

Gurobi solver found an optimal solution.

Furniture Problem: addressing infeasibility

To meet the Board request
requires 100 extra units ofmahogany and 550 extra
units of overtime.
The optimal production plan
is to produce only 100 chairs.
The company will lose
$14,000 per week !!!

The Board request wasproven not to be a good idea.

Final Remarks about model status• It is a good modeling practice that the LP problem is well characterized.
• This means that when the data of the LP problem satisfy the specified modelingassumptions, the LP problem has an optimal solution.
• That is, the LP problem is never infeasible, unbounded, and there are no alternate
optimal solutions.
• To avoid infeasibility add “artificial” variables to the constraints that may be
infeasible. These artificial variables will have a “high” penalty in the objectivefunction in such a way that they become positive only to make the problem feasible.
Ideally, these artificial variables have a business meaning that the user of thedecision support application can properly interpret.
• To avoid that the LP problem is unbounded, define realistic upper bounds for all thedecision variables of the LP problem.

• If the LP problem has alternate optimal solutions, if possible add another objectivefunctions that eliminates the alternate optimal solutions.

Linear Programming Overview
Further considerations:• Maximize or minimize objective function• Unconstrained decision variables• Initial basic solution• Presolve• Matrix sparsity

What if we need to minimize an objective function?
We have assumed that we are maximizing an LP problem. Notice that the rules
for a non-basic variables to become basic variables can be changed to address
the minimization problem.
𝒏σ
Alternatively, since 𝑴𝒊𝒏 σ𝒏
𝒃
𝒙
=
−𝑴𝒂𝒙
−
𝒋=𝟏 𝒋 𝒋
𝒋=𝟏 𝒃𝒋 𝒙𝒋 , then we solve

𝑴𝒂𝒙 σ𝒏𝒋=𝟏(−𝒃𝒋 )𝒙𝒋 .
Example: Min {1, 2} = -Max {-1, -2} = 1

What if a decision variable can be positive or negative?

If the decision variable is unconstrained in sign, the Gurobi
Optimizer will take care of this automatically.
An example of a decision variable that is unconstrained is profit.
Negative profit is interpreted as a loss.

How to determine an initial basic feasible solution?
• Gurobi behind the scenes may use a technique called Phase 1 of Linear
Programming:• This technique entails adding non-negative artificial variables to the equations(=) and greater-or-equal (≥) inequalities.
• Then replace the original objective function by a new objective, minimize thesummation of the artificial variables.
• If the minimum value of the summation of artificial variables is positive, the LP
problem is infeasible.
• If the minimum value of the summation of artificial variables is zero, then thebasic feasible variables of the optimal solution are an initial basic feasible
solution of the original LP model (*).
(*) There are some subtleties about this statement beyond the scope of this class.

How to determine an initial basic feasible solution? .. 2
• Consider the following LP problem with the Furniture factory board request.

• An instance of the parametrized formulation is
𝑀𝑎𝑥 𝑧 = 45𝑥1 + 80𝑥2 − 20𝑥3 − 30𝑥4
5𝑥1 + 20𝑥2 − 𝑥3 ≤ 400
10𝑥1 + 15𝑥2 − 𝑥4 ≤ 450
45𝑥1 + 80𝑥2 ≥ 4500
𝑥1 , 𝑥2, , 𝑥3 . 𝑥4 ≥ 0How to determine an initial basic feasible solution? .. 2
• Original LP problem.

𝑀𝑎𝑥 𝑧 = 45𝑥1 + 80𝑥2 − 20𝑥3 − 30𝑥4
5𝑥1 + 20𝑥2 − 𝑥3 ≤ 400
10𝑥1 + 15𝑥2 − 𝑥4 ≤ 450
45𝑥1 + 80𝑥2 ≥ 4500
𝑥1 , 𝑥2, , 𝑥3 . 𝑥4 ≥ 0• We add an artificial variable alpha to the ≥ constraint. At Phase 1 of linear programming,
we minimize the value of alpha, i.e. alpha should be equal to zero and non-basic
variable, to identify an initial basic feasible solution.
Original LP Problem

LP Problem Standard Form

𝑀𝑖𝑛 𝑤 = 𝛼𝑀𝑎𝑥 𝑤 = −𝛼LP Problem Canonical Form

𝑀𝑎𝑥 𝑤 = −4500 + 45𝑥1 + 80𝑥2 − 𝑠1

5𝑥1 + 20𝑥2 − 𝑥3 ≤ 400
10𝑥1 + 15𝑥2 − 𝑥4 ≤ 450

5𝑥1 + 20𝑥2 − 𝑥3 + ℎ1 = 400
10𝑥1 + 15𝑥2 − 𝑥4 + ℎ2 = 450ℎ1 = 400 − 5𝑥1 − 20𝑥2 + 𝑥3
ℎ2 = 450 − 10𝑥1 − 15𝑥2 + 𝑥4

45𝑥1 + 80𝑥2 + 𝛼 ≥ 4500

45𝑥1 + 80𝑥2 + 𝛼 − 𝑠1 = 4500

𝛼 = 4500 − 45𝑥1 − 80𝑥2 + 𝑠1

𝑥1 , 𝑥2 , 𝑥3 . 𝑥4 , 𝛼 ≥ 0𝑥1 , 𝑥2 , 𝑥3 . 𝑥4 , 𝛼, ℎ1 , ℎ2 , 𝑠1 ≥ 0

𝑥1 , 𝑥2 , 𝑥3 . 𝑥4 , 𝛼, ℎ1 , ℎ2 , 𝑠1 ≥ 0

How to determine an initial basic feasible solution? .. 3
We apply the simplex method to the Phase 1 LP problem in canonical form with respect to the basis(ℎ1 , ℎ2 , 𝛼). The following table shows the basic feasible solution at each iteration of the simplex
method, the non basic variable entering the basis and the basic variable leaving the basis.
Iteration

Basic feasible solution Phase 1

Non basic variable
entering the basis

Basic variable leaving
the basis1ℎ1 = 400 , ℎ2 = 450 , 𝛼 = 4500

𝑥2

ℎ1

2

𝑥2 = 20 , ℎ2 = 150 , 𝛼 = 2900

𝑥3

ℎ2

3

𝑥2 = 30 , 𝑥3 = 200 , 𝛼 = 2100

𝑥4

𝛼

4

𝑥2 = 56.25, 𝑥3 = 725 , 𝑥4 = 393.75

𝑥1

𝑥2

5

𝑥1 = 100 , 𝑥3 = 100 , 𝑥4 = 550

This solution is optimal.

Notice that 𝛼 is non basic and = 0. This solution is an initial basic feasible solution of the original LP problem.
Iteration 4 continues with Phase 2 of the simplex method, where we find the optimal feasible basic solution.

Optimal solution found using Gurobi

x1 = 100x3 = 100x4 = 550

Gurobi corroborates the optimal solution found manuallyusing the two phases simplex method approach

How to determine an initial basic feasible solution? .. 4

Remarks• Gurobi user does not need to provide an initial basic feasible
solution, or solve the phase 1 minimization of the sum of
artificial variables problem to generate an initial basic solution.
• Gurobi only needs the original LP formulation. It automaticallyfinds an initial feasible basic solution to start the simplex
method.

Presolve

Presolve• LP problems can use a large amount of computer time, consequently it is advisable to have LP
models that can be solved as quickly as possible.
• The Presolve engine of Gurobi can dramatically reduce the size of an LP problem. The
reduced problem can then be solved faster than the original one. The solution of the reduced
problem is then used to generate a solution of the original problem.

• To briefly illustrate the core ideas behind a Presolve approach consider the following example.

• Max 2x1 + 3x2 –x3 –x4 … (0)• Subject to: x1 + x2 + x3 -2x4 ≤ 4 … (1)•-x1 –x2 + x3 – x4 ≤ 1 … (2)

•

x1

•

x1, x2, x3, x4 ≥ 0 … (4)+ x4 ≤ 1 … (3)• Notice that x3 has a negative objective coefficient. We
have a maximization problem, then we want to make x3
as small as possible.
• Observe that x3 has positive coefficient in constraints (1)and (2),• and these constraints are of the ‘≤’, then we want tomake x3 as small as possible.
• Therefore, x3 can be reduced to its lower bound of zeroand eliminated as a redundant variable.

Presolve ..2
•
•
•
•
•

Max 2x1 + 3x2 –x4 … (0)Subject to: x1 + x2 -2x4 ≤ 4 … (1)-x1 –x2 – x4 ≤ 1 … (2)x1+ x4 ≤ 1 … (3)x1, x2, x3, x4 ≥ 0 … (4)• After removing x3, let’s analyze constraint (2) –x1 –x2 –x4 ≤ 1. Notice that all coefficients of thevariables in this constraint are negative. For any positive value of variables x1, x2, and x3
constraint (2) is satisfied, consequently this constrained is redundant and can be eliminated.
The reduced problem is then:•Max 2x1 + 3x2 –x4… (0)• Subject to: x1 + x2 - 2x4 ≤ 4 … (1)•x1+ x4 ≤ 1 … (3)•x1, x2, x4 ≥ 0 and x3=0 … (4)Example of the power of Gurobi Presolve
Gurobi Case Study:• Solution approach:
Problemstatement:
how
to optimize
the selectionandschedulingofaThereportfolio
IT
Project
Portfolio
Optimization
isProject
an extremely
difficultproblemto solve.
areofan•• A
decision
supporttool,
calledPortfolio
Optimization(PPO),
wasbuilt toprojects
suchthat the oftrade-offs
amongobjectives
areprojects
optimized,
while within
astronomical
combinations
tovarious
selectandschedule
optimally
automate
the number
numbercrunchingprocesses
duringthecreationand maintenanceof asatisfying
constraints(e.g.
labor availability and budgets) and other businessthe scarceandlimitedresources
available.
portfolio
ofresource
IT projects.
constraints (e.g. project precedence constraints).
• Gurobi solver was used to solve this complex MIP problem.

Example of the power of Gurobi Presolve .. 3
Size

PPO model

PPO model
after Presolve

Reduction %Total # of variables

9307

3170

66 %

Total # of constraints

6461

337

94 %

Gurobi solving time–

8.53 s–Gurobi solving time no presolve

156.1 s––Matrix sparsity of LP problems•• An
Presolvetakes
advantageof the LP
sparsityof thematrixisof
technology
coefficientstoimportantfeatureof practicaland MIPmodelsthattheir matrixof technology
significantly is
reducethe size of the problem.
coefficientssparse.
means thata smallof coefficientsin theismatrixof technology•• ThisThe sparsityof thematrixnumberof technology
coefficients
effectively
exploited coefficientsin a very is
non-zero.
efficient computer implementation of the simplex method called the revised simplex
method.
Objective function
coefficients𝑛
Objective
Function

Constraints

Technology
coefficients

𝑀𝑎𝑥 ෍
𝑗=1

𝑏𝑗 𝑥𝑗

Decision
Variables
RHS: righthand side

σ𝑛𝑗=1 𝑎𝑖,𝑗 𝑥𝑗 ≤ 𝐾𝑖 (𝑖 = 1 . . 𝑚)
𝑥𝑗 ≥ 0 (𝑗 = 1. . 𝑛)

Set of indicesfor Constraints

Set of indicesfor Variables

Duality in Linear Programming

Linear Programming Duality
In the section of sensitivity analysis of Linear Programming, we asked the following question:• For the furniture problem, is it profitable to make a third product, like desks?
• Assume that the price of the desk is $110,• and the desk consumes 15 units of mahogany and 25 units of labor.
• Shadow prices determine the marginal worth of an additional unit of a resource:• The shadow price of the mahogany capacity constraint is $1.
• The shadow price of the labor capacity constraint is $4.

• Let’s compute the opportunity cost of making one desk and compare it with the price of a desk. If
this opportunity cost is greater than the desk price, then it is not worth it to make desks.
• The opportunity cost can be computed by multiplying the units of mahogany capacity that one
desk built consumes by the shadow price of mahogany capacity, and multiplying the units oflabor capacity that one desk built consumes by the shadow price of labor capacity:• That is, ($1)*15 (units of mahogany) + ($4)*25 (hours of labor) = $115 > $110.
• Therefore, investing resources to produce desks, otherwise used to produce chairs and tables,
is not profitable.

Linear Programming Duality .. 2

Duality in Linear Programming is anunifying theory that established therelation between an LP problem –called Primal Problem, and anotherrelated LP problem –called Dual
Problem, where its decision variables(dual variables) are the shadow
prices of the resource constraints.

Furniture Problem: Primal and Dual problems
The primal and dual of the Furniture problem are:PrimalDual

1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 45𝑥1 + 80𝑥2

4.0 𝑀𝑖𝑛 𝐶𝑜𝑠𝑡 = 400𝑤1 + 450𝑤2

2.0

5𝑥1 + 20𝑥2 ≤ 400

Mahogany

3.0

10𝑥1 + 15𝑥2 ≤ 450

Labor

5.0
6.0

𝑥1 , 𝑥2 ≥ 0
Chairs Tables

5𝑤1 + 10𝑤2 ≥ 45
20𝑤1 + 15𝑤2 ≥ 80

ChairsTables𝑤1 , 𝑤2 ≥ 0
Mahogany

Labor• In this dual problem, the decision variable w1 represents the opportunity cost of the mahogany resource, andw2 is the opportunity cost of the labor resource. These decision variables are the shadow prices of mahogany
and labor capacity.
• Notice the switch between the objective function coefficients and the right hand sides of the primal and dual
problems.
• Also, notice that the rows of the primal problem are the columns of the dual problem. This means that
inequalities (5.0) and (6.0) ensures that the opportunity costs of consumption of resources per unit of productionof chairs and tables, respectively, should be at least the value of their price. The objective is to minimize theresource opportunity costs.

Furniture Dual Problem: Graphical solution(4.0)
Objective Function

𝑤2

Dual
4.0 𝑀𝑖𝑛 𝐶𝑜𝑠𝑡 = 400𝑤1 + 450𝑤2

Labor
Constraint (6.0)
Tables5.0

5𝑤1 + 10𝑤2 ≥ 45

Chairs6.0

20𝑤1 + 15𝑤2 ≥ 80

Tables𝑤1 , 𝑤2 ≥ 0
4Mahogany Labor

Constraint (5.0)
Chairs

(0,0)

𝑤1
1

4

MahoganyFurniture Dual Problem: Graphical solution
𝑤2

Dual
4.0 𝑀𝑖𝑛 𝐶𝑜𝑠𝑡 = 400𝑤1 + 450𝑤2

Labor

Constraint (6.0)
Tables5.0

5𝑤1 + 10𝑤2 ≥ 45

Chairs6.0

20𝑤1 + 15𝑤2 ≥ 80

Tables𝑤1 , 𝑤2 ≥ 0($1, $4)

4Mahogany Labor

Constraint (5.0)
Chairs

(0,0)

1

𝑤1

4
Objective Function = $2200

MahoganyFurniture Dual Problem: ParametrizedFurniture Dual Problem: Solved with Gurobi ..1
The data of the Furniture Dual problem is identical to the original Furniture problem –called Primal Problem.

Furniture Dual Problem: Solved with Gurobi ..2
The right hand side of the constraints are the price of each product. The left hand side is the opportunity costof consuming each resource when making the products. The sense of the inequalities is greater than equal
to have an evaluation of the resource at least equal to the price.

GRB.MINIMZE is the default
Coefficients in the objective function are the resource capacities

Furniture Dual Problem: Solved with Gurobi ..3

Furniture Dual Problem: Solved with Gurobi ..4

Gurobi solver finds the optimal solutionof the Furniture dual problem$1.00 The optimal value of the shadow price for mahogany is $1.00$4.00 The optimal value of the shadow price for labor is $4.00$2,200 The optimal objective function value is $2,200

Furniture Dual Problem: Solved with Gurobi .. 5

• The “shadow prices” of the products’ constraints are 14 tables and 24 chairs. These are theoptimal (make) values of the Furniture primal problem. Notice that in both problems, primal anddual, the optimal objective function value is $2,200. This is not a coincidence!!!

Duality in Linear Programming
Remarks:• In general, it can be shown that the dual of a dual problem is the primal problem, and that wheneither problem has an optimal solution, the other problem also has an optimal solution, and the
optimal objective function value of both problems is the same.
• Another important feature of duality in linear programming is that the optimal solution of the dual
problem is contained in the information provided by the simplex method while solving andfinding an optimal solution to the primal problem.

• Duality in linear programming provides a good characterization of optimality conditions that canbe exploited computationally to solve LP problems efficiently.

Relationship between primal and dual problems
Primal1)

Primal (maximize)

Dual (minimize)i’th constraint ≤i’th variable ≥ 0

2)i’th constraint ≥i’th variable ≤ 0

3)i’th constraint =i’th variable unrestricted

4)j’th variable ≥ 0j’th constraint ≥5)j’th variable ≤ 0j’th constraint ≤6)j’th variable unrestrictedj’th constraint =1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 45𝑥1 + 80𝑥2
2.0

5𝑥1 + 20𝑥2 ≤ 400

Mahogany

3.0

10𝑥1 + 15𝑥2 ≤ 450

Labor

𝑥1 , 𝑥2 ≥ 0
Chairs Tables

Dual

4.0 𝑀𝑖𝑛 𝐶𝑜𝑠𝑡 = 400𝑤1 + 450𝑤2
5.0
6.0

Chairs
5𝑤1 + 10𝑤2 ≥ 45
20𝑤1 + 15𝑤2 ≥ 80 Tables
𝑤1 , 𝑤2 ≥ 0
Mahogany

Labor

Remark:Notice that the relationship between the Furniture primal and dual problems is captured by rows 1) and 4)

Optimality conditions
Linear Programming

Optimality conditions in linear programming .. 1
Consider the Furniture primal and dual problems:
PrimalDual

1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 45𝑥1 + 80𝑥2

4.0 𝑀𝑖𝑛 𝐶𝑜𝑠𝑡 = 400𝑤1 + 450𝑤2

2.0
3.0

5.0
6.0

5𝑥1 + 20𝑥2 ≤ 400 Mahogany
10𝑥1 + 15𝑥2 ≤ 450 Labor
𝑥1 , 𝑥2 ≥ 0

Chairs
5𝑤1 + 10𝑤2 ≥ 45
20𝑤1 + 15𝑤2 ≥ 80 Tables
𝑤1 , 𝑤2 ≥ 0
Mahogany

Chairs Tables

Labor

Furniture primal and dual problems in standard form

1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 45𝑥1 + 80𝑥2

4.0 𝑀𝑖𝑛 𝐶𝑜𝑠𝑡 = 400𝑤1 + 450𝑤2

2.0

5𝑥1 + 20𝑥2 + ℎ1 = 400

Mahogany

5.0

5𝑤1 + 10𝑤2 − 𝑠1 = 45

3.0

10𝑥1 + 15𝑥2 + ℎ2 = 450

Labor

6.0

20𝑤1 + 15𝑤2 − 𝑠2 = 80 Tables

𝑥1 , 𝑥2, ℎ1, ℎ2 ≥ 0
Chairs Tables

Chairs𝑤1 , 𝑤2 𝑠1 , 𝑠2 ≥ 0
Mahogany Laborℎ1 is the slack variable of the mahogany constraint

𝑠1 is the surplus variable of the chairs constraintℎ2 is the slack variable of the labor constraint

𝑠2 is the surplus variable of the tables constraintOptimality conditions in linear programming .. 2
Consider the optimal solution of both problems, primal and dual
Primal optimal solution:
x1 = 24, x2 = 14, h1 = 0, h2 = 0

Dual optimal solution:
w1 = 1, w2 = 4, s1 = 0, s2 = 0

1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 45 𝑥1 = 24 + 80 𝑥2 = 14 = 2200

4.0 𝑀𝑖𝑛 𝐶𝑜𝑠𝑡 = 400 𝑤1 = 1 + 450 𝑤2 = 4 = 2200

Mahogany

Chairs

2.0 5 𝑥1 = 24 + 20 𝑥2 = 14 + (ℎ1 = 0) = 400

binding

5.0 5 𝑤1 = 1 + 10 𝑤2 = 4 − (𝑠1 = 0) = 45

Labor

Tables

3.0 10 𝑥1 = 24 + 15 𝑥2 = 14 + (ℎ2 = 0) = 450 binding

6.0 20 𝑤1 = 1 + 15 𝑤2 = 4 − (𝑠2 = 0) = 80

𝑥1 , 𝑥2, ℎ1, ℎ2 ≥ 0
Chairs Tables

𝑤1 , 𝑤2 𝑠1 , 𝑠2 ≥ 0
Mahogany Labor

Remarks• Note that the mahogany and labor constraints are binding, i.e. the slack variables (h1 = h2 = 0).
• Note that the shadow price of the mahogany and labor constraints are positive, i.e. (w1 = 1, w2 = 4).

• Note that the chairs and tables constraints are binding, i.e. the surplus variables (s1 = s2 = 0).
• Note that the “shadow price” of the chairs and tables constraints are positive, i.e. (x1 = 24, x2 = 14).

Optimality conditions in linear programming .. 3
In summary
Primal optimal solution

Dual optimal solution

Chair variable x1 = 24

Chair constraint (is binding) surplus variable s1 = 0

Table variable x2 = 14

Table constraint (is binding) surplus variable s2 = 0

Mahogany constraint (is binding) slack variable h1 = 0

Mahogany shadow price w1 = 1

Labor constraint (is binding) slack variable h2 = 0

Labor shadow price w2 = 4

Complementary (a.k.a. orthogonality) conditions in linear programming optimal solutions• x*s = 0. At optimality, the product of the decision variables in the primal problem and theassociate surplus (slack) variables in the dual problem is always zero.
• h*w = 0. At optimality, the product of the slack (surplus) variables in the primal problem and theassociate shadow prices in the dual problem is always zero.

Summary of optimality conditions for linear programming• A solution (x1=24, x2=14) to the primal problem and a solution (w1=1, w2=4) of the dual
problem are optimal, if and only if:• Primal feasibility: we have found a solution of the primal problem that satisfy all its
constraints.
• The production plan satisfies the mahogany and labor constraints.

2.0 5 𝑥1 = 24 + 20 𝑥2 = 14 = 400 Mahogany capacity
3.0 10 𝑥1 = 24 + 15 𝑥2 = 14 = 450 Labor capacity• Dual feasibility: we have found a solution of the dual problem that satisfy all its constraints.
• The shadow prices associated to the mahogany and labor resources satisfy the priceconstraints for the chairs and the tables.

5.0 5 𝑤1 = 1 + 10 𝑤2 = 4 = 45

Chair price6.0 20 𝑤1 = 1 + 15 𝑤2 = 4 = 80 Table priceSummary of optimality conditions for linear programming• Complementary (orthogonality) conditions:• The product of the decision variables in the primal problem and the associate surplus
variables in the dual problem is always zero. (Cost efficient).
• Since we are building 24 chairs, the surplus variable of the constraint of the price ofchairs is 0. That is, x1*s1=0. This means that the opportunity costs of building chairs isequal to the price of the chair:

5.0 5 𝑤1 = 1 + 10 𝑤2 = 4 − (𝑠1 = 0) = 45
• Since we are building 14 tables, the surplus variable of the constraint of the price oftables is 0. That is, x2*s2=0. This means that the opportunity costs of building tables isequal to the price of the table:

6.0 20 𝑤1 = 1 + 15 𝑤2 = 4 − (𝑠2 = 0) = 80

Summary of optimality conditions for linear programming• The product of the decision variables in the dual problem and the associate slack variablesin the primal problem is always zero. (Resource efficient).
• Since the shadow price (opportunity cost) of mahogany is $1, the slack variable of the
mahogany constraint is 0. This means we are using the mahogany resource efficiently
and there is no waste.

(2.0) 5(𝑥1 = 24) + 20(𝑥2 = 14) + (ℎ1 = 0) = 400• Since the shadow price (opportunity cost) of labor is $4, the slack variable of the labor
constraint is 0. This means we are using the labor resource efficiently and there is nowaste.

(3.0) 10(𝑥1 = 24) + 15(𝑥2 = 14) + (ℎ2 = 0) = 450

Summary of optimality conditions for linear programming• The optimal objective function value of the primal problem = the optimal objective function of
the dual problem. This mathematical theorem is known as strong duality.

1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 = 45 𝑥1 = 24 + 80 𝑥2 = 14 = 2200
4.0 𝑀𝑖𝑛 𝐶𝑜𝑠𝑡 = 400 𝑤1 = 1 + 450 𝑤2 = 4 = 2200

Dual Simplex method
Variation of Simplex method

The Dual simplex method
The key idea of the dual simplex method is to apply the simplex method to the dual problem, but using
the canonical form of the primal problem.
𝑥2
TablesOriginal LP Problem Formulation
1.0 𝑀𝑎𝑥 𝑟𝑒𝑣𝑒𝑛𝑢𝑒(𝑧) = 45𝑥1 + 80𝑥2
2.0
5𝑥1 + 20𝑥2 ≤ 400 Mahogany
3.0
10𝑥1 + 15𝑥2 ≤ 450 Labor
𝑥1 , 𝑥2 ≥ 0
Tables(Revenue)30

LP Problem Formulation in Canonical Form
1.0 𝑀𝑎𝑥 𝑧 = 2400 − 25ൗ3 𝑥1 − 80ൗ15 ℎ2
2.0 ℎ1 = −200 + 25ൗ3 𝑥1 + 4ൗ3 ℎ2
3.0 𝑥2 =30 − 2ൗ3 𝑥1 − 1ൗ15 ℎ2
𝑥1, 𝑥2, ℎ1, ℎ2 ≥ 0

Consider the following basic infeasible solution:x1=0, x2=30, h1=-200, h2=020Polyhedron(Mahogany)𝑥1 ≥ 0(0,0)(Labor)ChairsThe Dual simplex method ..2
𝑥2
Tables• Recall that the simplex method iterates from one basic feasible solution to another, always trying to
improve the value of the objective function.

• The simplex method finds an optimal basic feasible solution when all the reduced costs of the nonbasic variables of the primal problem expressed in a canonical form are ≤ 0. (Maximization problem).
• The idea of the dual simplex method is to start with a (dual) basic feasible solution (i.e. all the
reduced costs of the non-basic variables are ≤ 0). Notice that if all the basic variables are ≥ 0, thenthe current solution is a basic feasible solution for the primal problem in a canonical form thatsatisfies the optimality conditions, consequently this solution is optimal.

(Revenue)30• Dual basic feasible solution: since reduced costs
of non-basic variables are ≤ 0:
x1=0, x2=30, h1=-200, h2=020Polyhedron

LP Problem Formulation in Canonical Form
1.0 𝑀𝑎𝑥 𝑧 = 2400 − 25ൗ3 𝑥1 − 80ൗ15 ℎ2
2.0 ℎ1 = −200 + 25ൗ3 𝑥1 + 4ൗ3 ℎ2
3.0 𝑥2 =30 − 2ൗ3 𝑥1 − 1ൗ15 ℎ2
𝑥1, 𝑥2, ℎ1, ℎ2 ≥ 0(Mahogany)𝑥1 ≥ 0(0,0)(Labor)ChairsThe Dual simplex method ..3
𝑥2
Tables• Suppose that at least there is one basic variable that is negative. Choose the basic variable with themost negative value as the variable to leave the basis. In this example, the variable h1 will leave thebasis.
• If all the coefficients of the non-basic variables in the canonical form equation of the basic variableleaving the basis are negative, STOP the LP problem is infeasible.
LP Problem Formulation in Canonical Form
1.0 𝑀𝑎𝑥 𝑧 = 2400 − 25ൗ3 𝑥1 − 80ൗ15 ℎ2
2.0 ℎ1 = −200 + 25ൗ3 𝑥1 + 4ൗ3 ℎ2
3.0 𝑥2 =30 − 2ൗ3 𝑥1 − 1ൗ15 ℎ2
𝑥1, 𝑥2, ℎ1, ℎ2 ≥ 0(Revenue)
30

20

Polyhedron(Mahogany)𝑥1 ≥ 0(0,0)(Labor)ChairsThe Dual simplex method ..4
𝑥2
Tables• Else, there is at least one non-basic variable with a positive coefficient, consider the minimum ratio testof the absolute of the reduce costs and the positive coefficient of non-basic variables in the canonicalform equation of the basic variable leaving the basis. The non-basic variable with the minimum ratio
enters the basis. Determine the new (dual) basic feasible solution. Minimum ratio test:• Min { (25/3)/(25/3)=1, (80/15)/(4/3)=4,}= 25/3)/(25/3)=1. Hence, the variable x1 enters the basis.
• Determine the new (dual) basic feasible solution by pivoting.
LP Problem Formulation in Canonical Form
1.0 𝑀𝑎𝑥 𝑧 = 2400 − 25ൗ3 𝑥1 − 80ൗ15 ℎ2
2.0 ℎ1 = −200 + 25ൗ3 𝑥1 + 4ൗ3 ℎ2
3.0 𝑥2 =30 − 2ൗ3 𝑥1 − 1ൗ15 ℎ2
𝑥1, 𝑥2, ℎ1, ℎ2 ≥ 0(Revenue)
30

20

Polyhedron(Mahogany)𝑥1 ≥ 0(0,0)(Labor)Chairs

Pivot

The Dual simplex method ..5• Pivoting). In equation (2.0), express basic variable x1 in terms of non-basic variables h1 and h2:
𝑥2
Tables

2.0 𝑥1 = 24 + 3ൗ25 ℎ1 − 4ൗ25 ℎ2• In equation (3.0), replace the value of x1:

3.0

𝑥2 = 14 − 2ൗ25 ℎ1 − 1ൗ25 ℎ2• In the objective function (1.0), replace the value of x1: 1.0(Revenue)

Pivot

30

𝑥1, 𝑥2, ℎ1, ℎ2 ≥ 0

𝑀𝑎𝑥 𝑧 = 2200 − 1ℎ1 − 4ℎ2• Notice that the current solution is both a primal basic feasible solution, since
all basic variables are ≥ 0; and a dual basic feasible solution, since all the
reduced costs associated to the non-basic variables are ≤ 0.
• As we have seen, this solution satisfies the complementary conditions:• Therefore, the solution is optimal.

20

Polyhedron(Mahogany)𝑥1 ≥ 0(0,0)(Labor)ChairsThe Dual simplex method ..5• The dual simplex method is recommended for LP problems in which adual basic feasible solution is available.

• The dual simplex method is particularly useful for reoptimizing an LP
problem after a constraint has been added, since we don’t need to start
the solution approach from scratch.
• The cutting planes method to solve MIP problems relies heavily on the
dual simplex. The core idea of the cutting planes method is to add a
constraint to the LP problem continuous relaxation whenever an integer
variable has a fractional value in the optimal solution. The added
constraint will make this fractional value of the integer variable infeasible.

END