Operations Research 1

Prof. Dr. Marco Lübbecke

marco.luebbecke@rwth-aachen.de
@mluebbecke

Lehrstuhl für Operations Research

www.or.rwth-aachen.de
@or rwth orrwth
Aims of this Chapter

I get acquainted with several classical textbook optimization problems

→ these are often much simpler than practical problems
→ but they serve as building blocks for more realistic situations
I thereby learn a rich set of modeling techniques in integer linear programming
⇒ you become “fluent” in formulating integer programs

I obtain a basic understanding of what constitutes a good model

I obtain a very basic understanding of how to improve a model
 This Course: Mixed-Integer Linear Programs

Mixed-Integer Linear Programs (MILP, MIP)

min ct x
s.t. Ax ≥ b
x ∈ Zn+ × Qq+
gemischt-ganzzahliges lineares Programm

special cases
I n = 0 linear program (LP)
I q = 0 (pure) integer linear program (ILP, IP)
I x ∈ {0, 1}n binary program (BP)

2 Modeling with Integer Variables · 2.0 · p. 2.0-3

 The Need for Integer Variables

I continuous variables x ∈ Q work well to model amounts of divisible goods, filling

rates, percentages/shares etc.
→ think of all the mixing tasks you have modeled with linear programs
I in practice we (much) more often encounter situations where integrality x ∈ Z
must be enforced
→ e.g., amounts of indivisible goods (like trucks, persons)
I binary variables x ∈ {0, 1} will help us model logical constraints
→ e.g., yes-no-decisions, implications, . . .

I integer programs will prove to be extremely more powerful modeling tools than
linear programs

2 Modeling with Integer Variables · 2.0 · p. 2.0-4

Overview on Chapters

1 Introduction

2 Modeling with Integer Variables

2.1 Integer Linear Programs
2.3 Non-Linear Integer Programs
2.4 Relaxations and Strength of Models
2.5 Cutting Planes

3 Exact Algorithms

4 Heuristics

5 From Theory to Practice

 Finding best Matches

image source: parship.de, elitepartner.de, theverge.com

I e.g., online dating

image source: quora.com

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-1
 Minimum Cost (Bipartite) Matching Problem

I persons

image source: www.freepik.com

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-2
 Minimum Cost (Bipartite) Matching Problem

I persons, machines

image source: www.freepik.com

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-2
 Minimum Cost (Bipartite) Matching Problem

I persons, machines

I every machine must be operated

image source: www.freepik.com

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-2
 Minimum Cost (Bipartite) Matching Problem

I persons, machines

I every machine must be operated

I a person can operate one machine

image source: www.freepik.com

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-2
 Minimum Cost (Bipartite) Matching Problem

I persons, machines
I persons have different skills

I every machine must be operated

I a person can operate one machine

image source: www.freepik.com

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-2
 Minimum Cost (Bipartite) Matching Problem

I persons, machines
I persons have different skills

I every machine must be operated

I a person can operate one machine

I task: assign workers to machines

I goal: minimize total assignment cost

image source: www.freepik.com

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-2
 Minimum Cost (Bipartite) Matching Problem
n persons, m machines find a cost minimum assignment such that each machine is
cij assignment cost i → j operated, and no person operates more than one machine

1 I (complete) bipartite edge weighted graph

1 I G = (U ∪ V, E, c), |U | = n, |V | = m
2
2
3

m
n
U V

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-3
 Minimum Cost (Bipartite) Matching Problem
n persons, m machines find a cost minimum assignment such that each machine is
cij assignment cost i → j operated, and no person operates more than one machine

1 I (complete) bipartite edge weighted graph

1 I G = (U ∪ V, E, c), |U | = n, |V | = m
2
2 one-sided perfect matching
3 I set M ⊆ E of min{n, m} edges, such that no two
e1 , e2 ∈ M are incident // don’t share a common vertex
X
I cost of M : c(M ) = c(e)
m e∈M
n
U V I finding a minimum cost matching is easy
// i.e., polynomial time solvable
2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-3
 Minimum Cost (Bipartite) Matching Problem

n persons, m machines find a cost minimum assignment such that each machine is
cij assignment cost i → j operated, and no person operates more than one machine

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-4
 Minimum Cost (Bipartite) Matching Problem

n persons, m machines find a cost minimum assignment such that each machine is
cij assignment cost i → j operated, and no person operates more than one machine

xij ∈ {0, 1} i = 1, . . . , n, j = 1, . . . , m // assign i → j

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-4
 Minimum Cost (Bipartite) Matching Problem

