Appunti di Foundations of Operations Research

A A A

i j j

after the end of .

A

i Example

A project can be represented by a DAG where:

G = (N,A)

- each arc corresponds to an activity,

- arc length represents the duration of the activity.

To account for the precedence constraints, the arcs must be positioned so that:

12

there exists a directed path where the arc

associated to precedes the arc

A

i

associated to A

j

Each node v corresponds to the event "end of all the activities and, hence, to the possible

(i,v) ∈ δ (v)"

-

beginning of all the (v,j) ∈ δ (v).

+ Example

After creating the graph with all precedence respected, we can contract some arcs to simplify the

graph. Pay attention to not introduce unwanted precedence constraints!

Finally, we introduce “artificial nodes” so that the graph G:

- contains a unique initial node s corresponding to the event “beginning of the project”

- contains a unique final node t corresponding to the event “end of the project”

- does not contain multiple arcs (with same endpoints)

Example

Critical Path Method (CPM)

The algorithm determines a schedule that minimizes the overall project duration and the slack of

each activity, i.e., the amount of time by which its execution can be delayed, without affecting the

overall minimum project duration.

Method:

1. Initialization: Construct the graph G representing the project and find a topological order of the

nodes. 13

2. Consider the nodes by increasing indices and, for each find: the earliest time Tmin at

h ∈ N, h

which the event associated to node h can occur (Tmin corresponds to the minimum project

t

duration).

3. Consider the nodes by decreasing indices and, for each find: the latest time Tmax at

h ∈ N, h

which the event associated to node h can occur without delaying the project completion date

beyond Tmin .

t

4. For each activity find the slack:

(i,j) ∈ A, σ = Tmax - Tmin - d

ij j i ij

Example

14

10 Network flows

Problems involving the distribution of a given “product” (e.g., water, gas, data) from a set of “sources”

to a set of “users” to optimize a given objective function (e.g., amount of product, total cost).

Many direct and indirect applications: telecommunication, transportation (public, freight, railway, air),

logistics etc…

Maximum flow problem: Given a network G = (N,A) with an integer capacity k for each arc (i,j) A,

∈

ij

and nodes s, t N, determine a feasible flow x R from s to t of maximum value.

m

∈ ∈

Note:

If there are many sources/sinks with a unique type of product, dummy nodes s* and t* can be added.

DEFINITIONS

- A network is a directed and connected graph with a source and a sink

G = (N,A) s ∈ N t ∈ N,

with and a capacity for each arc

s ≠ t, k ≥ 0, (i, j) ∈ A.

ij

- A feasible flow x from s to t is a vector with a component for each arc

x ∈ R x (i,j) ∈ A

m ij

satisfying the capacity constraints

0 ≤ ≤ ∀(, ) ∈

ⅈ ⅈ

and the flow balance constraints at each intermediate node u ∈ N (u ≠ s, t)

∑ = ∑ , ∀ ∈ {, }

ⅈ

− +

(ⅈ,)∈ () (,)∈ ()

- The value of flow x is ∑

=

+

(,)∈ ()

- Given a network and a feasible flow an arc is saturated (empty) if

x, (i,j) ∈ A x = k (x = 0)

ij ij ij

Example

X is empty, x is saturated

1t 2t

15

- A cut separating s from t is of with and

δ(S) G s ∈ S ⊂ N t ∈ N\S

- Capacity of the cut induced by ∑

δ(S) S: () =

+

(ⅈ,)∈ () ⅈ

Example

- Given a feasible flow x from s to t and a cut separating s from t, the value of the feasible

δ(S)

flow x through the cut is

δ(S) () = ∑ − ∑

ⅈ ⅈ

−

+ (ⅈ,)∈ ()

(ⅈ,)∈ ()

PROPERTIES

- Let x be any feasible flow from s to t. For every cut separating s from t, we have

δ(S)

() = ({})

Implied by the flow balance equations ∀v ∈ N\{s,t}

- For every feasible flow from s to t and every cut with separating from t, we have

x δ(S), S ⊆ N, s

() ≤ () ( ℎ ≤ ℎ )

As a consequence, if for a subset with and then is a flow of maximum

(S) = k(S) S ⊆ N s ∈ S t ∉ S, x

value and the cut is of minimum capacity.

δ(S)

The first property expresses a weak duality relationship (the optimal value of the dual problem is

always less than or equal to the optimal value of the primal problem for minimization problems)

between the two problems:

1. Primal problem

Given with integer capacities on the arcs and determine a feasible flow of

G = (N,A) s, t ∈ N,

maximum value

2. Dual problem

Given with integer arc capacities and determine a cut (separating s from t) of

G = (N,A) s, t ∈ N,

minimum capacity.

(The following algorithm implies that the value of a feasible flow of maximum value = the capacity of a

cut of minimum capacity.)

Ford-Fulkerson’s algorithm

Idea: Start from a feasible flow x and try to iteratively increase its value by sending, at each iteration,

