Lecture Notes in Linear Programming modeling

Dritan Nace

November 12, 2021

2
Introduction

These lecture notes are exclusively destined to students of UTC. It provides a

short introduction of linear programming theory with a special focus on model-
ing transportation and logistic problems.
Linear programming formulations are popular because the mathematics is nicer,
the theory is richer, and the computation simpler for linear problems than for
nonlinear ones. In particular several modelers and solvers of high quality are
available in the market.

i
ii INTRODUCTION
Contents

Introduction i

1 Introduction to Linear Programming 3

1.1 A first example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Linear Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Linear Program modeling . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Examples of Linear Programming problems . . . . . . . . . . . . 7
1.4.1 A simplified production problem . . . . . . . . . . . . . . 7
1.4.2 The knapsack problem . . . . . . . . . . . . . . . . . . . . 7
1.4.3 The diet problem . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.4 The art gallery problem . . . . . . . . . . . . . . . . . . . 8
1.4.5 A warehousing problem . . . . . . . . . . . . . . . . . . . 8
1.4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Logistic, transportation and scheduling problems modelling 13

2.1 Logistic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Single installation . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Full coverage . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3 Maximum coverage . . . . . . . . . . . . . . . . . . . . . . 15
2.1.4 P-center problem . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.5 P-median problem . . . . . . . . . . . . . . . . . . . . . . 16
2.1.6 Warehouse location . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Transportation problems . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 The transportation problem . . . . . . . . . . . . . . . . . 17
2.2.2 The travelling salesman problem . . . . . . . . . . . . . . 18
2.2.3 The maximal flow problem . . . . . . . . . . . . . . . . . 19
2.2.4 The minimum cost flow problem . . . . . . . . . . . . . . 19
2.2.5 The multi-flow problem . . . . . . . . . . . . . . . . . . . 20
2.3 Scheduling problems . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.1 The one-machine problem . . . . . . . . . . . . . . . . . . 21
2.3.2 Number of delayed tasks problem . . . . . . . . . . . . . . 22
2.3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Additional exercises . . . . . . . . . . . . . . . . . . . . . . . . . 23

1
2 CONTENTS
Chapter 1

Introduction to Linear
Programming

1.1 A first example

Let start with an example: Consider a production facility (or an activity) for a
manufacturing company. The facility is capable of producing a variety of prod-
ucts that, for simplicity, we shall enumerate as 1, 2, . . . , n. These products are
manufactured out of certain raw materials. Let us assume that there are m
di↵erent raw materials, which again we shall simply enumerate as 1, 2, . . . , m.
The decisions involved in managing/operating this facility are complicated and
arise dynamically as market conditions evolve around it. However, to describe
a simple, fairly realistic optimization problem, we shall consider a particular
snapshot of the dynamic evolution. At this specific point in time, the facility
has, for each raw material j = 1, 2, . . . , m, a known amount, say bj , on hand.
Furthermore, each raw material has at this moment in time a known unit market
value. We shall denote the unit value of the j th raw material by cj . In addition,
each product is made from known amounts of the various raw materials. That
is, producing one unit of product i requires a certain known amount, say aij
units, of raw material j. Also, the ith final product can be sold at the known
prevailing market price of pi euros per unit.

The problem we wish to consider is the one faced by the company’s pro-
duction manager. It is the problem of how to use the raw materials on hand.
Let us assume that the manager decides to produce xi units of the ith product,
i = 1, 2, . . . , n. As said above, the revenue associated with the production of
one unit of product i is pi . But there is also a cost of raw materials that must
be considered.
Pm
The cost of producing one unit of product i is expressed as j=1 aij cj.
Therefore, the net revenue associated with the production of one unit is the
di↵erence between the revenue and the cost. Since the net revenue plays an
important
Pm role in our model, we introduce notation for it by setting fi = pi
j=1 aij cj, which gives the objectif function:

3
f,a and b are parameters: known values
xi are decision variables because we dont know what is the best value of x in order to get the best profit

4 CHAPTER 1. INTRODUCTION TO LINEAR PROGRAMMING

n
X
max fi xi (1.1)
the objectif function i=1

Now, let look at the raw materials on hand. Assuming that he decides to
produce xi units of the ith product, i = 1, 2, . . . , n, the manager can’t produce
more product than he has raw material for. The amount of raw material j
consumed by a given production process is aij , and so he must adhere to the
following constraints:
n
X
aij xi  bj , j = 1, 2, . . . , m (1.2)
i=1

Last, requiring nonnegativity: the constraint function

xi 0, i = 1, 2, . . . , n (1.3)

To summarize, the production manager’s job is to determine production

values xi , i = 1, 2, . . . , n, so as to maximize (1.1) subject to the constraints
given by (1.2) and (1.3). This optimization problem is an example of a linear
programming problem. This particular example is often called the resource
allocation problem.

1.2 Linear Optimization

Optimization can be seen as the mathematical branch intended to handle a
complex decision problem, involving the selection of values for a number of
interrelated variables, by focusing attention on a single objective designed to
quantify performance and measure the quality of the decision. The objective
is maximizing (or minimizing, depending on the formulation) subject to the
constraints that may limit the selection of decision variable values. All depen-
dencies expressed through constraints or objective function are assumed linear.

In a linear program there can be distinguished:

1. Decision variables, that are the unknowns that the user needs to determine.

2. Objective (or optimization) function. This is used to express the objective

(minimization or maximization) in terms of the decision variables.

3. Constraints are functions that express the requirements on the relation-

ships between the decision variables.

4. Domain of variables allow to limit the set of decision variables as part of

continuousl/integer/positive... numbers.

5.
 linear programming because all functions used are
1.2. LINEAR OPTIMIZATION linear 5

Standard form of an LP formulation. The general mathematical programming

problem can be stated as: it's called programming
because we can model any
max f (x) (1.4a) problem with the same
subject to formulas in mathematics
hi (x) = 0, i = 1, 2, . . . , m (1.4b) similar to programming
languages that use same
gj (x)  0, j = 1, 2, . . . , p (1.4c) instructions models solving
x 2 S. (1.4d) programs

Where x is an n-dimensional vector of unknowns, x = (x1 , x2 , . . . , xn ), and

f , hi , i = 1, 2, . . . , m, and gj , j = 1, 2, . . . , p, are real-valued linear functions of
the variables x1 , x2 , . . . , xn .
The set S is a subset of n-dimensional space. The function f is the objec-
tive function of the problem and the equations, inequalities, and set restrictions
are constraints. Any particular combination of decision variables is referred to
as a solution. A solution is said feasible if it satisfies all constraint requirements.

In this course we will focus on a specific formulation called standard formu-

lation which is specified below:

n'est pas important

max c1 x1 + c2 x2 + · · · + cn xn (1.5a)
subject to
a11 x1 + a12 x2 + · · · + a1n xn = b1 (1.5b)
a21 x1 + a22 x2 + · · · + a2n xn = b2 (1.5c)
··· (1.5d)
am1 x1 + am2 x2 + · · · + amn xn = bm (1.5e)
xi 0, 8i 2 {1, . . . , n}. (1.5f)

Note that each of the constraints should be arranged such that all terms with
decision variables be on the left of the constraint realation, and the only part
that appears on the right is the constant term.
Converting various forms of LP to the standard form can be done as follows:

1. (Slack variables). Consider the problem as in the standard form but con-
straints are typically: ai1 x1 + ai2 x2 + · · · + ain xn  bi . These constraints
can be rewritten as equalities by adding a new variable (slack variable) to
the left hand side.

2. (Surplus variables). If the above linear inequalities are reversed: ai1 x1 +

ai2 x2 + · · · + ain xn bi . These constraints can be rewritten as equalities
by substracting a new variable (surplus variable) to the left hand side.

3. (Free variable). If xi 0 is not present and hence xi is free to take on

either positive or negative values. We then write xi = ui vi , where
ui 0 and vi 0. An alternative for converting to standard form when
xi is unconstrained in sign is to eliminate xi together with one of the
constraint equations.
 6 CHAPTER 1. INTRODUCTION TO LINEAR PROGRAMMING

Example. Consider the following problem:

max x1 + 3x2 + 4x3 (1.6a)

subject to
x1 + 2x2 + x3 = 5 (1.6b)
2x1 + 3x2 + x3 = 6 (1.6c)
x2 0, x3 0. (1.6d)

Considering x1 = 5 2x2 x3 the above can be rewritten as:

max x2 + 3x3 (1.7a)

subject to
x2 + x3 = 4 (1.7b)
x2 0, x3 0. (1.7c)

1.3 Linear Program modeling

Although in the majority of cases modelling a LP problem is straightforward,
in some others it may be needed to introduce new variables and/or to rearrange
the constraints. We will cite a few examples below:
In some situations expressing the objective function may need using maxmin or
minmax functions. Let be given variables x1 , x2 , . . . , xn , and the objective func-
tion consists in maximizing the minimum of them: max{min{x1 , x2 , . . . , xn }}. min is not a
This leads to a maxmin function which cannot be expressed straightly by linear linear function we
programming. A simple way to deal with it is to introduce a new variable y need to linearize
which is a lower bound of xj , and state the problem as follows: it we replace it by
y the value of y is
max y (1.8a) a lower bound for
subject to the set of x
xj y, j = 1, . . . , n (1.8b) the largest
lower bound is
... the minimum
better solution In some other situations some multiplicative functions may be found. A
because the simple example is min{1/x} which may be simply expressed as max{x}. In
condition is to give some other situations we may have bilinear terms ax where both a and x are
the most possible fo decision variables. Although in the general case such a formulation cannot be
each product linearized, it can be easily handled when one of them is binary and the other
is upperly bounded. Let suppose that x is a binary variable and a 2 {0, .., M }.
Than let first introduce a new variable y = ax. This new variable (y) is used
instead of expression ax wherever it appears in the model. Now one needs to
1.4. EXAMPLES OF LINEAR PROGRAMMING PROBLEMS 7

add new constraints to make y( 0) to behave properly, that is,

ya (1.9a)
y  Mx (1.9b)
y a + (x 1)M (1.9c)