n persons, m machines find a cost minimum assignment such that each machine is
cij assignment cost i → j operated, and no person operates more than one machine
n X
X m
min cij xij // minimize cost of edges in matching
i=1 j=1

xij ∈ {0, 1} i = 1, . . . , n, j = 1, . . . , m // assign i → j

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-4
 Minimum Cost (Bipartite) Matching Problem

n persons, m machines find a cost minimum assignment such that each machine is
cij assignment cost i → j operated, and no person operates more than one machine
n X
X m
min cij xij // minimize cost of edges in matching
i=1 j=1
n
X
s. t. xij = 1 j = 1, . . . , m // every machine must be operated
i=1

xij ∈ {0, 1} i = 1, . . . , n, j = 1, . . . , m // assign i → j

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-4
 Minimum Cost (Bipartite) Matching Problem

n persons, m machines find a cost minimum assignment such that each machine is
cij assignment cost i → j operated, and no person operates more than one machine
n X
X m
min cij xij // minimize cost of edges in matching
i=1 j=1
n
X
s. t. xij = 1 j = 1, . . . , m // every machine must be operated
i=1
Xm
xij ≤ 1 i = 1, . . . , n // noone can operate more than one machine
j=1

xij ∈ {0, 1} i = 1, . . . , n, j = 1, . . . , m // assign i → j

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-4
 Minimum Cost (Bipartite) Matching Problem

I let us understand the notation pictorially (only once, I promise)

1
1
2 n
X
2 I xij = 1, j = 1, . . . , m
i=1
3

m
n

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-5
 Minimum Cost (Bipartite) Matching Problem

I let us understand the notation pictorially (only once, I promise)

1
1
2 n
X
2 j=2 I xi2 = 1, j = 2
i=1
3

m
n

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-5
 Minimum Cost (Bipartite) Matching Problem

I let us understand the notation pictorially (only once, I promise)

1
1
2 n
X
2 j=2 I xi2 = 1, j = 2
i=1
3

m
n

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-5
 Minimum Cost (Bipartite) Matching Problem

I let us understand the notation pictorially (only once, I promise)

1
1
2 n
X
2 I xij = 1, j = 1, . . . , m
i=1
3 m
X
I xij ≤ 1, i = 1, . . . , n
j=1
m
n

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-5
 Minimum Cost (Bipartite) Matching Problem

I let us understand the notation pictorially (only once, I promise)

1
1
2 n
X
2 I xij = 1, j = 1, . . . , m
i=1
i=3 3 m
X
I x3j ≤ 1, i = 3
j=1
m
n

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-5
 Minimum Cost (Bipartite) Matching Problem

I let us understand the notation pictorially (only once, I promise)

1
1
2 n
X
2 I xij = 1, j = 1, . . . , m
i=1
i=3 3 m
X
I x3j ≤ 1, i = 3
j=1
m
n

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-5
 Variables Encode Solutions

I example n = 4, m = 3
I 4 · 3 variables: x1,1 , x1,2 , x1,3 , x1,4 , x2,1 , x2,2 , . . . , x4,2 , x4,3
I theoretically, this yields 212 different 0-1 combinations

0 0 0 0 0 ··· 0 0 0 0 0 0 1 1 ··· 0 1 1 0 1 0 0 1 ··· 0 1 0

0 0 0 0 0 ··· 0 0 1 0 0 0 1 1 ··· 1 0 0 0 1 0 0 1 ··· 0 1 1
0 0 0 0 0 ··· 0 1 0 0 0 0 1 1 ··· 1 0 1 0 1 0 0 1 ··· 1 0 0
0 0 0 0 0 ··· 0 1 1 0 0 0 1 1 ··· 1 1 0 0 1 0 0 1 ··· 1 0 1
. .. ..
.. . .
0 0 0 0 1 ··· 1 1 0 0 0 1 0 1 ··· 0 1 1 1 1 1 1 1 ··· 1 1 0
0 0 0 0 1 ··· 1 1 1 0 0 1 0 1 ··· 1 0 0 1 1 1 1 1 ··· 1 1 1
.. ..
. .

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-6
 Variables Encode Solutions

I example n = 4, m = 3
I 4 · 3 variables: x1,1 , x1,2 , x1,3 , x1,4 , x2,1 , x2,2 , . . . , x4,2 , x4,3
I theoretically, this yields 212 different 0-1 combinations
I only a subset is feasible (defined by the constraints)

0 1 0 0 1 ··· 0 1 0
0 0 0 1 1 ··· 1 0 0
0 1 0 0 1 ··· 1 0 0

. .. ..
.. . .

0 0 1 0 1 ··· 1 0 0
.. ..
. .

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-6
 Variables Encode Solutions