an additional amount of product along a (n undirected) path from s to t with a strictly positive residual

capacity. 16

DEFINITIONS:

- A path from to is an augmenting path w.r.t. the current feasible flow if for every

P s t x x < k

ij ij

forward arc and for every backward arc.

x > 0

ij

- Given a feasible flow for we construct the residual network

x G = (N,A), G = (N, A )

associated to accounting for all possible flow variations w.r.t.

x, x:

If is not empty, A with k =

o (i,j) ∈ A (j,i) ∈ x > 0.

ji ij

If is not saturated, with k = k - x > 0.

o (i,j) ∈ A (i,j) ∈ A ji ij ij

k is called the residual capacity.

ji

Method:

For each iteration find an augmenting path and construct the corresponding residual network. The

algorithm terminates when there is no more augmenting path in the network. The flow that we have

computed is the one with maximum capacity.

11 Hard graph optimization problems

DEFINITIONS:

- An instance of a problem is a special case of

I P P.

- The size of an instance denoted by is the number of bits needed to encode

I, |I|, I.

- An algorithm is polynomial if it requires, in the worst case, a polynomial number of elementary

operations where d is a constant and

f (n) = O(n ), n = |I|.

d

- A problem P is polynomially solvable (“easy”) if there is a polynomial time algorithm providing

an (optimal) solution for every instance.

For many (discrete) optimization problems, the best algorithm known today requires a number of

elementary operations which grows, in the worst-case, exponentially in the size of the instance.

NP-hard computational problems are at least as di-cult as a wide range of very challenging problems

for which no polynomial-time algorithm is known to date. NP-hardness of a problem is very strong

evidence that it is inherently di-cult. Does not mean that it cannot admit a polynomial-time algorithm!

If any NP-hard problem admits a polynomial-time algorithm then a huge variety of very challenging

computational problems not known to be polynomially solvable, would admit one.

Ex of NP-hard problems: TSP(Traveling Salesman Problem) and VRP(vehicle route problem), fin the

path of maximum total weight in a directed graph, ILP(Integer Linear Programming) ext…

17

02 Linear Programming

01 Linear Programming (LP)

DEFINITIONS

1. A Linear Programming (LP) problem is an optimization problem:

min f(x)

Where: s.t. x ∈ X ⊆ R n

The Objective function f: X R is linear;

→

o The Feasible region X = {x R : g (x) r 0, i {1, …, m}, r {=, ≥,

n

o ∈ ∈ ∈

i i i

≤}} with g : R R linear, for i = 1, …, m.

n →

i

2. x* R is an optimal solution of (1) if f(x*) ≤ f(x), x X

n

∈ ∀ ∈

A variety of decision-making problems can be formulated/approximated as LPs.

ASSUMPTIONS

1. Linearity of the objective function and constraints:

- Proportionality: Contribution of each variable = constant x variable

- Additivity: Contribution of all variables = sum of single contributions

2. Divisibility: The variables can take fractional (rational) values

3. Parameters are considered as constants which can be estimated with a sufficient degree of

accuracy

02 Equivalent Forms

General form: Matrix notation:

Standard form:

Only equality constraints and all nonnegative variables:

The two forms are equivalent. Simple transformation rules allow to pass from one form to the other

form. This transformation may involve adding/deleting variables and/or constraints:

1.

2.

3.

4. 18

03 Graphical solution

DEFINITIONS

1. A level curve of value z of a function f is the set of points in R where f is constant and takes

n

value z

2. H = {x R : a x = b} is a hyperplane (It is essentially a linear subspace of dimension one (n−1)

n T

∈

smaller than the space in which (n) is contained. In R is a plane)

3

3. H = {x R : a x ≤ b} is an affine half-space (half-plane in R )

- n T 2

∈

4. The feasible region X of any LP is a polyhedron P (Intersection of a finite number of half-

spaces)

5. A subset S R is convex if for each pair y , y S, S contains the whole segment connecting y

n 1 2 1

⊆ ∈

and y 2

6. The segment defined by y ,y S, defined by all the convex combinations of y and y , is

1 2 1 2

∈

[y ,y ] = {x R : x = αy + (1-α)y α [0,1]}

1 2 n 1 2 ˄

∈ ∈

7. A vertex of P is a point of P which cannot be expressed as a convex combination of two other

distinct points of P. Algebraically, x is a vertex of P if and only if:

x = αy + (1-α)y , α [0,1], y ,y P x = y v x = y

1 2 1 2 1 2

➔

∈ ∈

8. Given a polyhedron P, a vector d R with d ≠ 0 is an unbounded feasible direction of P if, for

n

∈

every point x P, the “ray” {x R : x = x + λd, λ ≥ 0} is contained in P.

n

∈ ∈

0 0

9. A polytope is a bounded polyhedron, that is, it has the only unbounded feasible direction d=0

19

PROPERTIES

1. A polyhedron P is a convex set of R . Indeed, any half-space is conv