where M is a large value constant. The case when both are binary variables is
handled similarly.
Di↵erent situations may be met when modeling constraints as well. For
instance, the so-called capacity constraints usually give rise to upper bound
constraints; In the same line, demand constraints will usually give rise to lower
bound constraints. Another type of frequently met constraint is the socalled
mass balance one, which expresses the requirement of conservation of mass. An
obvious example of this constraint is found in flow problems when expressing
that the amount of flow entering in some transit node is equal to the amount of
flow going out.
Another type of constraints are the proportion constraints where one decision
variable needs to represent a fixed part of a given sum. For instance, let a, b and
c give all, and a is required to be exactly 30% of all. Then, it can be expressed
as: a = 0.3(a + b + c).

1.4 Examples of Linear Programming problems

1.4.1 A simplified production problem
Determine the quantities to be produced such that all the production constraints
are satisfied and the profit is maximized. We suppose that two products A and
B can be produced, each of them passing through cutting and packing stages:
Necessary time to produce 1 unity of A is 2 hours for cutting and 3 hours for
packing. Necessary time to produce 1 unity of B is 2 hours for cutting and 1
hour for packing. Availability in working hours is 200 hours for cutting and 100
hours for packing. The unitary profits for A and B are respectively 20 and 10
euros.
This problem falls in the category of Resource Allocation problems studied in
Section 1.1. Writing the LP formulation is left to the reader.

1.4.2 The knapsack problem

The knapsack problem (KP) has a significant place in the study of integer pro-
gramming models with binary variables. In the knapsack problem, one needs to
pack a set of items (I), with given values (v) and sizes (w) (such as weights or
volumes), into a container with a maximum capacity (C). If the total size of the
items exceeds the capacity, we can’t pack them all. In that case, the problem
is to choose a subset of the items of maximum total value that will fit in the
container. The decision variables are represented by binary variables xi taking
value 1 if item i is selectedPand packed into thePcontainer and 0 otherwise. The
objective function is max i2I vi xi such that i2I wi xi  C.
8 CHAPTER 1. INTRODUCTION TO LINEAR PROGRAMMING

1.4.3 The diet problem

We assume that there are available at the market n di↵erent foods and that the
j th food sells at a price cj per unit. In addition there are m basic nutritional
ingredients and, to achieve a balanced diet, each individual must receive at least
bi units of the ith nutrient per day. Finally, we assume that each unit of food j
contains aij units of the ith nutrient.
If we denote by xj the number of units of food j in the diet, the problem then
is to select the xj ’s to minimize the total cost: c1 x1 + c2 x2 + · · · + cn xn subject
to the nutritional constraints: ai1 x1 + ai2 x2 + · · · + ain xn bi , i = 1, . . . , m, and
the non-negativity constraints: xj 0 for all j.

1.4.4 The art gallery problem

The art gallery problem is a well-studied optimization problem. It originates

from a real-world problem of guarding an art gallery with the minimum number
of guards who together can observe the whole gallery. In the geometric version
of the problem, the layout of the art gallery is represented by a simple polygon
and each guard is represented by a point in the polygon. In the graph theory
version the problem is represented as the vertex cover of an undirected graph
problem. A vertex cover of an undirected graph G = (V, E) is a subset of its
vertices such that for every edge (u, v) of the graph, either u or v is in the vertex
cover. Although the name is Vertex Cover, the set covers all edges of the given
graph. Given an undirected graph, the vertex cover problem is to find minimum
size vertex cover. If we denote by xi the binary variable indicating if vertex i is
in the Vertex Cover or not, the problem then is to select the xi ’s to minimize:
x1 + x2 + · · · + xn subject to the covering constraints: xi + xj 1, 8(i, j) 2 E
and the binary constraints: xi 2 {0, 1} for all vertex i.

1.4.5 A warehousing problem

Consider the problem of operating a warehouse, by buying and selling the stock
of a certain commodity, in order to maximize profit over a certain length of time,
say n months. The warehouse has a fixed capacity C, and there is a cost r per
unit for holding stock for one period. The selling price, pi , of the commodity is
known to fluctuate over a number of time periods n indexed by i. In any period
i the price holding for purchase is fi . The warehouse is originally empty and is
required to be empty at the end of the last period.
To formulate this problem, variables are introduced for each time period. In
particular, let zi denote the level of stock in the warehouse at the beginning of
period i. Let xi denote the amount bought during period i, and let yi denote
the amount sold during period i. If there are n periods, the problem may be
written as:
1.4. EXAMPLES OF LINEAR PROGRAMMING PROBLEMS 9

n
X n
X n
X
min fi xi pi yi + zi r (1.10a)
i=1 i=1 i=1
subject to
x i + zi yi = zi+1 1  i  n (1.10b)
zi  C 1  i  n (1.10c)
z1 = zn+1 = 0 (1.10d)
x, y, z 0. (1.10e)
 10 CHAPTER 1. INTRODUCTION TO LINEAR PROGRAMMING
les exercices 1 2 3 ne sont pas demandes
1.4.6 Exercises
1. Convert the following problem to standard form:

max x + 2y + 3z (1.11a)
subject to
6  x + y + z  15, (1.11b)
x 2, y 0, z 0 (1.11c)

2. Convert the following problem to standard form and solve:

max x1 + 4x2 + x3 (1.12a)

subject to
2x1 2x2 + x3 = 4 (1.12b)
x1 x3 = 1 (1.12c)
x2 0, x3 0. (1.12d)

3. Convert the following problem to a linear program in standard form:

min |x| + y + z (1.13a)