I example n = 4, m = 3
I 4 · 3 variables: x1,1 , x1,2 , x1,3 , x1,4 , x2,1 , x2,2 , . . . , x4,2 , x4,3
I theoretically, this yields 212 different 0-1 combinations
I only a subset is feasible (defined by the constraints)
I an algorithm later computes an optimal solution

0 1 0 0 1 ··· 0 1 0
0 0 0 1 1 ··· 1 0 0
0 1 0 0 1 ··· 1 0 0

.. .. ..
. . .

0 0 1 0 1 ··· 1 0 0
.. ..
. .

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-6
 A Note on Notation

I the graph needs not be complete // not all edges need to be present
Xn Xm
I however, the notation cij xij implicitly assumes this; better use ij ∈ E:
i=1 j=1

X
min cij xij // minimize cost of edges in matching
ij∈E
X
s. t. xij = 1 j = 1, . . . , m // operate every machine
ij∈E
X
xij ≤ 1 i = 1, . . . , n // no more than one machine
ij∈E
xij ∈ {0, 1} ij ∈ E // assign i → j

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-7
 Assignment Problem in Python/Gurobi

# model, n workers, m machines

model = Model("assignment problem")

# variables
x = {}
for i in range(n):
for j in range(m):
x[i,j] = model.addVar(obj=c[i][j], vtype=GRB.BINARY)

# each machine must be operated

for j in range(m):
model.addConstr(quicksum(x[i,j] for i in range(n)) == 1)

# each worker operates at most one machine

for i in range(n):
model.addConstr(quicksum(x[i,j] for j in range(m)) <= 1)

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-8
 . Modeling Basics: Alternatives

I the rationale behind the constraint

n
X
xi = 1 with xi ∈ {0, 1}, i = 1, . . . , n
i=1

is to choose exactly one alternative (out of n)

I analogously:
choose at most one alternative “≤ 1”
choose at least one alternative “≥ 1”

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-9
 Example: Course Timetabling: More Alternatives

I binary variables: xc,r,t ∈ {0, 1} // should course c take place in room r at time t?
I e.g., xOR1,Mo 8.30,TEMP2 ∈ {0, 1}
I constraint: choose exactly two weekly time slots for lecture OR1
I denote by ROR1 the set of rooms and by TOR1 the time slots eligible for OR1
X X
xOR1,r,t = 2
r∈ROR1 t∈TOR1

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-10
 Example: Course Timetabling: Modeling of Conflicts

I “conflict” of alternatives: cannot be chosen simultaneously

I e.g., room conflicts // at most one course per time slot in a room
X
xc,t,r ≤ 1 ∀ times t, ∀ rooms r
c:c can take place
in room r at time t

I e.g., curricula conflicts // no two compulsory courses simultaneously

X X
xc,t,r ≤ 1 ∀ times t
c: courses c in r: rooms r in which
a curriculum c can take place

I etc.; the main difficulty is probably to find a good notation

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-11
 Example: Vertex Coloring

Data
G = (V, E) undirected graph
Goal
color all vertices (=choose exactly one color per vertex from a set C) such that
adjacent vertices receive different colors, minimizing the number of used colors

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-12
 Example: Vertex Coloring

Data
G = (V, E) undirected graph
Goal
color all vertices (=choose exactly one color per vertex from a set C) such that
adjacent vertices receive different colors, minimizing the number of used colors

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-12
 Vertex Coloring: An Integer Program

xic ∈ {0, 1} i ∈ V, c ∈ C // color vertex i with color c?

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-13
 Vertex Coloring: An Integer Program

X
s.t. xic = 1 i∈V // color each vertex
c∈C

xic ∈ {0, 1} i ∈ V, c ∈ C // color vertex i with color c?

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-13
 Vertex Coloring: An Integer Program

X
s.t. xic = 1 i∈V // color each vertex
c∈C
xic + xjc ≤ 1 ij ∈ E, c ∈ C // avoid conflicts

xic ∈ {0, 1} i ∈ V, c ∈ C // color vertex i with color c?

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-13
 Vertex Coloring: An Integer Program

X
s.t. xic = 1 i∈V // color each vertex
c∈C
xic + xjc ≤ 1 ij ∈ E, c ∈ C // avoid conflicts

xic ∈ {0, 1} i ∈ V, c ∈ C // color vertex i with color c?

yc ∈ {0, 1} c ∈ C // do we use color c?

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-13
 Vertex Coloring: An Integer Program

X
χ(G) = min yc // minimize number of used colors
c∈C
X
s.t. xic = 1 i∈V // color each vertex
c∈C
xic + xjc ≤ 1 ij ∈ E, c ∈ C // avoid conflicts

