18.310A lecture notes March 17, 2015
Linear programming
Lecturer: Michel Goemans
1 Basics
Linear Programming deals with the problem of optimizing a linear objective function subject to
linear equality and inequality constraints on the decision variables. Linear programming has many
practical applications (in transportation, production planning, ...). It is also the building block for
combinatorial optimization. One aspect of linear programming which is often forgotten is the fact
that it is also a useful proof technique. In this first chapter, we describe some linear programming
formulations for some classical problems. We also show that linear programs can be expressed in a
variety of equivalent ways.
1.1 Formulations
1.1.1 The Diet Problem
In the diet model, a list of available foods is given together with the nutrient content and the cost
per unit weight of each food. A certain amount of each nutrient is required per day. For example,
here is the data corresponding to a civilization with just two types of grains (G1 and G2) and three
types of nutrients (starch, proteins, vitamins):
Starch Proteins Vitamins Cost ($/kg)
G1 5 4 2 0.6
G2 7 2 1 0.35
Nutrient content and cost per kg of food.
The requirement per day of starch, proteins and vitamins is 8, 15 and 3 respectively. The problem
is to find how much of each food to consume per day so as to get the required amount per day of
each nutrient at minimal cost.
When trying to formulate a problem as a linear program, the first step is to decide which
decision variables to use. These variables represent the unknowns in the problem. In the diet
problem, a very natural choice of decision variables is:
• x1 : number of units of grain G1 to be consumed per day,
• x2 : number of units of grain G2 to be consumed per day.
The next step is to write down the objective function. The objective function is the function to be
minimized or maximized. In this case, the objective is to minimize the total cost per day which is
given by z = 0.6x1 + 0.35x2 (the value of the objective function is often denoted by z).
Finally, we need to describe the different constraints that need to be satisfied by x1 and x2 .
First of all, x1 and x2 must certainly satisfy x1 ≥ 0 and x2 ≥ 0. Only nonnegative amounts of
LP-1
,food can be eaten! These constraints are referred to as nonnegativity constraints. Nonnegativity
constraints appear in most linear programs. Moreover, not all possible values for x1 and x2 give
rise to a diet with the required amounts of nutrients per day. The amount of starch in x1 units of
G1 and x2 units of G2 is 5x1 + 7x2 and this amount must be at least 8, the daily requirement of
starch. Therefore, x1 and x2 must satisfy 5x1 + 7x2 ≥ 8. Similarly, the requirements on the amount
of proteins and vitamins imply the constraints 4x1 + 2x2 ≥ 15 and 2x1 + x2 ≥ 3.
This diet problem can therefore be formulated by the following linear program:
Minimize z = 0.6x1 + 0.35x2
subject to:
5x1 + 7x2 ≥ 8
4x1 + 2x2 ≥ 15
2x1 + x2 ≥ 3
x1 ≥ 0, x2 ≥ 0.
Some more terminology. A solution x = (x1 , x2 ) is said to be feasible with respect to the above
linear program if it satisfies all the above constraints. The set of feasible solutions is called the
feasible space or feasible region. A feasible solution is optimal if its objective function value is equal
to the smallest value z can take over the feasible region.
1.1.2 The Transportation Problem
Suppose a company manufacturing widgets has two factories located at cities F1 and F2 and three
retail centers located at C1, C2 and C3. The monthly demand at the retail centers are (in thousands
of widgets) 8, 5 and 2 respectively while the monthly supply at the factories are 6 and 9 respectively.
Notice that the total supply equals the total demand. We are also given the cost of transportation
of 1 widget between any factory and any retail center.
C1 C2 C3
F1 5 5 3
F2 6 4 1
Cost of transportation (in 0.01$/widget).
In the transportation problem, the goal is to determine the quantity to be transported from each
factory to each retail center so as to meet the demand at minimum total shipping cost.
In order to formulate this problem as a linear program, we first choose the decision variables.
Let xij (i = 1, 2 and j = 1, 2, 3) be the number of widgets (in thousands) transported from factory
Fi to city Cj. Given these xij ’s, we can express the total shipping cost, i.e. the objective function
to be minimized, by
5x11 + 5x12 + 3x13 + 6x21 + 4x22 + x23 .
We now need to write down the constraints. First, we have the nonnegativity constraints saying
that xij ≥ 0 for i = 1, 2 and j = 1, 2, 3. Moreover, we have that the demand at each retail center
must be met. This gives rise to the following constraints:
x11 + x21 = 8,
LP-2
, x12 + x22 = 5,
x13 + x23 = 2.
Finally, each factory cannot ship more than its supply, resulting in the following constraints:
x11 + x12 + x13 ≤ 6,
x21 + x22 + x23 ≤ 9.
These inequalities can be replaced by equalities since the total supply is equal to the total demand.
A linear programming formulation of this transportation problem is therefore given by:
Minimize 5x11 + 5x12 + 3x13 + 6x21 + 4x22 + x23
subject to:
x11 + x21 = 8
x12 + x22 = 5
x13 + x23 = 2
x11 + x12 + x13 = 6
x21 + x22 + x23 = 9
x11 ≥ 0, x21 ≥ 0, x31 ≥ 0,
x12 ≥ 0, x22 ≥ 0, x32 ≥ 0.
Among these 5 equality constraints, one is redundant, i.e. it is implied by the other constraints
or, equivalently, it can be removed without modifying the feasible space. For example, by adding
the first 3 equalities and substracting the fourth equality we obtain the last equality. Similarly, by
adding the last 2 equalities and substracting the first two equalities we obtain the third one.
1.2 Representations of Linear Programs
A linear program can take many different forms. First, we have a minimization or a maximization
problem depending on whether the objective function is to be minimized or maximized. The
constraints can either be inequalities (≤ or ≥) or equalities. Some variables might be unrestricted
in sign (i.e. they can take positive or negative values; this is denoted by ≷ 0) while others might
be restricted to be nonnegative. A general linear program in the decision variables x1 , . . . , xn is
therefore of the following form:
Maximize or Minimize z = c0 + c1 x1 + . . . + cn xn
subject to:
≤
ai1 x1 + ai2 x2 + . . . + ain xn ≥ bi i = 1, . . . , m
=
≥0
xj j = 1, . . . , n.
≷0
The problem data in this linear program consists of cj (j = 0, . . . , n), bi (i = 1, . . . , m) and aij
(i = 1, . . . , m, j = 1, . . . , n). cj is referred to as the objective function coefficient of xj or, more
LP-3
, simply, the cost coefficient of xj . bi is known as the right-hand-side (RHS) of equation i. Notice
that the constant term c0 can be omitted without affecting the set of optimal solutions.
A linear program is said to be in standard form if
• it is a maximization program,
• there are only equalities (no inequalities) and
• all variables are restricted to be nonnegative.
In matrix form, a linear program in standard form can be written as:
Max z = cT x
subject to:
Ax = b
x ≥ 0.
where
c1 b1 x1
c = ... , b = .. , x = ..
. .
cn bm xn
are column vectors, cT denote the transpose of the vector c, and A = [aij ] is the m × n matrix
whose i, j−element is aij .
Any linear program can in fact be transformed into an equivalent linear program in standard
form. Indeed,
• If the objective function is to minimize z = c1 x1 + . . . + cn xn then we can simply maximize
z 0 = −z = −c1 x1 − . . . − cn xn .
• If we have an inequality constraint ai1 x1 + . . . + ain xn ≤ bi then we can transform it into an
equality constraint by adding a slack variable, say s, restricted to be nonnegative: ai1 x1 +
. . . + ain xn + s = bi and s ≥ 0.
• Similarly, if we have an inequality constraint ai1 x1 + . . . + ain xn ≥ bi then we can transform it
into an equality constraint by adding a surplus variable, say s, restricted to be nonnegative:
ai1 x1 + . . . + ain xn − s = bi and s ≥ 0.
−
• If xj is unrestricted in sign then we can introduce two new decision variables x+
j and xj
+ −
restricted to be nonnegative and replace every occurrence of xj by xj − xj .
For example, the linear program
Minimize z = 2x1 − x2
subject to:
x1 + x2 ≥ 2
3x1 + 2x2 ≤ 4
x1 + 2x2 = 3
x1 ≷ 0, x2 ≥ 0.
LP-4
Linear programming
Lecturer: Michel Goemans
1 Basics
Linear Programming deals with the problem of optimizing a linear objective function subject to
linear equality and inequality constraints on the decision variables. Linear programming has many
practical applications (in transportation, production planning, ...). It is also the building block for
combinatorial optimization. One aspect of linear programming which is often forgotten is the fact
that it is also a useful proof technique. In this first chapter, we describe some linear programming
formulations for some classical problems. We also show that linear programs can be expressed in a
variety of equivalent ways.
1.1 Formulations
1.1.1 The Diet Problem
In the diet model, a list of available foods is given together with the nutrient content and the cost
per unit weight of each food. A certain amount of each nutrient is required per day. For example,
here is the data corresponding to a civilization with just two types of grains (G1 and G2) and three
types of nutrients (starch, proteins, vitamins):
Starch Proteins Vitamins Cost ($/kg)
G1 5 4 2 0.6
G2 7 2 1 0.35
Nutrient content and cost per kg of food.
The requirement per day of starch, proteins and vitamins is 8, 15 and 3 respectively. The problem
is to find how much of each food to consume per day so as to get the required amount per day of
each nutrient at minimal cost.
When trying to formulate a problem as a linear program, the first step is to decide which
decision variables to use. These variables represent the unknowns in the problem. In the diet
problem, a very natural choice of decision variables is:
• x1 : number of units of grain G1 to be consumed per day,
• x2 : number of units of grain G2 to be consumed per day.
The next step is to write down the objective function. The objective function is the function to be
minimized or maximized. In this case, the objective is to minimize the total cost per day which is
given by z = 0.6x1 + 0.35x2 (the value of the objective function is often denoted by z).
Finally, we need to describe the different constraints that need to be satisfied by x1 and x2 .
First of all, x1 and x2 must certainly satisfy x1 ≥ 0 and x2 ≥ 0. Only nonnegative amounts of
LP-1
,food can be eaten! These constraints are referred to as nonnegativity constraints. Nonnegativity
constraints appear in most linear programs. Moreover, not all possible values for x1 and x2 give
rise to a diet with the required amounts of nutrients per day. The amount of starch in x1 units of
G1 and x2 units of G2 is 5x1 + 7x2 and this amount must be at least 8, the daily requirement of
starch. Therefore, x1 and x2 must satisfy 5x1 + 7x2 ≥ 8. Similarly, the requirements on the amount
of proteins and vitamins imply the constraints 4x1 + 2x2 ≥ 15 and 2x1 + x2 ≥ 3.
This diet problem can therefore be formulated by the following linear program:
Minimize z = 0.6x1 + 0.35x2
subject to:
5x1 + 7x2 ≥ 8
4x1 + 2x2 ≥ 15
2x1 + x2 ≥ 3
x1 ≥ 0, x2 ≥ 0.
Some more terminology. A solution x = (x1 , x2 ) is said to be feasible with respect to the above
linear program if it satisfies all the above constraints. The set of feasible solutions is called the
feasible space or feasible region. A feasible solution is optimal if its objective function value is equal
to the smallest value z can take over the feasible region.
1.1.2 The Transportation Problem
Suppose a company manufacturing widgets has two factories located at cities F1 and F2 and three
retail centers located at C1, C2 and C3. The monthly demand at the retail centers are (in thousands
of widgets) 8, 5 and 2 respectively while the monthly supply at the factories are 6 and 9 respectively.
Notice that the total supply equals the total demand. We are also given the cost of transportation
of 1 widget between any factory and any retail center.
C1 C2 C3
F1 5 5 3
F2 6 4 1
Cost of transportation (in 0.01$/widget).
In the transportation problem, the goal is to determine the quantity to be transported from each
factory to each retail center so as to meet the demand at minimum total shipping cost.
In order to formulate this problem as a linear program, we first choose the decision variables.
Let xij (i = 1, 2 and j = 1, 2, 3) be the number of widgets (in thousands) transported from factory
Fi to city Cj. Given these xij ’s, we can express the total shipping cost, i.e. the objective function
to be minimized, by
5x11 + 5x12 + 3x13 + 6x21 + 4x22 + x23 .
We now need to write down the constraints. First, we have the nonnegativity constraints saying
that xij ≥ 0 for i = 1, 2 and j = 1, 2, 3. Moreover, we have that the demand at each retail center
must be met. This gives rise to the following constraints:
x11 + x21 = 8,
LP-2
, x12 + x22 = 5,
x13 + x23 = 2.
Finally, each factory cannot ship more than its supply, resulting in the following constraints:
x11 + x12 + x13 ≤ 6,
x21 + x22 + x23 ≤ 9.
These inequalities can be replaced by equalities since the total supply is equal to the total demand.
A linear programming formulation of this transportation problem is therefore given by:
Minimize 5x11 + 5x12 + 3x13 + 6x21 + 4x22 + x23
subject to:
x11 + x21 = 8
x12 + x22 = 5
x13 + x23 = 2
x11 + x12 + x13 = 6
x21 + x22 + x23 = 9
x11 ≥ 0, x21 ≥ 0, x31 ≥ 0,
x12 ≥ 0, x22 ≥ 0, x32 ≥ 0.
Among these 5 equality constraints, one is redundant, i.e. it is implied by the other constraints
or, equivalently, it can be removed without modifying the feasible space. For example, by adding
the first 3 equalities and substracting the fourth equality we obtain the last equality. Similarly, by
adding the last 2 equalities and substracting the first two equalities we obtain the third one.
1.2 Representations of Linear Programs
A linear program can take many different forms. First, we have a minimization or a maximization
problem depending on whether the objective function is to be minimized or maximized. The
constraints can either be inequalities (≤ or ≥) or equalities. Some variables might be unrestricted
in sign (i.e. they can take positive or negative values; this is denoted by ≷ 0) while others might
be restricted to be nonnegative. A general linear program in the decision variables x1 , . . . , xn is
therefore of the following form:
Maximize or Minimize z = c0 + c1 x1 + . . . + cn xn
subject to:
≤
ai1 x1 + ai2 x2 + . . . + ain xn ≥ bi i = 1, . . . , m
=
≥0
xj j = 1, . . . , n.
≷0
The problem data in this linear program consists of cj (j = 0, . . . , n), bi (i = 1, . . . , m) and aij
(i = 1, . . . , m, j = 1, . . . , n). cj is referred to as the objective function coefficient of xj or, more
LP-3
, simply, the cost coefficient of xj . bi is known as the right-hand-side (RHS) of equation i. Notice
that the constant term c0 can be omitted without affecting the set of optimal solutions.
A linear program is said to be in standard form if
• it is a maximization program,
• there are only equalities (no inequalities) and
• all variables are restricted to be nonnegative.
In matrix form, a linear program in standard form can be written as:
Max z = cT x
subject to:
Ax = b
x ≥ 0.
where
c1 b1 x1
c = ... , b = .. , x = ..
. .
cn bm xn
are column vectors, cT denote the transpose of the vector c, and A = [aij ] is the m × n matrix
whose i, j−element is aij .
Any linear program can in fact be transformed into an equivalent linear program in standard
form. Indeed,
• If the objective function is to minimize z = c1 x1 + . . . + cn xn then we can simply maximize
z 0 = −z = −c1 x1 − . . . − cn xn .
• If we have an inequality constraint ai1 x1 + . . . + ain xn ≤ bi then we can transform it into an
equality constraint by adding a slack variable, say s, restricted to be nonnegative: ai1 x1 +
. . . + ain xn + s = bi and s ≥ 0.
• Similarly, if we have an inequality constraint ai1 x1 + . . . + ain xn ≥ bi then we can transform it
into an equality constraint by adding a surplus variable, say s, restricted to be nonnegative:
ai1 x1 + . . . + ain xn − s = bi and s ≥ 0.
−
• If xj is unrestricted in sign then we can introduce two new decision variables x+
j and xj
+ −
restricted to be nonnegative and replace every occurrence of xj by xj − xj .
For example, the linear program
Minimize z = 2x1 − x2
subject to:
x1 + x2 ≥ 2
3x1 + 2x2 ≤ 4
x1 + 2x2 = 3
x1 ≷ 0, x2 ≥ 0.
LP-4