subject to
x+y 1 (1.13b)
2x + z = 3 (1.13c)
y, z 0 (1.13d)

4. A class of piece-wise linear functions can be represented as f (x) =

max(cT1 x + d1 , cT2 x + d2 , ..., cTp x + dp ). For such a function f , consider the
problem minimize f (x) subject to Ax = b, x 0. Show how to convert this
problem to a linear programming problem
5. A manufacturer wishes to produce to produce 1000 lb of an alloy that is,
by weight, 30% metal A and 70% metal B. Five alloys are available at various
prices as indicated below:

Alloy 1 2 3 4 5
%A 10 25 50 75 95
%B 90 75 50 25 5
Price/lb 5 4 3 2 1.50

The desired alloy will be produced by combining some of the other alloys.
The manufacturer wishes to find the amounts of the various alloys needed and to
determine the least expensive combination. Formulate this problem as a linear
program.
6. A small firm specializes in making five types of spare automobile parts.
Each part is first cast from iron in the casting shop and then sent to the finishing
shop where holes are drilled, surfaces are turned, and edges are ground. The
required worker-hours (per 100 units) for each of the parts of the two shops are
shown below:
.''
1.4. EXAMPLES OF LINEAR PROGRAMMING PROBLEMS 11

Part 1 2 3 4 5
Casting 2 1 3 3 1
Finishing 3 2 2 1 1

The profits from the parts are 30, 20, 40, 25, and 10 (per 100 units), respec-
tively. The capacities of the casting and finishing shops over the next month are
700 and 1000 worker-hours, respectively. Formulate the problem of determining
the quantities of each spare part to be made during the month so as to maximize
profit.
7. A small computer manufacturing company forecasts the demand over
the next n months to be di , i = 1, 2, . . . , n. In any month it can produce at
most r units, using regular production, at a cost of b dollars per unit. By using
overtime, it can produce additional units at c dollars per unit, where c > b.
The firm can store units from month to month at a cost of s dollars per unit
per month. Formulate the problem of determining the production schedule that
minimizes the cost.
12 CHAPTER 1. INTRODUCTION TO LINEAR PROGRAMMING
Chapter 2

Logistic, transportation and

scheduling problems modelling

In today’s global economies, transportation is a key facilitator of trade, and

hence an important factor in rising prosperity and welfare. Natural resources
are scarce and not evenly distributed in terms of type and geographical loca-
tion in the world. Transportation and logistic chains enable the distribution
of materials, food and products from the locations where they are extracted,
harvested or produced to people’s homes and nearby stores. At the same time,
current logistics systems are fundamentally unsustainable, due to the emission
of CO2, congestion, noise and the high price that has to be paid in terms of
infrastructural load. Hence, there are problems that are necessary to solve in
practice and transport and logistics problems belong among them. The correct
optimization of such problems enables us to minimize the cost and time.
Another group of interesting problems comes from scheduling. Scheduling is
concerned with the allocation of scarce resources to activities with the objective
of optimizing one or more objectives. Depending on the situation, resources
may be machines in an assembly plant, CPU or memory in a computer system,
runways at an airport, etc. With respect to above, activities may be various
operations in a manufacturing process, execution of a computer program, land-
ings and take-o↵s at an airport, and so on. There also may be di↵erent criterion
to optimize. One objective may be the minimization of the makespan, while
another objective may be the minimization of the number of late jobs.
The focus of this chapter is in introducing some typical optimization prob-
lems in each of above areas together with their linear formulations.

2.1 Logistic problems

Among the logistic problems, the facility Location Problem is perhaps one of
the most important topics in industrial engineering and operations research.
It aims to take strategic decisions for distribution of goods, services, and in-
formation. There are plenty of applications for hub location problem, such as
Transportation Management, Urban Management, locating service centers, In-
strumentation Engineering, design of sensor networks, Computer Engineering,
design of computer networks, Communication Networks Design, Power Engi-

13
14CHAPTER 2. LOGISTIC, TRANSPORTATION AND SCHEDULING PROBLEMS MODELLING

neering, localization of repair centers, and Design of Manufacturing Systems.

Today, we note that the markets are becoming larger, but often with a more
dispersed clientele, deliveries easier thanks to the opening of borders but more
competitive. In the problems we are presenting, the general objective is to de-
termine the optimal location of a number of facilities on a set of possible sites,
so as to minimize the number of installations to cover all demands, or maximize
the demand covered with a fixed number of installations, or minimize costs when
delivery issues are also concerned (the facility location-allocation), it depends
on the application on hand. Then, the questions to be answered are: How many
installations? Where to place them? How to assign requests to sites?

2.1.1 Single installation

Consider first a very simple case: the location of a single installation. Data is
composed of m possible sites, n entities (customers, suppliers, etc.) to be served,
and a simple load measurement Lj for each entity j, to be defined. Depending
on the activity, this may be a tonnage of goods entering or leaving the site, a
number of weekly trips, etc. Also, distances dij between any site i and any entity
j are known. The objective is to choose a site i⇤ minimizing a score estimating
the work of moving loads.
The solution method is simply calculating for any site i of a load-distance
score ld(i), Pand choosing the site with the minimum score.
ld(i) = j=1..n Lj dij
A special case of above is the ”Center of gravity” problem. This is a variant
of continuous localization which consists of determining the center of gravity of
loads, i.e. the geographical location (x⇤ , y ⇤ ), e.g. longitude and latitude, is to
be determined, so we only consider the entities to be served, (whose coordinates
(xi yi ) are known), and not the sites.
Question: Give the formulas for calculating x⇤ and y ⇤ .