xic ∈ {0, 1} i ∈ V, c ∈ C // color vertex i with color c?

yc ∈ {0, 1} c ∈ C // do we use color c?

I χ(G) is called the chromatic number of G.

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-13
 Vertex Coloring: An Integer Program

X
χ(G) = min yc // minimize number of used colors
c∈C
X
s.t. xic = 1 i∈V // color each vertex
c∈C
xic + xjc ≤ 1 ij ∈ E, c ∈ C // avoid conflicts
xic ≤ yc i ∈ V, c ∈ C // if xic = 1 then yc = 1
xic ∈ {0, 1} i ∈ V, c ∈ C // color vertex i with color c?
yc ∈ {0, 1} c ∈ C // do we use color c?

I χ(G) is called the chromatic number of G.

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.1 Assignment Problem · p. 2.1-13
 Transportation Problem (Hitchcock, 1941)

Transportation Problem
given G = (U ∪ V, E)
with E ⊆ U × V (bipartite)

image source: G.B. Dantzig, Linear Programming and Extensions, 1963

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-14
 Transportation Problem (Hitchcock, 1941)

Transportation Problem
given G = (U ∪ V, E)
with E ⊆ U × V (bipartite)
I supplies ai ∈ Z+ , i ∈ U

image source: G.B. Dantzig, Linear Programming and Extensions, 1963

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-14
 Transportation Problem (Hitchcock, 1941)

Transportation Problem
given G = (U ∪ V, E)
with E ⊆ U × V (bipartite)
I supplies ai ∈ Z+ , i ∈ U
I demands bj ∈ Z+ , j ∈ V

image source: G.B. Dantzig, Linear Programming and Extensions, 1963

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-14
 Transportation Problem (Hitchcock, 1941)

Transportation Problem
given G = (U ∪ V, E)
with E ⊆ U × V (bipartite)
I supplies ai ∈ Z+ , i ∈ U
I demands bj ∈ Z+ , j ∈ V
I cost c(e) ∈ Z+ , e ∈ E
// per unit transportation cost

find: cost minimal transport, that ships

every supply and satisfies all demands
image source: G.B. Dantzig, Linear Programming and Extensions, 1963

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-14
 Transportation Problem

n supplies ai , m demands bj find a cost minimum transport that fulfills

cij cost per unit i → j demands and supplies suffice

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-15
 Transportation Problem

n supplies ai , m demands bj find a cost minimum transport that fulfills

cij cost per unit i → j demands and supplies suffice

xij ∈ Z+ i = 1, . . . , n, j = 1, . . . , m // how many units to ship i → j

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-15
 Transportation Problem

n supplies ai , m demands bj find a cost minimum transport that fulfills

cij cost per unit i → j demands and supplies suffice

X
min cij xij // minimize total transportation cost
ij∈E

xij ∈ Z+ i = 1, . . . , n, j = 1, . . . , m // how many units to ship i → j

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-15
 Transportation Problem

n supplies ai , m demands bj find a cost minimum transport that fulfills

cij cost per unit i → j demands and supplies suffice

X
min cij xij // minimize total transportation cost
ij∈E

X
xij ≥ bj j = 1, . . . , m // satisfy demands
ij∈E

xij ∈ Z+ i = 1, . . . , n, j = 1, . . . , m // how many units to ship i → j

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-15
 Transportation Problem

n supplies ai , m demands bj find a cost minimum transport that fulfills

cij cost per unit i → j demands and supplies suffice

X
min cij xij // minimize total transportation cost
ij∈E
X
s. t. xij ≤ ai i = 1, . . . , n // do not exceed supplies
ij∈E
X
xij ≥ bj j = 1, . . . , m // satisfy demands
ij∈E

xij ∈ Z+ i = 1, . . . , n, j = 1, . . . , m // how many units to ship i → j

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-15
 Example/Variant: Courses with limited Enrollment

image source: www.wiwi.rwth-aachen.de/

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-16
 Example/Variant: Courses with limited Enrollment

n students wish to take ai courses, i = 1, . . . , n; m courses with a limited number of

participants bj , j = 1, . . . , m; student i has preference cij ∈ {1, 2, 3} for course j

1
1
X
2 min cij xij // minimize total preference
2 ij∈E
X
3 s. t. xij = ai i = 1, . . . , n // student wishes
m ij∈E
X
xij ≤ bj j = 1, . . . , m // course limits
ij∈E
n xij ∈ {0, 1} ij ∈ E // student i takes course j
students courses

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-17
 Example/Variant: Courses with limited Enrollment

n students wish to take ai courses, i = 1, . . . , n; m courses with a limited number of