2.1.2 Full coverage

The problem of full coverage raises when one seeks to cover all clients/requests
in a given area. The problem may be expressed as follows.
Data:

• n potential sites (indexed by i),

• m demand points (indexed by j),

• distances dij between any site i and any entity j.

• Dc coverage distance beyond which a customer cannot be served,

• constants (0,1) denoted by aij indicating whether the point of demand j

is covered by the site i, that is aij = 1 ' dij  Dc .

• ci cost of opening a site i,

Objective: calculate the sites to be opened to cover all the requests, with a
minimum total cost.
Binary linear programming formulation:
2.1. LOGISTIC PROBLEMS 15

n
X
min c i xi (2.1a)
i=1
subject to
n
X
ai,j xi 1, 8j 2 {1, . . . , m} (2.1b)
i=1
xi 2 {0, 1}, 8i 2 {1, . . . , n}. (2.1c)

2.1.3 Maximum coverage

In contrast to the precedent problem, we give up total coverage and seek for
maximizing the demand covered with a limited number of sites to open. Pa-
rameters and additional variables are:
• p: maximum number of sites to open,
• dj : request/demand of point j,
• zj : binary variable indicating whether demand j is covered.
Formulation of the problem as a binary linear program follows:

m
X
max d j zj (2.2a)
j=1

subject to
n
X
zj  ai,j xi 8j 2 {1, . . . , m} (2.2b)
i=1
n
X
xi  p, (2.2c)
i=1
xi 2 {0, 1}, 8i 2 {1, . . . , n} (2.2d)
zj 2 {0, 1}, 8j 2 {1, . . . , m}. (2.2e)

2.1.4 P-center problem

The p-center problem is a relatively well known facility location problem that
involves locating p identical facilities on a network to minimize the maximum
distance between demand nodes and their closest facilities. The focus of the
problem is on the minimization of the worst case service time.
Parameters and additional variables are:

•M
n: a set of a number of nodes to serve,
• a set of n sites, of which only p sites can open,
• Distance matrix dij between sites and nodes,
• yij : a binary variable taking 1 if site i is covering demand j,
16CHAPTER 2. LOGISTIC, TRANSPORTATION AND SCHEDULING PROBLEMS MODELLING

• z: is the maximum covering distance.

The objective is to place the sites to minimize the maximum intervention

distance. An example is placement of fire stations, etc.

min z (2.3a)
subject to
n
X
yij = 1, 8j 2 {1, . . . , m} (2.3b)
i=1
X
xi  p, (2.3c)
i
n
X
dij yij  z, 8j 2 {1, . . . , m} (2.3d)
i=1
yij  xi , 8i 2 {1, . . . , n}, 8j 2 {1, . . . , m} (2.3e)
xi 2 {0, 1}, 8i 2 {1, . . . , n} (2.3f)
yij 2 {0, 1}, 8i 2 {1, . . . , n}, 8j 2 {1, . . . , m}. (2.3g)

2.1.5 P-median problem

In contrast to the p-center problem, the p-median one looks for minimizing
the average intervention distance. An example is the placement of warehouses
to minimize the average travel time to deliver a customer. So, the p-median
problem seeks to minimize the average intervention distance, possibly weighted
by the demands of the nodes denoted with qj below. Linear programming
formulation follows:

m
X X
min qj dij yij (2.4a)
j=1 i

subject to
n
X
yij = 1, 8j 2 {1, . . . , m} (2.4b)
i=1
n
X
xi  p, (2.4c)
i=1
yi,j  xi , 8i 2 {1, . . . , n}, 8j 2 {1, . . . , m} (2.4d)
xi 2 {0, 1}, 8i 2 {1, . . . , n} (2.4e)
yi,j 2 {0, 1}, 8i 2 {1, . . . , n}, 8j 2 {1, . . . , m}. (2.4f)

2.1.6 Warehouse location

This problem arises when one seeks to minimize the total cost including the fixed
cost of opening and operating the sites and the cost of transportation. It is then
necessary to decide which sites to open and what quantities to deliver from
any site to any customer. This classic problem is called the warehouse location
2.2. TRANSPORTATION PROBLEMS 17

problem. We denote with fi the opening cost, dj the demand corresponding to

certain period, and with cij the delivery unitary cost from i to j. Variables yij
denote the quantity of demand j covered by site i and M gives a sufficiently
large constant.
Linear programming formulation follows:

n
X m X
X n
min fi xi + cij yij (2.5a)
i=1 j=1 i=1

subject to
n
X
yij = dj , 8j 2 {1, . . . , m} (2.5b)
i=1
m
X
yi,j  M xi 8i 2 {1, . . . , n}, (2.5c)
j=1

xi 2 {0, 1}, 8i 2 {1, . . . , n} (2.5d)

yij 0, 8i 2 {1, . . . , n}, 8j 2 {1, . . . , m}. (2.5e)

2.2 Transportation problems

There are various transport issues between sources with given availabilities and
destinations with given demands to be satisfied. Links in the network have costs
that should be taken in account when writing down the cost (objective) function
for problems like:
• transport problem,
• assignment problem,
• transshipment problem,
• optimal path problems,
• vehicle routing problems.
In some other cases, links have capacities:
• maximum flow problem,
• minimum cost flow problem,
• multi-flow problem.

2.2.1 The transportation problem

Quantities a1 , a2 , ..., an , respectively, of a certain product are to be shipped
from each of n locations and received in amounts b1 , b2 , . . . , bm , respectively,
at each of m destinations. A shipping cost cij is associated with the ship-
ping of a unit of product from origin i to destination j. It is desired to de-
termine the amounts xij to be shipped between each origin-destination pair
i = 1, 2, . . . , n; j = 1, 2, . . . , m; so as to satisfy the shipping requirements and
18CHAPTER 2. LOGISTIC, TRANSPORTATION AND SCHEDULING PROBLEMS MODELLING

minimize the total cost of transportation. The problem is representable graph-

ically by a bipartite graph.

n X
X m
min cij xij (2.6a)
i=1 j=1

subject to
m
X
xij  ai , i = 1, 2, . . . , n (2.6b)
j=1
n
X
xij bj , j = 1, 2, . . . , m (2.6c)
i=1
xij 0, i = 1, 2, ..., n; j = 1, 2, . . . , m. (2.6d)

The assignment problem is a transportation problem with availability and

requests fixed at 1 and n = m.
In the transshipment problem, the graph has infinite capacity arcs but is no
longer bipartite, that is, some intermediate nodes/destinations are present in
the graph.

2.2.2 The travelling salesman problem

The travelling salesman problem, known as TSP problem, one of the most fa-
mous in the group of vehicle routing problems and more largely in combinatorial
optimization. It consists in computing, for a given list of cities and the distances
between each pair of cities, the shortest possible route that visits each city ex-
actly once and returns to the origin city. The travelling salesman problem
was mathematically formulated in the 1800s by the Irish mathematician W.R.
Hamilton, which problem is known in graph theory as the Hamiltonian cycle
one. Let G = (V, E) be the graph composed of n nodes (V ) representing cities
and arcs (E) representing direct links between cities weighted by their distance
(dij ). Let xij represent the decision variables taking 1 if arc (ij) is chosen to be
in the circuit and 0 otherwise. The problem may be formulated as follows:

X
min dij xij (2.7a)
i,j

subject to
n
X
xij = 1, 8i = 1, 2, . . . , n (2.7b)
j=1
Xn
xij = 1, 8j = 1, 2, . . . , n (2.7c)
i=1
X
xij 1, 8S ⇢ V (2.7d)
i2S,j2V \S

xij 2 {0, 1}, 8i = 1, 2, . . . , n, j = 1, 2, . . . , n (2.7e)

2.2. TRANSPORTATION PROBLEMS 19

In
Clearly constraints (2.7d) are very numerous and cannot be all put explicitly.
Then, we start with a subset of such constraints and solve the problem. The
obtained solution x is necessarily composed of circuits and all nodes are visited.
If the solution corresponds to a single circuit, then the solution is optimal,
otherwise one can build a constraint of type (2.7d) by putting in a set S all
nodes contained in a sub-tour and next add it in the formulation and solve
again the augmented problem1 .

2.2.3 The maximal flow problem

Consider a capacitated network N = (V, E, C) with n nodes (V ) in which two
special nodes, called the source s and the sink t, are distinguished. All other
nodes must satisfy the strict flow conservation requirement; that is, the net flow
into these nodes must be zero. The outflow f of the source will equal the inflow
of the sink as a consequence of the conservation at all other nodes. There is also a
defined a capacity vector C. An arc connecting node i to node j is denoted with
(i, j) 2 E. The flow passing on each arc should satisfy the capacity constraint,
that is sum of flows passing through arc (i, j) should be less or equal to Cij . A
set of arc flows satisfying these conditions is said to be a flow in the network of
value f . U + (i) and U (i) denote respectively the out-neighbourhood and the
in-neighbourhood of node i. The maximal flow problem is that of determining
the maximal flow that can be established in such a network.

X
Minimum en

·
max f (2.8a)
subject to
X X

-
xsj xjs f = 0, (2.8b)

-
le
-
j2U + (s) j2U (s)
X X -

xij xji = 0, i = {1, . . . , n} \ {s, t} (2.8c)

j2U + (i) j2U (i)

xij  Cij , (i, j) 2 E, (2.8d)

xij 0, (i, j) 2 E. (2.8e)

2.2.4 The minimum cost flow problem

The minimum cost flow problem is that of determining a flow of a given value
f of minimal cost. The cost is represented by vector w. Then, the problem can

:
be formulated as the -
maximum flow problem instead that f is now a parameter
and the objective function becomes:

O
X
min wi,j xi,j
-
(i,j)2E

1 Other formulations are also possible. Another option to avoid sub-tours is to add some

variables and constraints. Then, instead of constraints (2.7d), we add new variables ui (one
per node) and constraints: ui uj  n 1; 2  i 6= j  n, ui 2 N It can be shown that this
constraint avoids having sub-tours in the obtained solution.
20CHAPTER 2. LOGISTIC, TRANSPORTATION AND SCHEDULING PROBLEMS MODELLING

2.2.5 The multi-flow problem