participants bj , j = 1, . . . , m; student i has preference cij ∈ {1, 2, 3} for course j

1 M represents “large” penalty cost for not assigning one course

1 n
X X
2 min cij xij + M xid // minimize total preference
2 ij∈E i=1
X
3 s. t. xij +xid = ai i = 1, . . . , n // student wishes
m ij∈E
X
xij ≤ bj j = 1, . . . , m // course limits
d ij∈E
n xij ∈ {0, 1} ij ∈ E // student i takes course j
students courses

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-17
 Example/Variant: Courses with limited Enrollment

n students wish to take ai courses, i = 1, . . . , n; m courses with a limited number of

participants bj , j = 1, . . . , m; student i has preference cij ∈ {1, 2, 3} for course j

1 M represents “large” penalty cost for not assigning one course

1 n
X X
2 min cij xij + M xid // minimize total preference
2 ij∈E i=1
X
3 s. t. xij +xid = ai i = 1, . . . , n // student wishes
m ij∈E
X
xij ≤ bj · 1.1 j = 1, . . . , m // course limits
d ij∈E
n xij ∈ {0, 1} ij ∈ E // student i takes course j
students courses
variant: overbooking factor of 10%
2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.2 Transportation Problem · p. 2.1-17
 More Generally: Minimum Cost Network Flows

directed graph G = (V, A); cost c : A → Z+

capacities u : A → Z+ ; demands b : V → Z

−2 0 1
r (3, 1/2) t (2, 1/1) z

(10, 0/5)
(6, 3/5)

(5, 2/4)
(6

)
/2
,0

,0
/3

legend for a = (i, j):

(4
)

i (c(a), f (a)/u(a)) j
(2, 2/2) b(i) b(j)
s (4, 0/1) v w
(1, 0/3)
3 0 −2

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.3 Minimum Cost Flows · p. 2.1-18
 More Generally: Minimum Cost Network Flows

directed graph G = (V, A); cost c : A → Z+ i

capacities u : A → Z+ ; demands b : V → Z

X
min cij xij
ij∈A
X X
s. t. xij − xji = bi , i∈V // flow conservation
ij∈δ + (i) ji∈δ − (i)
xij ≤ uij , ij ∈ A // capacities
xij ∈ Z+ , ij ∈ A

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.3 Minimum Cost Flows · p. 2.1-19
 More Generally: Minimum Cost Network Flows

δ+ (i)
directed graph G = (V, A); cost c : A → Z+ i
capacities u : A → Z+ ; demands b : V → Z

X
min cij xij
ij∈A
X X
s. t. xij − xji = bi , i∈V // flow conservation
ij∈δ + (i) ji∈δ − (i)
xij ≤ uij , ij ∈ A // capacities
xij ∈ Z+ , ij ∈ A

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.3 Minimum Cost Flows · p. 2.1-19
 More Generally: Minimum Cost Network Flows

δ+ (i)
directed graph G = (V, A); cost c : A → Z+ i
capacities u : A → Z+ ; demands b : V → Z δ− (i)

X
min cij xij
ij∈A
X X
s. t. xij − xji = bi , i∈V // flow conservation
ij∈δ + (i) ji∈δ − (i)
xij ≤ uij , ij ∈ A // capacities
xij ∈ Z+ , ij ∈ A

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.3 Minimum Cost Flows · p. 2.1-19
 Special Case of a Min Cost Flow: Shortest s-t-Paths

directed graph G = (V, A), source s, sink t

cost c : A → Z+ ; capacities u ≡ 1
X
min cij xij
ij∈A

X X  1 i=s
s. t. xij − xji = −1 i = t
0 i ∈ V \ {s, t}

ij∈δ + (i) ji∈δ − (i)
image source: maps.google.com
xij ∈ {0, 1}, ij ∈ A

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.3 Minimum Cost Flows · p. 2.1-20
 Variants of Shortest Paths

I resource constraint: resource consumption t : A → Z+ ; limit T

X
tij xij ≤ T
ij∈A

I forbidden pairs: not both arcs in (ak1 , ak2 ) can be visited, k = 1, . . . , K

xak + xak ≤ 1 k = 1, . . . , K
1 2

I both variants are NP-hard

2 Modeling with Integer Variables · 2.1 Integer Linear Programs · 2.1.3 Minimum Cost Flows · p. 2.1-21
What we have Seen

I we re-visited graph optimization problems, formulated them as integer programs

I we refreshed some graph notation en passant
I we used binary variables and assignment constraints to model the selection from
alternatives: at most/exactly/at least one (or more)
I as an example we learned about the vertex coloring problem