The related multi-flow problems are like the flow one but several commodities,
called d, d 2 D, are sharing the same network. One commodity is determined
by its origin (or source) and destination (or sink) nodes s(d) and t(d), and its
achieved value fd . The minimum cost multi-commodity flow problem, where fd
is a given parameter, is formulated as:

X X
min wi,j xdi,j (2.9a)
(i,j)2E d

subject to
X X
xds(d),j xdj,s(d) = fd , 8d 2 D (2.9b)
j2U + (sd)) j2U (s(d))
X X
xdij xdji = 0, 8d 2 D, 8i 2 V \ {s(d), t(d)} (2.9c)
j2U + (i) j2U (i)
X
xdij  Cij , 8(i, j) 2 E (2.9d)
d2D

xdij 0, 8d 2 D, 8(i, j) 2 E. (2.9e)

Exercises

1. The minimum cost maximum flow problem is that of determining among

the maximal flows that can be established in such a network, the one of
minimal cost. How one can solve this problem?
2. Use the minimum cost flow problem formulation given above to formulate
the minimum shortest path problem.

2.3 Scheduling problems

The study of scheduling dates back to 1950s. Researchers in operations re-
search, industrial engineering,and management were faced with the problem of
managing various activities occurring in a workshop. Next, beginning in the
late 1960s, computer scientists also encountered scheduling problems in the de-
velopment of operating systems. Back in those days, computational resources
(such as CPU, memory and I/O devices) were scarce. Efficient utilization of
these scare resources can lower the cost of executing computer programs. This
provided an economic reason for the study of scheduling.
Today, the community is interested in di↵erent problems like single machine
problems, flow-shop and job-shop scheduling problems, the resource-constrained
project scheduling problem, etc. In general, these problems are tackled by spe-
cific algorithms, but more recently other methods as constraint programming
and mathematical (linear) programming are also studied. In the following we
will look at two well-known problems that are the one machine problem and the
number of delayed tasks.
Generally speaking, problem formalization of scheduling problems is con-
cerned with data including tasks/jobs (ready time, processing time, due time),
 2.3. SCHEDULING PROBLEMS 21

number of machines, precedence constraints, preemption, etc. The notation

used are as follows:

• Parameters (per task i): ri (ready time), pi (processing time), di (due

time);

• Decision variables: ti (start date of execution of task i), xij (execution of

task i at order j), ci (completion execution time of task i).

• Precedence/conjunctive constraints such that task i before task j are ex-

pressed as ti + pi  tj ;

• Disjunctive constraints may be expressed as: ti + pi  tj or tj + pj  ti ;

ti +pi  tj +M (1 b); tj +pj  ti +M b; b 2 {0, 1}, where M is a sufficiently
large value.

• Objective function is generally concerned with minimization of completion

time (makespan), total lateness, number of delayed tasks, etc.

2.3.1 The one-machine problem

We consider the n-job one-machine scheduling problem with ready time ri , pro-
cessing time pi , and due time di for each job i. Preemption is not allowed, and
precedence constraints among jobs are not considered. Decision variables: xij
(boolean variables): task i executed at the j th order; tj ( 0) start time for task

IE
placed at order j; M

LP formulation of one-machine problem:

D Deloi ef teste X ar su(2.10a)

je port
min tn + xin pi
in order
J ↓
i
subject to

deloged
n
X
1 xij = 1, 8i = 1, 2, . . . , n (2.10b)
j=1

Yj
=
o othermise Xn
xij = 1, 8j = 1, 2, . . . , n (2.10c)
i=1
n
X ryzo
-----
tj
i=1
xij ri , 8j = 1, 2, . . . , n (2.10d)

n
X
V .
tj + xij pi  tj+1 , 8j = 1, 2, . . . , n (2.10e)

&3
i=1

Mjj tj +
n
X
xij pi 
n
X
xij di , 8j = 1, 2, . . . , n (2.10f)
i=1 i=1
xij 2 {0, 1}, 8i = 1, 2, . . . , n, j = 1, 2, . . . , n (2.10g)

Egli
22CHAPTER 2. LOGISTIC, TRANSPORTATION AND SCHEDULING PROBLEMS MODELLING

2.3.2 Number of delayed tasks problem

In contrast with the one-machine problem, the the number of delayed tasks
problem concerns a set I = 1, 2, ..n of tasks of duration 1 and deadlines di , a
partial order < denoted with P rec on I. The objective is to achieve a scheduling
of these tasks on one machine satisfying the partial order and such that the
number of delayed tasks is the smallest possible.
LP formulation:

X
min yj (2.11a)
j

subject to
ti < tj 8(i, j) 2 P rec, (2.11b)
tj + 1  dj + M yj , 8j = 1, 2, . . . , n (2.11c)
tj 0, 8j = 1, 2, . . . , n (2.11d)
yj 2 {0, 1}, 8j = 1, 2, . . . , n (2.11e)

where tj ( 0) is a decision variable indicating the starting time of job j and yj

is a binary variable taking 1 if task j is delayed and 0 otherwise.

2.3.3 Exercises
Exercise 1. The company Tapisall must fulfill a command of three models of
wallpaper: one (model 1) has a blue background with green patterns, another
(model 2) has a green background with blue patterns, and the last ( model 3) is
entirely in green. Each model is manufactured as a roll of continuous paper that
passes over several machines, each printing a di↵erent color (machine 1 for blue
color and machine 2 for green). The order of passage on the machines varies
from model to model: we first print the blue background on model 1, then
the green patterns. For model 2, apply the green background, then the blue
patterns. We also know that for operational reasons model 3 must be processed
first on machine 2 (compared to the other two models on the same machine)
and that any started task must be completed before starting another one. The
execution time of these operations is variable according to the surface to be
printed. The times (in minutes) required to apply each color to each model are
denoted with pij , that is duration of process i on machine j.

Exercise 2. Assuming that there is no solution satisfying all deadline con-

straints of one-machine problem, one is looking for minimization of total delays.
We assume that all ready times are not an issue as they are fixed at rj = 0 for
each job j. Modify the above formulation to handle this objective. Consider
also the case when one looks for minimization of the number of delayed tasks.
 ·
P22
model ! L ,

=I
T
-

model 2 Pas
2.4. ADDITIONAL EXERCISES 23

2.4 Additional exercises

Exercise 1. The cafeteria
To operate a cafeteria, the manager must ensure on-call duty based on the
statistics on the required sta↵. Then number of desired employees on day j is
denoted with Dj .
Question: Calculate the minimum number of employees to hire knowing that
an employee works 5 days in a row and then has two days o↵.

Exercise 2. Running a foundry

A foundry receives a specific order for 1, 000 tons of steel. This steel must
meet the following characteristics: it must contain at least 0.45% manganese
(Mn) while its percentage of silicon (SI) must be between 3.25 and 5. To cast
this steel, the foundry has limited quantities of three types of minerals: A, B
and C. The contents expressed in (%) per A, B and C are respectively 4, 1, and
0.6 for Si and 0.45, 0.5 and 0.4 for Mn.
The process for producing steel is such that direct addition of Mn is possible.
This Manganese is available at a price of 8 million euros (ME) per ton. As for
the minerals, they cost respectively 21 ME per thousand tons for type A, 25
ME for B and 15 ME for C.
If the foundry plans to sell the steel produced at 0.45 ME per ton, how should it
manufacture the 1000 tons requested in order to maximize profit, knowing that
the cost of smelting a ton of mineral is 0.005 ME?

Exercise 3. Balanced loading

N SNCF wagons with a payload limited to a weight P are reserved for trans-
porting m boxes. The boxes 1, 2, . . . , m and their weight p1 , p2 , .., pm are known.
It is accepted that there is a way to put all boxes in the wagons.
Question 1. How to allocate the boxes to the wagons so as to respect the max-
imum payloads and to minimize the load of the most loaded wagon. Model the
problem as a linear program.
Question 2. Study the case of two wagons. Make the connection with the
(well-known) knapsack problem.

Exercise 4. Backing up files

Before going on vacation you want to make floppy disk backups of important
files. You have at your disposal p blank floppy disks with capacities of C GB.
They are given the size of the n files that you want to save. Assuming that
you do not have any programs to compress the data and that you have enough
floppy disks available for back up everything, how to distribute these files on
the floppy disks in order to minimize the number of floppy disks used.

Exercise 5. Street surveillance with cameras

A municipality wants to install cameras at the intersections of an industrial
zone following repeated thefts. It is assumed that each portion of the street
between two intersections is in a straight line. A camera installed at an inter-
section can rotate 360 degrees and see all the adjacent streets. The municipality
wishes to install a minimum number of cameras. Suggest a mathematical model
24CHAPTER 2. LOGISTIC, TRANSPORTATION AND SCHEDULING PROBLEMS MODELLING

for this problem. The surveillance zone can be represented by a graph where
the nodes are the crossroads and the arcs are the streets.

Exercise 6. A transport problem

An Italian transport company must send empty containers from its n depots
to m ports. The number of containers available in the depots is denoted with ai .
Container requirements in ports are denoted with bj . Transport of containers
by barges. Each barge can only contain two containers and the cost of transport
(per barge) is proportional to the distance traveled (p Euros/km). The distances
are given and denoted with Dij .
Formulate as a Linear Program the minimal cost transport problem.

Exercise 7. A transport problem: delivery of heavy packages

A transport company has to deliver to suburban customers n packages with
known weights. The transport company has m vehicles that can carry the maxi-
mum payloads pj at the daily costs cj also known. Each vehicle can only deliver
in the same day packages whose sum of weights does not exceed its payload.
Question 1. Determine the minimum cost transport daily plan (vehicle / pack-
age). Give the corresponding Linear Program.
Question 2. How can I be sure that packages l and q will not be delivered by
the same vehicle?

Exercise 8. Combined transport

A cargo of T tons must be transported on a fixed route of n cities (from
city 1 to 2, ..., to n), with three modes of transport to choose from: rail, road,
air. You can change mode at each of the intermediate cities i : i 2 {2..n 1},
but the cargo must take a single mode j : j 2 {1..3} between two consecutive
cities. The transport costs wi,j (starting from city i : i 2 {1..n 1} and using
mode j : j 2 {1..3}) are given parameters as well as the costs of mode changes
cj,k , j 2 {1..3}, k 2 {1..3}.
Question. Model the problem as a Linear Program whose objective is to mini-
mize the total cost of transport.