Annegret K Wagler
email: annegret.wagler@univ-bpclermont.fr

Combinatorial optimization: The interplay of graph theory, linear and integer programming illustrated on network flow

Combinatorial Optimization is one of the fields in mathematics with an impressive development in recent years, driven by demands from applications where discrete models play a role. Here, we intend to give a comprehensive overview of basic methods and paradigms, in particular the beautiful interplay of methods from graph theory, geometry, linear and integer programming related to combinatorial optimization problems. To understand the underlying framework and the interrelationships more clearly, we illustrate the theoretical results and methods with the help of flows in networks as running example. This includes on the one hand a combinatorial algorithm for finding a maximum flow in a network, combinatorial duality and the Max Flow/Min Cut-Theorem as one of the fundamental combinatorial minmax relations. On the other hand, we discuss solving the network flow problem as linear program with the help of the Simplex Method, linear programming duality and the dual program for network flow. Finally, we address the problem of integer network flows, ideal formulations for integer linear programs and consequences for the network flow problem.

In practical settings, finding the best of something typically includes some side constraints. In mathematical terms, this can be expressed with the help of some function(s) f : R n → R. The functions involve certain variables x ∈ R n . This leads to the following classical optimization problem: max or min c(x) subject to f 1 (x) ≤ b 1 . . . . . . . . .

f k (x) ≤ b k x ∈ R n
The points x ∈ R n satisfying all side constraints f (x) ≤ b are called feasible. The set of all feasible points is called the feasible region of the optimization problem. If all side constraints are linear functions, the above optimization problem is a linear program and the feasible region is a convex set, which allows to solve the problem in polynomial time.

If the studied objects are entities as workers, planes,... which cannot be divided, it is necessary to use integral variables x ∈ Z n or decision variables x ∈ {0, 1} n which makes the corresponding integer linear programs computationally more demanding. This is typically the case for combinatorial optimization problems, where the goal is to search for an optimum object in a finite collection of certain objects. Hereby, the objects have a concise representation within a discrete structure (like a graph or a network), but their number is huge such that scanning all objects to select the best one among them is not an option. The aim of Combinatorial Optimization is to find more efficient solution methods.

The first step towards solving a problem is always to build a mathematical model: it helps to correctly formalize the problem, that is, to decide which conditions are crucial to describe the problem, and how to formalize them appropriately. This can reveal relationships by gaining structural insight of the problem, for instance in terms of bounds for the objective function value arising from dual combinatorial objects. The second step is to develop methods for finding a feasible solution, and to certify optimality (without knowing the optimal solution before). In addition, it is important to study the complexity of the problem, that is, to answer the question how hard or easy the studied problem is.

In this chapter, we shall discuss how to model and solve combinatorial optimization problems, illustrated with the help of the well-studied network flow problem as running example.

Problem 1 (Network Flow Problem). Find a maximal flow, that is, transport the maximal amount of certain goods (or water, electricity, cars, ...), through a given transportation network (consisting of pipelines, streets, etc.).

In Section 2, we first address the Network Flow Problem from a combinatorial point of view. This includes to model the problem with the help of an appropriate discrete structure (a network) and the studied combinatorial objects therein (a flow).

We discuss combinatorial duality and the Max Flow/Min Cut-Theorem as one of the fundamental combinatorial min-max relations. Moreover, we present Ford-Fulkersons's combinatorial algorithm for finding a maximum flow in a network.

In Section 3, we introduce linear programs and show how to formulate the Network Flow Problem in this context. Next, we discuss the geometry of the feasible region of linear programs and its impact on solving linear programs with the help of the Simplex Method. Furthermore, we address linear programming duality and consider the dual program for network flow.

Finally, in Section 4, we introduce integer linear programs, linear programming relaxations for integer linear programs and ways to strengthen them. We conclude with the problem of integer network flows, discuss ideal formulations for integer linear programs related to totally unimodular matrices, and consequences for the network flow problem.

A combinatorial algorithm for network flow

The combinatorial formulation of the Network Flow Problem involves both an appropriate discrete structure to model the input of that problem and a combinatorial object therein to describe the desired output:

• Model: construct a directed graph with transportation ways (pipes, streets, ...) as directed arcs, their crossing points (connections, swivel valves, ...) as nodes, and arc weights as capacities; • Task: find a maximal flow through the network (respecting the arc capacities).

We first introduce the underlying discrete structures. For that, consider a digraph D = (V, A) with node set V and arc set A where each arc a = (u, v) ∈ V × V is an ordered pair. We say that a = (u, v) is the arc outgoing from u and ingoing to v and denote by δ -(v) = {a ∈ A : a = (u, v)} the set of arcs ingoing to v and by δ + (v) = {a ∈ A : a = (v, u)} the set of arcs outgoing from v. A directed path is a subgraph of D with (distinct) nodes v 1 , . . . , v k ∈ V and (exactly) the arcs (v i , v i+1 ) ∈ A for 1 ≤ i < k, and is called (v 1 , v k )-path if it links v 1 with v k . Figure 1 shows a digraph with a directed path.

x z s w t y Fig. 1 A digraph with a directed path (induced by the black nodes and the dashed arcs).

A digraph together with a source/sink pair and arc capacities becomes a network (see Figure 2). More formally: Definition 1. We call N = (D; s,t; c) a network if D = (V, A) is a digraph with two specified nodes, a source s ∈ V with δ -(s) = / 0 and a sink t ∈ V with δ + (t) = / 0, and arc capacities c a for all a ∈ A. • capacity constraints 0 ≤ f (a) ≤ c a for all arcs a ∈ A, and

• flow conservation constraints (δ f )(v) = ∑ a∈δ -(v) f (a) -∑ a∈δ + (v) f (a) = 0 for all nodes v ∈ V \ {s,t}.
We denote by

val( f ) := ∑ a∈δ -(t) f (a) = ∑ a∈δ + (s) f (a)
the value of the (s,t)-flow f . For illustration, Figure 3 shows a network with an (s,t)-flow f and its value val( f ). The existence of an (s,t)-flow in a given network N = (D; s,t; c) is ensured as soon as there exists an (s,t)-path in the underlying digraph D (which can be easily checked with the help of Breadth First Search techniques starting in s). We will next address the question whether and how we can find an upper bound for its possible value (without knowing the optimum before). For that, we look for the combinatorial structure in a digraph being dual to flows.

Definition 3. Let N = (D; s,t; c) be a network with digraph D = (V, A). An (s,t)-cut (V s ,V t ) is a partition V = V s ∪V t of V into subsets V s and V t = V \V s with s ∈ V s and t ∈ V t . The capacity of an (s,t)-cut (V s ,V t ) is c(V s ,V t ) = ∑ u∈V s ,v∈V t c (u,v) ,
see Figure 4 for illustration. 4 A network with an (s,t)-cut V s = {s, x, y}, V t = {t, w, z} and capacity c(V s ,V t ) = 24 (as sum of the capacities of all forward arcs crossing the dashed line).

Let N = (D; s,t; c) be a network with digraph D = (V, A) and consider an (s,t)flow f as well as an

(s,t)-cut (V s ,V t ) in N. The flow across the (s,t)-cut (V s ,V t ) is f (V s ,V t ) = ∑ u∈V s ,v∈V t f ((u, v)) -∑ u∈V s ,v∈V t f ((v, u)).
Obviously, val( f ) ≤ c(V s ,V t ) holds for any (s,t)-cut in a network. We even have: Theorem 1 (Max-Flow Min-Cut Theorem (Ford & Fulkerson [START_REF] Ford | Maximum flow through a network[END_REF])). For any network N = (D; s,t; c) with digraph D = (V, A) and s = t ∈ V , we have

max{val( f ) : f (s,t)-flow in N} = min{c(V s ,V t ) : (V s ,V t ) (s,t)-cut in N}.
The Max-Flow Min-Cut Theorem is one of the fundamental theorems in Combinatorial Optimization. It ensures that the minimum capacity of all (s,t)-cuts in a network always equals the maximum value of an (s,t)-flow. The next question is how to construct such a maximum flow in a network. To state the corresponding combinatorial algorithm, we first have to introduce the following notions. Definition 4. Let N = (D; s,t; c) be a network with digraph D = (V, A), f an (s,t)flow, and

P = {s = v 0 , v 1 , . . . , v k = t} an (undirected) (s,t)-path.
• The residual capacity of an arc a of P is

∆ f (a) = c a -f (a) if a = (v i , v i+1 ) is a forward arc, ∆ f (a) = f (a) if a = (v i+1 , v i ) is a backward arc.
• The residual capacity of the path P is

∆ f (P) = min{∆ f (a) : a arc of P} and P is called f -augmenting path if ∆ f (P) > 0.
Finding f -augmenting paths can be done with Breadth First Search techniques starting in s, where a node u is considered as "neighbor" of the active node v if there is an arc a with ∆ f (a) > 0 linking v and u (or u and v), see Figure 5. With the help of an f -augmenting path, we can increase the value of f as follows:

Lemma 1. Let P be an f -augmenting (s,t)-path in a network N with (s,t)-flow f . There exists an (s,t)-flow f ′ in N with val( f ′ ) = val( f ) + ∆ f (P). We obtain f ′ by modifying f on the arcs of P as follows:

f ′ (a) = f (a) + ∆ f (a)
for any forward arc a of P, f ′ (a) = f (a) -∆ f (a) for any backward arc a of P.

For illustration, Figure 6 shows f and the resulting flow f ′ after augmentation using the f -augmenting path from Figure 5. This augmentation can be repeated until no further augmenting path for the current flow can be found. An optimally criterion from [START_REF] Ford | Maximum flow through a network[END_REF] guarantees that this leads indeed to the studied maximum flow: Theorem 2 (Ford & Fulkerson [START_REF] Ford | Maximum flow through a network[END_REF]). An (s,t)-flow f in a network N = (D; s,t; c) has maximal value if and only if there is no f -augmenting (s,t)-path in N.

f(P) = 1 ∆ val(f) = 7 val(f') = 8
Therefore, we arrived at the following combinatorial algorithm for computing maximum flows due to Ford & Fulkerson [START_REF] Ford | Maximum flow through a network[END_REF]:

Max-Flow Algorithm (Ford & Fulkerson [16]) Input: Digraph D = (V, A) with arc weights c ∈ Z |A| + , source s ∈ V , sink t ∈ V .
Output: Maximum (s,t)-flow f . STEP 1: Initialize f with f (a) := 0 for all arcs a ∈ A. STEP 2: Find an f -augmenting path P.

IF such a path P exists:

Augment f by f (a) := f (a) + ∆ f (a) if a is a forward arc of P, f (a) := f (a) -∆ f (a) if a is a backward arc of P. Iterate STEP 2. ELSE STOP.

Remark.

• The Max-Flow Algorithm by Ford & Fulkerson [START_REF] Ford | Maximum flow through a network[END_REF] terminates correctly due to the characterization of maximum flows by augmenting paths (Theorem 2). Note that at this final step, the algorithm finds the shore V s of an (s,t)-cut (V s ,V t ) such that all arcs outgoing from V s are saturated as the capacity of this cut equals the value of the current flow which, therefore, cannot be improved further. Hence, the capacity of this (s,t)-cut gives a certificate for the maximality of the obtained flow. • In the worst case, the algorithm performs val( f * ) augmentation steps using each time an f -augmenting path P with ∆ f (P) = ).

An example how to perform the Max-Flow Algorithm is presented in Figure 7. More information on network flows can be found in [START_REF] Ford | Network Flow Theory[END_REF][START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]. x Fig. 7 The Max-Flow Algorithm starts with a flow f with f (a) := 0 for all a ∈ A. For each current flow f , a Breadth First Search is performed that, starting in s, adds a node u as neighbor of the active node v if there is an arc a with ∆ f (a) > 0 linking v and u (or u and v), until t is reached. This results in a unique f -augmenting path P and f is augmented along P to f ′ . The procedure is repeated until no augmenting path can be found anymore since the Breadth First Search tree consists in one shore V s of a (s,t)-cut (V s ,V t ) where all arcs outgoing from V s are saturated.

Solving network flow by linear programming techniques

"From an economic point of view, Linear Programming has been the most important mathematical development in the 20th century." Martin Grötschel

In this section we discuss the following questions about Linear Programming:

• What is a linear program and how it is possible to model a real problem (for instance network flow) as linear program? • How does the feasible region of a linear program look from a geometric point of view? • What are the consequences for solution techniques for Linear Programming?

Modeling a problem as a linear program

We first address the question what a linear program is. We illustrate this formal definition with the help of a small example: Example 1. This example shows a linear program given explicitly as well as in matrix formulation:

max x 1 + x 2 is the linear objective function c T x s.t. -x 1 + x 2 ≤ 1 x 1 ≤ 3 form the linear constraints Ax ≤ b x 2 ≤ 2 x 1 , x 2 ≥ 0
are the non-negativity constraints x ≥ 0 Figure 8 gives the graphical interpretation of the constraints and the feasible region, i.e. the set of all feasible solutions x ∈ R n + satisfying A x ≤ b.

-x + x < 1 1 2

x < 3 We next discuss the reformulation of the Network Flow Problem as linear program. Given a network N = (D; s,t; c) with D = (V, A), the problem of finding an (s,t)-flow f : A → R maximizing the value val( f ) can be encoded as follows:

1 x > 0 1 x > 0 2 x < 2 2 feasible solutions
• the required variables are x a to express the flow f (a) on each arc a ∈ A;

• the objective function is max ∑ a∈δ + (s) x a to maximize the flow leaving the source s (or, equivalently, max ∑ a∈δ -(t) x a as flow entering the sink t); • the flow conservation constraints read as ∑ a∈δ -(v) x a =∑ a∈δ + (v) x a ∀v ∈ V \ {s,t};

• the capacity constraints lead to x a ≤ c a ∀a ∈ A; • in addition, non-negativity x a ≥ 0 ∀a ∈ A is required for all variables.

max ∑ a∈δ + (s) x a s.t. ∑ a∈δ -(v) x a = ∑ a∈δ + (v) x a ∀v ∈ V \ {s,t} x a ≤ c a ∀a ∈ A x a ≥ 0 ∀a ∈ A Indeed,
= 0 x xz +x yz -x zt = 0 x sw ≤ 6 x sx ≤ 5 x sy ≤ 3 x wt ≤ 3 x wy ≤ 1 x xy ≤ 1 x xz ≤ 2 x yt ≤ 7 x yz ≤ 9 x zt ≤ 5 x sw , x sx , x sy , x wt , x wy , x xy , x xz , x yt , x yz , x zt , ≥ 0

Geometry of the feasible region

For a given linear program max c T x s.t. Ax ≤ b, x ≥ 0 the task is to find one vector x maximizing the objective function value within the feasible region described by the constraint system Ax ≤ b, x ≥ 0. In general, a linear program can have the following sets of optimal solutions: a unique optimum, infinitely many optima, or no optimal solutions at all due to infeasibility or unboundedness, see Figure 9. Fig. 9 The different situations for sets of optimal solutions of a feasible linear program: a unique optimum, infinitely many optima, or no optimal solution due to unboundedness (in all cases, the feasible region of the linear program is shaded and the arrows indicate the direction of the objective function vector).

In particular, whenever an optimal solution exist for a linear program, it is attained at the boundary of its feasible region. This is a central issue for Linear Programming (see, e.g. [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] for a proof):

Theorem 3 (Linear Programming Theorem). If a linear program has a (bounded) optimal solution, then there exists an "extremal" point on the boundary of the feasible region which is optimal.

Hence, as a first step towards finding an optimal solution, we shall describe the feasible region of a linear program more formally and study its boundary (in particular the extremal points). For that, we need to introduce the following notations.

Let x 1 , . . . , x k ∈ R n be points and λ 1 , . . . , It turns out that the feasible regions of linear programs are special convex sets: For a ∈ R n and b ∈ R, the set

λ k ∈ R + with ∑ i≤k λ i = 1. The point x = ∑ i≤k λ i x i ∈ R n is a convex combination of x 1 , . . . , x k . A set C ⊆ R n is convex if for any two points x, x ′ ∈ C, also any of their convex combinations λ x + (1 -λ )x ′ , λ ∈ (0, 1) belongs to C. For a subset D ⊆ R n , its convex hull conv(D) consists of all points in R n being a convex combination of points in D. A subset C 0 ⊆ C of a convex set C ⊆ R n is an extremal set if C 0 is convex, for all x, x ′ ∈ C and λ ∈ (0, 1) with λ x + (1 -λ )x ′ ∈ C 0 , we have x, x ′ ∈ C 0 .
• x ∈ R n : a T x = b is a hyperplane of R n , • x ∈ R n : a T x ≤ b is a closed half-space of R n .
A polyhedron P ⊆ R n is the intersection of finitely many closed half-spaces and/or hyperplanes in R n . A bounded polyhedron is called polytope.

Every polyhedron is a convex set, as hyperplanes and half-spaces are convex, and the intersection of convex sets yields a convex set again.

The dimension dim(P) of a polyhedron P ⊆ R n is the smallest dimension of an affine subspace containing P, or the largest d for which P contains points x 0 , x 1 , . . . , x d s.t. the vectors x 0x 1 , . . . , x 0x d are linearly independent.

The extremal sets of a polyhedron P are called faces, and in particular faces of dimension A bounded polyhedron, i.e. a polytope, has besides its description as intersection of finitely many closed half-spaces and/or hyperplanes a second representation [START_REF] Minkowski | Allgemeine Lehrsätze über konvexe Polyeder[END_REF][START_REF] Weyl | Elementare Theorie der konvexen Polyeder[END_REF]:

• 0 are extreme points, • 1 are edges, • dim(P) -1 are facets.

Theorem 4 (Weyl-Minkowski Theorem). A bounded polyhedron is the convex hull of its extreme points.

For A ∈ R m×n and b ∈ R m as constraint matrix and right hand side vector, let

P(A, b) = {x ∈ R n : Ax ≤ b}
denote the polyhedron defined by the corresponding half-spaces A i• ≤ b i or hyperplanes A j• = b j . We can characterize its extreme points as follows (see, e.g. [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] for a proof): Theorem 5. For a polyhedron P = P(A, b) ⊆ R n and x ⋆ ∈ P, the following assertions are equivalent:

• x ⋆ is an extreme point of P; • {x ⋆ } is a 0-dimensional face of P; • x ⋆ is not a convex combination of other points in P; • P \ {x ⋆ } is still convex; • ∃c ∈ R n \ {0} s.t. x ⋆ is unique optimum of max c T x, x ∈ P.
The drawback of the above characterization is that none of the conditions characterizing x ⋆ as an extreme point is easy to check. This changes in the special case where the studied polyhedron is given by hyperplanes only. For A ∈ R m×n and b ∈ R m , let

P = (A, b) = {x ∈ R n : Ax = b} .
Then we have the following (see, e.g. [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] for a proof):

Theorem 6. For a polyhedron P = P = (A, b) ⊆ R n and x ⋆ ∈ P, the following assertions are equivalent:

• x ⋆ is an extreme point of P; • The columns A • j of A with j ∈ supp (x ⋆ ) are linearly independent.
As extreme points of the feasible region P of a linear program are crucial and can be easily detected if P is of the special form P = (A, b), we consider linear programs given in the so-called equational form:

max c T x s.t. A x = b
x ≥ 0 Remark:

• Linear programs in equational form are also called linear programs given in standard form. • Note that any linear program can be transformed into equational form, namely, by introducing so-called slack variables y ∈ R m :

max c T x s.t. A x ≤ b ⇒ max c T x s.t. A x + y = b x ≥ 0 x, y ≥ 0
• For linear programs in equational form, we assume that the equation system Ax = b has at least one solution (i.e. that P = (A, b) = / 0 holds), and that the rows of the matrix A are linearly independent (i.e. no redundant constraints occur).

We are interested in special feasible solution of a linear program: Definition 6. A basic feasible solution of the linear program in equational form

max c T x s.t. Ax = b x ≥ 0 with A ∈ R m×n , b ∈ R m is a feasible solution x ⋆ ∈ R n
for which there exists an melement subset B ⊆ {1, . . . , n} s.t. the (square) matrix A B is non-singular (i.e., the columns of A indexed by B are linearly independent), and x ⋆ j = 0 for all j / ∈ B.

Example 3. The vector x ⋆ = (0, 2, 0, 1, 0) is a basic feasible solution of the equation system

x 1 + 5x 2 + 3x 3 + 4x 4 + 6x 5 = 14 x 2 + 3x 3 + 5x 4 + 6x 5 = 7 with B = {2, 4}.
In fact, basic feasible solutions are crucial for Linear Programming due to the following reason: Theorem 7. Consider a linear program in equational form:

max c T x s.t. Ax = b, x ≥ 0.
• If there is at least one feasible solution and the objective function is bounded from above on P = (A, b) ∩ R n + , then there always exists an optimal solution. • If an optimal solution exists, then there is also a basic feasible solution which is optimal.

In addition, basic feasible solutions are easy to detect: This opens the possibility to solve linear programs with the help of basic feasible solutions.

A rather naive approach to solve linear programs would be: For a given linear program max c T x s.t. Ax = b, x ≥ 0,

• find all extreme points of P = (A, b), i.e., all basic feasible solutions (there are at most m n if A ∈ R m×n ).

• select the best one among them (i.e. this x with c T x maximal).

Is there a more clever idea to solve linear programs?

The Simplex Method for solving linear programs

Given a matrix A ∈ R m×n and vectors b ∈ R m , c ∈ R n , consider the linear program max c T x s.t. Ax ≤ b x ≥ 0.
To solve the linear program with the help of the Simplex Method, one takes advantage of the following previously stated results: If a linear program has a bounded optimal solution, then there exists an extreme point on the boundary of the feasible region which is optimal (Main Theorem of Linear Programming). For a linear program given in equational form

max c T x s.t. Ax = b, x ≥ 0
we have even more:

• If P = (A, b
) is non-empty and bounded, there exists always an optimal solution.

• Among all optimal solutions, there is always a basic feasible solution.

• Basic feasible solutions are easy to detect: A feasible solution x is basic if and only if the columns of the matrix A B are linearly independent, where

B = j ∈ {1, . . . , n} : x j > 0 .
The idea of the Simplex Method is to start with an arbitrary basic feasible solution and, as long as the current solution is not optimal, to move to a "neighbored" basic feasible solution with a better objective function value. We first shall illustrate this method with the help of an introductory example (the linear program from Example 1) before stating it formally.

Example 4. Given the following linear program:

max x 1 + x 2 s.t. -x 1 + x 2 ≤ 1 x 1 ≤ 3 x 2 ≤ 2 x 1 , x 2 ≥ 0
As the linear program is not in equational form, we have to transform it by introducing slack variables in order to turn the inequalities into equations. The resulting equational form of the above linear program (with slack variables in bold) is:

max x 1 + x 2 s.t. -x 1 + x 2 + x 3 = 1 x 1 + x 4 = 3 x 2 + x 5 = 2 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0
From the linear program in equational form, we easily get x 0 = (0, 0, 1, 3, 2) T as initial basic feasible solution by taking the slack variables as basis B 0 = {3, 4, 5} and the original variables as non-basis N 0 = {1, 2}.

We next rewrite the linear program as so-called simplex tableau, having the basic variables as left hand side (in bold) and an additional row for the objective function value z = c T x:

x 3 = 1 + x 1 -x 2 x 4 = 3 -x 1 x 5 = 2 -x 2 z = x 1 + x 2
Considering the simplex tableau associated with x 0 = (0, 0, 1, 3, 2) T , we obviously have z = 0 as objective function value.

In order to improve z, we can increase the value of x 1 or x 2 , w.l.o.g. say x 2 (keeping x 1 = 0). How much depends on the tableau and the non-negativity constraints: from

x 3 = 1 + x 1 -x 2 , x 1 , x 2 , x 3 ≥ 0 we infer x 2 ≤ 1, from x 5 = 2 -x 2 and x 2 , x 5 ≥ 0 we infer x 2 ≤ 2.
Together, we conclude that x 2 = 1 is possible.

We update the tableau accordingly by rewriting the first row (to have x 2 as left hand side) and substituting this expression for x 2 in the other rows. The resulting tableau (with changes in bold) is

x 2 = 1 + x 1 -x 3 x 4 = 3 -x 1 x 5 = 1 -x 1 + x 3 z = 1 + 2x 1 -x 3
associated with the basic feasible solution x 1 = (0, 1, 0, 3, 1) T , B 1 = {2, 4, 5} and with objective function value z = 1. Improving z further is possible by increasing the value of x 1 only (as increasing x 3 would decrease z).

From the tableau and non-negativity constraints we see that no restriction comes from x 2 = 1 + x 1x 3 , the second row x 4 = 3x 1 and x 1 , x 4 ≥ 0 show x 1 ≤ 3, but x 5 = 1x 1 + x 3 and x 1 , x 3 , x 5 ≥ 0 result in x 1 ≤ 1. Hence, x 1 = 1 is possible.

We update the tableau accordingly by rewriting the third row (to have x 1 as left hand side) and substituting this expression for x 1 in the other rows. We get the new tableau (with changes in bold)

x 2 = 2 -x 5 x 4 = 2 + x 5 -x 3 x 1 = 1 -x 5 + x 3 z = 3 -2x 5 + x 3 associated with x 2 = (1, 2, 0, 2, 0) T , B 2 = {1, 2
, 4} and z = 3. Now, improving z is possible only by increasing the value of x 3 (as increasing x 5 would decrease z). From the tableau and non-negativity we see that x 4 = 2 + x 5x 3 and x 3 , x 4 , x 5 ≥ 0 result in x 3 ≤ 2, while the row x 1 = 1x 5 + x 3 does not restrict the value of x 3 . Hence, x 3 = 2 is possible.

We update the tableau accordingly by rewriting the second row (to have x 3 as left hand side) and substituting this expression for x 3 in the other rows. The resulting tableau (again with changes in bold) is

x 2 = 2 -x 5 x 3 = 2 + x 5 -x 4 x 1 = 3 + 0 -x 4 z = 5 -x 5 -x 4
associated with x 3 = (3, 2, 2, 0, 0) T , B 3 = {1, 2, 3} and z = 5. In this situation, we cannot increase a non-basic variable further without decreasing z (as x 5 and x 4 appear with negative signs). So, we are stuck. But x 3 is the optimal solution: Any feasible solution x with c T x = z has to satisfy z = 5 -x5 -x4 which implies z ≤ 5 (together with non-negativity). Hence, x 3 is optimal! In fact, x 3 is the unique optimal solution (as z = 5 requires x 4 = x 5 = 0 and the equations uniquely determine the values of x 1 , x 2 and x 3 ).

The geometric interpretation is as follows (see Figure 12): Starting with the initial basic feasible solution x 0 = (0, 0) (in the original variables only), the simplex method moves along the edges of the feasible region from one basic feasible solution to another, while the objective function value grows until it reaches the optimum.

-x + x < 1 1 2 x < 3 1 x > 0 1 x > 0 2 x < 2 2 1 x x 2 x 3 0
x Fig. [START_REF] Edmonds | A min-max relation for submodular functions on graphs[END_REF] The geometric interpretation of the basis exchanges performed in Example 4.

The previous example illustrated the solution method for linear programs found by Dantzig [START_REF] Dantzig | Maximization of a linear function of variables subject to linear inequalities[END_REF] (see also [START_REF] Dantzig | Notes on linear programming[END_REF][START_REF] Dantzig | The Diet Problem[END_REF]), now we state it formally:

The Simplex Method (Dantzig [START_REF] Dantzig | Maximization of a linear function of variables subject to linear inequalities[END_REF]) Input: a matrix A ∈ R m×n and vectors b ∈ R m , c ∈ R n , defining a linear program max c T x s.t. Ax ≤ b, x ≥ 0 Output:a vector x * maximizing the objective function 1. Transform the program into equational form (if necessary). 2. Find an initial basic feasible solution x 0 ∈ R n and the corresponding basis B 0 ⊆ {1, . . . , n} s.t. A B 0 is non-singular and x 0 j = 0∀ j / ∈ B 0 . Generate the corresponding simplex tableau T (B 0 ). 3. Move from one basic feasible solution x i with basis B i to a basic feasible solution

x i+1 with basis B i+1 and higher objective function value by selecting j ∈ B i and ℓ ∈ {1, . . . , n} \ B i and setting B i+1 := B i \ { j} ∪ {ℓ} s.t. c(x i+1 ) ≥ c(x i ) holds. 4. Stop if no further improvement is possible.

We will next discuss all the necessary steps of the Simplex Method in detail.

STEP 1 (Transformation).

As we need linear programs given in equational form max c T x s.t. Ax = b, x ≥ 0, inequalities and variables without sign restrictions are disturbing and the following transformation becomes necessary: If the given (in)equality system has a

• row A i• x ≤ b i ,
introduce a slack variable x n+i ≥ 0 and replace the row by

A i• x + x n+i = b i • row A j• x ≥ b j ,
introduce a slack variable x n+ j ≥ 0 and replace the row by

-A j• x + x n+ j = -b j
• variable x ℓ without sign restriction, introduce two new variables y ℓ ≥ 0 and z ℓ ≥ 0, and substitute x ℓ everywhere by y ℓz ℓ .

After applying an according transformation, the original linear program is in equational form, as required for the next step. with A = (A, I) and x = (x 1 , . . . , x n , . . . , x n+1 , . . . , x n+m ) if b ≥ 0 (otherwise, we multiply the equations with b i < 0 by -1). This works, since we have: Lemma 2. The original linear program is feasible if and only if every optimal solution x of ALP satisfies x n+1 = . . . = x n+m = 0. For any such optimal solution, its basic vector x B = (x 1 . . . , x n ) is a basic feasible solution of the original linear program.

The simplex tableau T (B 0 ) determined by B 0 is a system of m + 1 linear equations in variables x 1 , . . . , x n and z that has the same set of solutions as the original system Ax = b, z = c T x. In matrix notation, T (B 0 ) reads as

x B 0 = b -Ax N z = z 0 + c T x N
where x B 0 is the vector of basic variables, x N the vector of non-basic variables and

N = {1, . . . , n} \ B 0 , and b ∈ R m , c ∈ R n-m , A ∈ R m×(n-m) , z 0 ∈ R.
This always works, since we have in general:

Lemma 3. For each feasible basis B, there exists exactly one simplex tableau T (B)

x B = b -Ax N z = z 0 -c T x N with A = A -1 B A N , b = A -1 B b, c = c N -(c T B A -1 B A B ) T and z 0 = c T B A -1 B b.
For the initial basic feasible solution x 0 , we often have A B 0 = I which simplifies the construction of the first tableau by

A = A N , b = b, c = c N -(c T B A N ) T and z 0 = c T B b.
Note that from any tableau T (B), we can read off immediately the basic feasible solution x 0 by

x 0 i = b i ∀i ∈ B and x 0 i = 0 ∀i ∈ N,
and the objective function value c T x 0 = z 0 = z 0 + c T 0.

STEP 3 (Basis exchanges).

In each basis exchange (called pivot step) of the Simplex Method, we go from the current basis B and its tableau T (B) to a new basis B ′ and its tableau T (B ′ ). Thereby, a nonbasic variable x ℓ with ℓ ∈ N = {1, . . . , n} \ B has to be exchanged by a basic variable x k with k ∈ B in order to obtain the new basis B ′ = (B \ {k}) ∪ {ℓ} .

We say that x k leaves the basis and x ℓ enters the basis. This leads to the following questions:

• Which conditions have x k and x ℓ to satisfy?

• How to select them if there is no unique choice?

• How to obtain the new tableau T (B ′ )?

We first discuss the conditions for entering and leaving variables. A nonbasic variable x ℓ with ℓ ∈ N may enter the basis if and only if its coefficient c ℓ in the last row of the tableau T (B)

x B = b -A x N z = z 0 + c T x N
is positive, i.e., if c T ℓ > 0 holds (as only incrementing such non-basic variables can increase the value z of the objective function). For chosen x ℓ with ℓ ∈ N, the leaving basic variable must correspond to a row of the tableau which limits the increment of x ℓ most strictly:

• All nonbasic variables x i with i ∈ N \ {ℓ} should remain zero, hence the j-th row of the tableau together with non-negativity yields

x j = b j -a jℓ x ℓ ≥ 0.
• If a jℓ ≤ 0, this inequality does not restrict the increase of x ℓ in any way.

• For any a jℓ > 0, we have x ℓ ≤ b j a jℓ . Thus, we can choose x k with a kℓ > 0 and b k a kℓ minimal. This leads to the following fundamental theorem which in addition shows how to detect two exceptional cases: unboundedness (i.e. the case where the linear program does not have a finite optimal solution) and degeneracy (i.e. the case where several bases correspond to a single basic feasible solution). In degenerate basic feasible solutions, some basic variables are zero: e.g., for the basic feasible solution x 0 = (0, 0, 0, 2) T , the following bases

B = {1, 4} or B ′ = {2, 4} or B ′′ = {3, 4} are possible.

Theorem 9 (Basis Exchange Theorem). Let x be a basic feasible solution with basis B and simplex tableau T (B)

x B = b -A x N z = z 0 + c T x N
and let ℓ ∈ N with c ℓ > 0. Then we have the following: Exceptions are degenerate pivot-steps, where we stay at the same extreme point x 0 as only the feasible basis changes. Possible reasons are superfluous variables or redundant inequalities (whose removal resolves degeneracy) or geometric reasons (e.g. that more than dim(P = (A, b)) hyperplanes meet in x 0 ). The resulting difficulty is so-called cycling:

• If A •ℓ ≤ 0, then the linear program is unbounded. • If A •ℓ ≤ 0,
• If degeneracy occurs, longer runs of degenerate bases exchanges (without improvement in the objective function value) may be necessary. • It may even happen that some tableau is repeated in a sequence of degenerate exchange steps (called cycling) s.t. the algorithm passes through an infinite sequence of tableaux and, thus, fails.

To finish a basis exchange, updating the simplex tableau according to the new basis is required. For the new basis B ′ , one can calculate the new tableau T (B ′ )

x B ′ = b -A x N ′ z = z 0 + c T x N ′ by A = A -1 B ′ A N ′ , b = A -1 B ′ b, c = c N ′ -(c T B ′ A -1 B ′ A N ′ ) T , z 0 = c T B ′ A -1
B ′ b from the original matrix A and the vectors b and c.

In computer implementations of the Simplex Method, however, this is never done (as it is inefficient). Note that for the next basis exchange, we only need the vector c (to select the next entering variable ℓ ∈ N ′ with c ℓ > 0), and for the chosen ℓ ∈ N ′ , the column A •ℓ and the vector b (to find the next leaving variable k ∈ B ′ ). For that, the matrix A -1 B ′ is computed (which is required to calculate all needed entries). This procedure is known as Revised Simplex Algorithm, see [START_REF] Dantzig | Linear Programming 2/ Theory and Extensions[END_REF].

Step 4 (Testing for Optimality) The Simplex Method stops if an optimal solution is found. To detect this situation, we have the following optimality criterion of a simplex tableau: Lemma 4. Consider a feasible basis B and its simplex tableau T (B)

x B = b -A x N z = z 0 + c T x N
If the basic feasible solution x 0 corresponding to B is non-degenerate (i.e., if b > 0), then we have: x 0 is the optimal solution if and only if c ≤ 0. Indeed, x 0 = b 0 has the objective function value equal to z 0 , while for any other feasible solution x, we have xN ≥ 0 and c T x = z 0 + c T xN ≤ z 0 (by c ≤ 0).

It is left to discuss the efficiency of the Simplex Method and pivoting. The number of pivot steps (i.e. basis exchanges) for solving a linear program by the Simplex Method strongly depends on the choices which variables should leave or enter the basis: Figure 14 shows an example where, starting from an initial basic feasible solution, the optimal solution could be reached in three or two steps. We do not know in advance which choices will be good if there are several possibilities of improving variables (i.e. nonbasic variables x j with j ∈ N from the current tableau with c j > 0). We denote the index set of the improving variables by N + .

A pivot rule is a rule how to select the entering variable among the improving ones (some rules also specify the choice of the leaving variable, if necessary). Some well-known pivot rules are:

• Largest Coefficient Rule: choose an improving variable x ℓ such that c ℓ = max c j : j ∈ N + (to maximize the improvement of z per unit increase of x ℓ ) • Largest Increase Rule: choose an improving variable that yields the maximal improvement in z (this rule is computationally more expensive, but locally maximizes the progress) • Steepest Edge Rule: choose an improving variable maximizing the value

c T (x new -x old ) ||x new -x old ||
(to move the current basic feasible solution into a direction closest to the one of the objective function c) • Bland's Rule: choose the improving variable x ℓ with the smallest index ℓ ∈ N + ; if there are several possibilities for the leaving variable, also take the one with the smallest index.

The Largest Coefficient Rule is the original rule by Dantzig [START_REF] Dantzig | Notes on linear programming[END_REF], whereas the Steepest Edge Rule is the champion in practice, and Bland's rule is particularly important, since we have:

Theorem 10 (Bland [START_REF] Bland | New finite pivoting rules for the simplex method[END_REF]). The Simplex Method with Bland's rule is always finite, as cycling is impossible.

Using other pivot rules, the Simplex Method may cycle (and theoretically, this is the only possibility how it may fail). In fact, for (almost) all pivot rules, there are worst case examples known that require an exponential number of pivot steps (e.g. for Dantzig's rule one in n variables and inequalities requiring 2 n -1 pivot steps by Klee & Minty [START_REF] Klee | How good is the simplex algorithm?[END_REF]). Note that in practice, most implementations of the Simplex Method try to circumvent cycling via different perturbation techniques.

In theory, the best known worst case bound for the running time of the Simplex Method is, therefore, e c √ n ln n for linear programs with n variables and constraints, using a simple randomized pivot rule (randomly permute the indices of the variables, then apply Bland's rule).

In practice, however, the Simplex Method performs very satisfactory even for large linear programs. Computational experiments indicate that it reaches, for linear programs with m equations, an optimal solution in something between 2m and 3m pivot steps, with about O(m 2 ) arithmetic operations per pivot step, such that the expected running time is about O(m 3 ).

Linear Programming Duality

In this subsection, we address the problem to obtain bounds for the objective function value of a linear program, e.g. an upper bound for the value of an optimal solution of a maximization problem, without knowing the optimum before. To this end, we shall start with an introductory example.

Example. Consider the following linear program

: max 2x 1 + 3x 2 s.t. 4x 1 + 8x 2 ≤ 12 2x 1 + x 2 ≤ 3 x 1 , x 2 ≥ 0
Without computing the optimum z * , we can infer from the first inequality and nonnegativity that z * ≤ 12 holds as

2x 1 + 3x 2 ≤ 4x 1 + 8x 2 ≤ 12.
We obtain a better bound by scaling the inequality by a factor 2:

2x 1 + 3x 2 ≤ 2x 1 + 4x 2 ≤ 6.
Adding the two inequalities and scaling by a factor 3 even yields:

2x 1 + 3x 2 ≤ 2x 1 + 3x 2 ≤ 5.
How good can a so-obtained upper bound u ≥ c T x for all feasible solutions x of the studied linear program be? To answer this question, we shall derive an inequality of the form

d 1 x 1 + d 2 x 2 ≤ u, where d 1 ≥ 2, d 2 ≥
3, and u is as small as possible. Then, for all x 1 , x 2 ≥ 0, we indeed have

2x 1 + 3x 2 ≤ d 1 x 1 + d 2 x 2 ≤ u.
For that, we combine the two inequalities of the linear program with some nonnegative coefficients y 1 and y 2 , obtain We now shall formalize this process. Given a matrix A ∈ R m×n and vectors b ∈ R m , c ∈ R n . Consider the primal linear program (P)

(
max c T x s.t. Ax ≤ b x ≥ 0.
To determine an upper bound u ≥ c T x for all x ∈ P(A, b), combine the m inequalities of Ax ≤ b with non-negative coefficients y 1 , . . . , y m s.t. the resulting inequality has the jth coefficient at least c j , for 1 ≤ j ≤ m, the right hand side is as small as possible. This leads to the dual linear program (D)

min b T y s.t. A T y ≥ c y ≥ 0.
The primal and the dual linear program are related as follows:

Theorem 11 (Weak Duality Theorem). Consider the dual linear programs

max c T x s.t. A x ≤ b, x ≥ 0 (P) min b T y s.t. A T y ≥ c, y ≥ 0 (D)
• For each feasible solution y of (D), the value b T y provides an upper bound for the maximum objective function value of (P), i.e., we have c T x ≤ b T y for each feasible solution x of (P). • Both (P) and (D) have a feasible solution. Then both linear programs have an optimal solution, say x * of (P) and y * of (D), and c T x * = b T y * holds.

• If (P) is unbounded, then (D) is infeasible. • If (D) is unbounded (from below), then (P) is infeasible.
Proofs of the two duality theorems can be found in [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF], for instance.

The two duality theorems are valid for all kinds of linear programs, we only have to construct the dual program properly: For a maximization problem with constraint matrix A ∈ R m×n , right hand side vector b ∈ R m , objective vector c ∈ R n , the dual program has

• variables y 1 , . . . , y m where y i corresponds to the ith constraint and satisfies

y i    ≥ 0 ≤ 0 ∈ R    if A i• x    ≤ ≥ =    b i
• n constraints, where the jth constraint corresponds to x j and reads

A • j y    ≥ ≤ =    c j if x j    ≥ 0 ≤ 0 ∈ R   
• the objective function b T y which is to be minimized.

We can summarize these conditions as the following "Dualization Recipe":

Primal linear program Dual linear program Variables x 1 , x 2 , . . . , x n y 1 , y 2 , . . . , y m Matrix A ∈ R m×n A T ∈ R n×m Right-hand side b ∈ R m c ∈ R n Objective function max c T x min b T y Constraints ith constraint has ≤ y i ≥ 0 ≥ y i ≤ 0 = y i ∈ R x j ≥ 0 jth constraint has ≥ x j ≤ 0 ≤ x j ∈ R =
The implications for the solvability of two dual linear programs are due to the Farkas Lemma [START_REF] Farkas | A Fourier-féle mechanikai elv alkamazásai[END_REF][START_REF] Farkas | Über die Theorie der Einfachen Ungleichungen[END_REF] (see also [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] for a proof):

Theorem 13 (Farkas Lemma). For A ∈ R m×n and b ∈ R m , exactly one of the following two possibilities occurs:

1. There is a vector x ∈ R n satisfying Ax = b and x ≥ 0. 2. There is a vector y ∈ R m s.t. y T A ≥ 0 T and y T b < 0.

Remark. The Farkas Lemma has several variants for the different types of linear programs, which can be summarized as follows:

The This leads to duality-based Simplex Methods to solve a linear program: the Dual Simplex Method and so-called primal-dual methods:

• To solve a linear program, we can apply the Simplex Method either to the primal linear program or to its dual linear program. The Dual Simplex Method solves the dual linear program by starting with a dual feasible basis and trying to attain primal feasibility while maintaining dual feasibility throughout. This can be substantially faster if -the dual linear program has less constraints than the primal linear program, or -an initial (dual) basic feasible solution is easy to obtain, or -the dual linear program is less degenerate.

• Primal-Dual Methods solve a linear program by iteratively improving a feasible solution of the dual linear program:

-Consider a primal linear program given by max c T x s.t. Ax = b, x ≥ 0.

-For a feasible dual solution y, define J = { j ∈ {1, . . . , n} : A • j y = c j }.

-A dual solution y is optimal if and only if there is a feasible primal solution x with x j = 0 ∀ j ∈ {1, . . . , n} \ J.

In addition to the aforementioned relations between primal and the dual linear programs, we have even more: If a primal linear program is a formulation for a combinatorial optimization problem, then its dual linear program has also an interpretation as a combinatorial optimization problem, related to the combinatorial object being dual to the original studied one.

We shall illustrate this relation with the help of our running example, the Network Flow Problem. N = (D;s,t;c) with digraph D = (V, A) and capacities c ∈ Z A . Recall from Problem 3 that the linear programming formulation of the Maximum Network Flow Problem is:

Example 5 (Dualization of Maximum Network Flow). Given a network

max ∑ a∈δ + (s) x a s.t. ∑ a∈δ -(v) x a = ∑ a∈δ + (v) x a ∀v ∈ V \ {s,t} x a ≤ c a ∀a ∈ A x a ≥ 0 ∀a ∈ A With V ′ = V \ {s,
t} denoting the set of internal nodes of the digraph, let

• F ∈ Z A×V ′ be the matrix of the flow conservation constraints,

• d ∈ Z A with d a = 1 if a ∈ δ + (s)
, d a = 0 otherwise be the objective vector.

Then the primal linear program (P) encoding the Maximum Flow Problem reads in matrix notation:

max d T x s.t. F x = 0 I x ≤ c x ≥ 0
For the dualization, we use one variable

• z v for the flow conservation constraint of v ∈ V ′ ,
• y a for the capacity constraint of a ∈ A.

This leads to the following dual linear program (D)

min c T y s.t. F T z+ I T y ≥ d y ≥ 0
A closer look to the dual program shows that the dual program has

• one variable z v ∈ R corresponding to the flow conservation for each v ∈ V ′ : x(δ -(v)) -x(δ + (v)) = 0
• one variable y a ≥ 0 corresponding to the capacity constraint for each a ∈ A,

• for each primal variable x a , a ∈ A, one constraint

F •a z + I •a y ≥ d a which reads, for a = (u, v) ∈ A z v -z u + y a ≥ 0 if u = s, v = t z v + y a ≥ 1 if u = s, v = t -z u + y a ≥ 0 if u = s, v = t
• the objective function c T y which is to be minimized.

What is the combinatorial interpretation of the dual program? For a network N = (D; s,t; c) with D = (V, A), consider the dual program

min c T y s.t. z v -z u + y a ≥ 0 ∀ a = (u, v) ∈ A z s = 1 z t = 0 y a ≥ 0 ∀ a = (u, v) ∈ A Recall that for a partition of V = V s ∪ V t with s ∈ V s and t ∈ V t , the subset of arcs δ + (V s ) = {(u, v) ∈ A : u ∈ V s , v ∈ V t } is an (s,t)-cut. Hence, each (s,t)-cut δ + (V s ) of a network N = (D; s,t; c) with D = (V, A) corresponds to a feasible solution (z, y) T ∈ R V ′ × R A + of the dual program with z v = 1 if v ∈ V s , z u = 0 if u ∈ V t y a = 1 if a ∈ δ + (V s ), y a = 0 if a ∈ δ + (V s ).
Recall further that the flow across the (s,t)-cut (V s ,V t ) is

f (V s ,V t ) = ∑ u∈V s ,v∈V t f (uv) -∑ u∈V s ,v∈V t f (vu)
and its capacity is

c(V s ,V t ) = ∑ u∈V s ,v∈V t c(uv).
Obviously, val( f ) ≤ c(V s ,V t ) holds for any (s,t)-cut. We have even more: Since every (s,t)-flow f satisfies the capacity constraints, we have that

f (V s ,V t ) ≤ c(V s ,V t ) and thus val( f ) ≤ c(V s ,V t )
holds for any (s,t)-cut. This upper bound for the maximum flow in a network also follows from the Weak Duality Theorem (Theorem 11), and the Max-Flow Min-Cut Theorem (Theorem 1), is a famous special case of the Strong Duality Theorem (Theorem 12), which implies:

max d T x = min c T y s.t. F x = 0 s.t. F T z + I T y ≥ d I x ≤ c y ≥ 0 x ≥ 0
In particular, the linear programming formulation for Maximum Network Flow from Problem 3 is the "right" formulation as it does not only properly encode the primal problem, but also its dual linear program has an interpretation as a Minimum Cut Problem, the combinatorial problem being dual to the original studied Network Flow Problem.

Integer Programming and the Network Flow Problem

In the previous section, we considered a linear program, i.e. the problem to maximize/minimize the value of c T x among all vectors x ∈ R n satisfying A x ≤ b x ≥ 0

where A ∈ R m×n is a given matrix and b ∈ R m , c ∈ R n are given vectors.

If in some practical settings, the studied objects are entities as workers, goods or planes which cannot be divided, we do not consider variables x ∈ R n but x ∈ Z n . This leads to an Integer Linear Optimization Problem. In this section we discuss

• how linear programs and integer linear programs are related , • why integer linear programs are hard to solve in general, and • what is special for solving Integer Network Flow Problems. We illustrate this formal definition with the help of a small example: Example 6. This example shows an integer linear program given explicitly as well as in matrix formulation:

Integer linear programs and their linear relaxations

max x 1 + x 2 is the linear objective function c T x s.t. -x 1 + x 2 ≤ 1 x 1 ≤ 3 form the linear constraints Ax ≤ b x 2 ≤ 2 x 1 , x 2 ≥ 0 are the non-negativity constraints x ≥ 0 x 1 , x 2 ∈ Z are the integrality constraints x ∈ Z 2
Figure 15 gives the graphical interpretation of the constraints and the resulting polyhedron P(A, b).

In an integer linear program

-x + x < 1 1 2
x < 3 In particular and in contrast to the case of Linear Programming, an optimal solution of an integer linear program is not necessarily attained on the boundary of P(A, b), but may be situated in its interior. Figure 16( This makes the problem hard in general (see, for instance, [START_REF] Kannan | On the computational complexity of integer programming problems[END_REF] for a proof and [START_REF] Bertsimas | Optimization over Integers. Dynamic Ideas[END_REF][START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF][START_REF] Nemhauser | Integer Programming and Combinatorial Optimization[END_REF][START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF][START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF] for further information): Theorem 14. It is NP-hard to decide whether an integer linear program has a solution above/below a certain threshold.

In contrary, the corresponding linear program obtained by dropping the integrality requirement, can be solved in polynomial time. How are linear and integer linear programs related to each other? The linear relaxation can be solved in polynomial time, but its optimal solution might be fractional and, thus, no solution of the corresponding integer linear program.

However, the convex hull of all integral solutions of an integer linear program is a polyhedron and, thus, can be described by means of linear inequalities, see Figure 16(b). Thus, in principle there exists a constraint system for each integer linear program, called ideal formulation, such that the feasible region has integral extreme points only: Definition 9. For an integer linear program

max c T x, Ax ≤ b, x ∈ Z n a linear program max c T x, A x ≤ b, x ∈ R n is an ideal formulation if P(A, b) = {x ∈ R n + : Ax ≤ b} = conv{x ∈ Z n + : Ax ≤ b}.
As the optimum of a linear program is always attained at an extreme point of P(A, b), linear programming techniques can be applied to solve integer linear programs given as ideal formulations! This leads to polynomial time solvability, provided that the required inequalities can be separated in polynomial time (i.e., that it can be checked efficiently whether a given point satisfies all inequalities or violates some of them; for instance, this is the case if the ideal formulation contains only a polynomial number of constraints).

In general, finding an ideal formulation for an integer linear program is as hard as solving the problem itself. In some special cases, however, certain properties related to the underlying combinatorial problem can lead to the desired situation, e.g. if the constraint matrix A of the integer linear program has a special structure. We will next define such a type of matrices.

Definition 10. •

A matrix A ∈ Z m×n of full row rank is unimodular if the determinant of each basis of A is in {-1, 1}. • A matrix A ∈ Z m×n is totally unimodular if the determinant of each square sub- matrix of A is in {-1, 0, 1}.
Remark. Unimodular and totally unimodular matrices must have entries in {-1, 0, 1} only. A matrix A ∈ Z m×n is totally unimodular if and only if

• (A, I) is totally unimodular;

• A T is totally unimodular.

The following matrices A, A T , (A T , I) are examples of totally unimodular matrices:

1 1 0 1 0 1   1 1 1 0 0 1     1 1 1 0 0 1 0 0 1 0 0 1 0 0 1  
Recall that a polyhedron is integral if all its extreme points are integral. The relation of unimodularity and the integrality of polyhedra coming from integer programming formulations is as follows (see [START_REF] Hoffman | Integral Boundary Points of Convex Polyhedra[END_REF] for the proof and [START_REF] Bertsimas | Optimization over Integers. Dynamic Ideas[END_REF][START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF][START_REF] Nemhauser | Integer Programming and Combinatorial Optimization[END_REF][START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF][START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF] for further information): Remark. The proof of the latter theorem is based on Cramer's rule: For a nonsingular matrix A ∈ R n×n and b ∈ Z n , we have

Ax = b ⇐⇒ x = A -1 b ⇐⇒ x i = det(A i ) det(A)
where A i is obtained from A by replacing the i-th column by b. From det(A) ∈ {-1, 1} for totally unimodular matrices, it follows x i ∈ Z.

Thus, all integer linear programs with (totally) unimodular constraint matrices have an integral polyhedron as the convex hull of its feasible solutions and can be solved with the help of linear programming techniques.

However, as the hardness of solving integer linear programs implies, we do not always have totally unimodular constraint matrices. A more general setting involves Linear Programming Duality: Definition 11. A system Ax ≤ b of linear inequalities is totally dual integral (TDI) if the linear program min b T y s.t. A T y = c, y ≥ 0 has an integral optimal solution for every integral vector c such that max c T x, Ax ≤ b is bounded.

Note that A is totally unimodular if and only if the system Ax ≤ b, x ≥ 0 is totally dual integral for all integral vectors b.

Also the concept of totally dual integrality, introduced by Edmonds & Giles [START_REF] Edmonds | A min-max relation for submodular functions on graphs[END_REF], is related to the integrality of polyhedra: To summarize: Ideal formulations follow the idea to go back to linear programs in order to solve integer linear programs.

In fact, we can apply linear programming techniques and solve an integer linear program in polynomial time in one of the following situations: the canonical integer linear programming formulation A x ≤ b, x ≥ 0 is

• ideal as P(A, b) is integral; • not ideal, but the constraint system A x ≤ b, x ≥ 0 with P(A, b) = conv{x ∈ Z n + : A x ≤ b}
is easy to find by adding (polynomially many) further constraints;

• not ideal in general, but is ideal for some special cases where additional combinatorial properties are satisfied.

Note that ideal formulations for integer linear programs typically involve a much larger number of constraints than compact formulations using integrality requirements (which makes the separation problem harder).

For most integer optimization problems, no ideal formulation is known at all. In this general situation, one might start from a canonical integer linear program A x ≤ b, x ≥ 0 and try to find hyperplanes approximating conv{x ∈ Z n + : A x ≤ b} at the "right place" (i.e. near the optimal solution as illustrated in Figure 17).

Such approaches to enhance the original formulation are called cutting plane methods and work as follows:

Generic Cutting Plane Method

Input: an integer linear program (ILP) max c T x, Ax ≤ b, x ∈ Z n Output: an optimal integer solution x * 1. Solve the linear relaxation (LP) max c T x, Ax ≤ b, x ∈ R n .

If P(A, b) is empty, then the ILP is also infeasible, and STOP. Else, let x * be an optimal (extreme point) solution of the LP. 2. If x * is integral, then STOP because x * is also optimal for the ILP. 3. If x * is not integral, then find an inequality that is satisfied by all feasible solutions of the ILP, but is violated by x * . 4. Append this inequality (the cutting plane) to the LP, and proceed with Step 1.

A classical way to generate new valid inequalities from the known constraints in Ax ≤ b are so-called Chvátal-Gomory cuts, introduced by Chvátal [START_REF] Chvátal | Edmonds polytopes and a hierarchy of combinatorial problems[END_REF] and implicitly by Gomory [START_REF] Gomory | Outline of an algorithm for integer solutions to linear programs[END_REF]. In fact, every valid inequality for the convex hull of all integral solutions can be generated by applying the Chvátal-Gomory procedure (i.e., adding all Chvátal-Gomory cuts) to P(A, b) a finite number of times. This guarantees that cutting plane methods indeed terminate.

It is a currently active field of research to find more efficient cutting planes than the classical ones, as e.g. split cuts, intersection cuts and others [START_REF] Balas | Optimizing Over the Split Closure[END_REF][START_REF] Basu | Intersection Cuts with Infinite Split Rank[END_REF][START_REF] Conforti | Corner Polyhedron and Intersection Cuts[END_REF][START_REF] Pia | A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts[END_REF].

For more information on Integer Programming, see e.g. [START_REF] Bertsimas | Optimization over Integers. Dynamic Ideas[END_REF][START_REF] Grötschel | Geometric Algorithms and Combinatorial Optimization[END_REF][START_REF] Nemhauser | Integer Programming and Combinatorial Optimization[END_REF][START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF][START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF].

Computing integer network flows

We finally discuss the Integer Network Flow Problem. Given a network N = (D; s,t; c) with D = (V, A), the problem of finding an integral (s,t)-flow f : A → Z maximizing the value val( f ). In order to formulate this problem as integer linear program, we again need

• the variables x a to express the flow f (a) on each arc a ∈ A,

• the linear objective function max ∑ a∈δ + (s) x a of maximizing the flow leaving the source s, • the linear flow conservation constraints ∑ a∈δ -(v) x a = ∑ a∈δ + (v) x a ∀v ∈ V \ {s,t}, • the linear capacity constraints x a ≤ c a ∀a ∈ A, and in addition, integrality is required for all variables:

x a ∈ Z ∀a ∈ A. Indeed, every vector x ∈ Z A satisfying all the above constraints corresponds to an integral (s,t)-flow f , an optimal solution to a maximum flow. How hard or easy is it to compute a maximum flow as optimal solution of the above integer linear program?

As integer linear programs are hard to solve in general, this leads to the question whether we can find an ideal formulation by taking advantage of special combinatorial properties of the underlying Network Flow Problem.

Recalling that all integer linear programs with (totally) unimodular constraint matrices have an integral polyhedron as the convex hull of its feasible solutions, we wonder whether the constraint matrices for the Network Flow Problem satisfy this property.

Indeed, one example for unimodularity are node/arc incidence matrices of digraphs, the underlying discrete structure for the networks of our flow problem: Theorem 17. The node/arc incidence matrix of any digraph D = (V, A) is totally unimodular.

The proof of the latter theorem is based on the following characterization of totally unimodular matrices: Theorem 18. A matrix M ∈ Z m×n is totally unimodular if and only if each subset I ⊆ {1, . . . , n} of columns has a bipartition I = I A ∪ I B s.t. for all rows j ∈ {1, . . . , m}, we have ∑ i∈I A m ji -∑ i∈I B m ji ∈ {-1, 0, 1}. Thus, we shall study how our constraint matrix is related to this property.

In fact, for a network N = (D; s,t; c) with digraph D = (V, A), the flow conservation matrix F ∈ Z V ′ ×A has one row for each of the constraints

∑ a∈δ -(v)
x a -∑ a∈δ + (v)

x a = 0 ∀v ∈ V ′ = V \ {s,t}. As a matrix is totally unimodular if and only if its transposed matrix is totally unimodular, it follows for the dual linear program: To conclude: the latter results form an example par excellence in the field of socalled Polyhedral Combinatorics, a powerful, coherent and unifying tool for Combinatorial Optimization, involving algorithms, the geometry of solution sets and minmax relations with dual problems. The studied Network Flow Problem demonstrates that these aspects are closely related in general: "Often a polynomial-time algorithm yields, as a by-product, a description (in terms of inequalities) of an associated polyhedron. Conversely, an appropriate description of the polyhedron often implies the polynomial-time solvability of the associated optimization problem, by applying linear programming techniques. With the duality theorem of linear programming, polyhedral characterizations yield min-max relations, and vice versa."

Alexander Schrijver

Fig. 2 ADefinition 2 .

 22 Fig.2A network consisting of a digraph with source s, sink t and arc capacities.

Fig. 3 AProblem 2 (

 32 Fig. 3 A network with (s,t)-flow f of value val( f ) = 8 (on each arc a ∈ A, its flow value and capacity are indicated by f (a)/c a ).

  Fig.[START_REF] Bland | New finite pivoting rules for the simplex method[END_REF] A network with an (s,t)-cut V s = {s, x, y}, V t = {t, w, z} and capacity c(V s ,V t ) = 24 (as sum of the capacities of all forward arcs crossing the dashed line).

Fig. 5 A

 5 Fig.5A network with (s,t)-flow f and augmenting (s,t)-path P with residual capacity ∆ f (P) = 1 (resulting as minimum value of the residual capacities of its arcs).

Fig. 6 A

 6 Fig.6A network with a (s,t)-flow f and the flow f ′ obtained by augmentation.

Definition 5 .

 5 A linear program (LP) is as follows: Maximize/Minimize the value of c T x among all vectors x ∈ R n satisfying A x ≤ b x ≥ 0 (optional) where A ∈ R m×n is a given constraint matrix, b ∈ R m a given right hand side vector, and c ∈ R n a given objective function vector.

Fig. 8

 8 Fig.[START_REF] Dantzig | Notes on linear programming[END_REF] The graphical interpretation of the constraints and the feasible region (the shaded region) of the linear program given in Example 1.

Problem 3 (

 3 Thus, the Maximum Network Flow Problem of finding an (s,t)-flow f : A → R maximizing the value val( f ) reads as linear program: Maximum Network Flow Problem (LP Formulation)). Given a network N = (D; s,t; c) with digraph D = (V, A), solve the following linear program:

  Note that the empty set and C itself are trivial extremal sets of C. Special extremal sets are extreme points in C which cannot be obtained as proper convex combination of some other points in C, see Figure10for examples.

Fig. 10

 10 Fig. 10 Extremal sets of convex sets.

Figure 11 Fig. 11 A

 1111 Figure 11 illustrates different faces of a polytope.

Theorem 8 .

 8 A feasible solution x of a linear program max c T x s.t. Ax = b, x ≥ 0 is basic if and only if the columns of the matrix A K are linearly independent, where K = j ∈ {1, . . . , n} : x j > 0 .

STEP 2 (

 2 Initial basic feasible solution). Consider a linear program in equational form. We distinguish the following two cases. If the original linear program was given in inequality form max c T x s.t. Ax ≤ b, x ≥ 0, then the transformation in STEP 1 into equational form with the help of slack variables x n+1 , . . . , x n+m yields max c T x s.t. Ax = b x ≥ 0 with A = (A, I) and x = (x 1 , . . . , x n , x n+1 , . . . , x n+m ). By the structure of A, an obvious basic feasible solution of the transformed linear program is x 0 = 0 b with basis B 0 = {x n+1 , . . . , x n+m } (i.e. containing all slack variables). If the linear program is already given in equational form max c T x s.t. Ax = b, x ≥ 0, there is no obvious initial basic feasible solution (as x = 0 is infeasible if b = 0). For each row of Ax = b, we introduce an auxiliary variable x n+i = b i -A T i• x and find values for x 1 , . . . , x n s.t. x n+i = 0 holds for all 1 ≤ i ≤ m by solving the auxiliary linear program ALP max -∑ i≤m x n+i s.t. Ax = b, x ≥ 0

Fig. 13

 13 Fig.[START_REF] Edmonds | Theoretical improvements in algorithmic efficiency for network flow problems[END_REF] Basis exchanges in the non-degenerate and in the degenerate case.

Fig. 14

 14 Fig. 14 Different basis exchanges towards the optimal solution.

Theorem 12 (

 12 Strong Duality Theorem). For the dual linear programs max c T x s.t. A x ≤ b, x ≥ 0 (P) min b T y s.t. A T y ≥ c, y ≥ 0 (D) exactly one of the following possibilities occurs: • Neither (P) nor (D) has a feasible solution. • (P) is unbounded and (D) has no feasible solution. • (P) has no feasible solution and (D) is unbounded.

  system Ax ≤ b The system Ax = b has a solution y ≥ 0 and y T A ≥ 0 y T A ≥ 0 T implies x ≥ 0 if and only if imply y T b ≥ 0 that y T b ≥ 0 has a solution y ≥ 0 and y T A = 0 y T A = 0 T implies x ∈ R if and only if imply y T b ≥ 0 that y T b = 0 That is: if the primal and the dual linear program are neither infeasible nor unbounded, then the maximum of the primal program (P) equals the minimum of the dual program (D).

Definition 7 .

 7 We first address the question what an integer linear program is. An integer linear program (ILP) is as follows: maximize/minimize the value of c T x among all vectors x ∈ Z n satisfying A x ≤ b x ≥ 0 where A ∈ R m×n is a given constraint matrix, b ∈ R m a given right hand side vector, and c ∈ R n a given objective function vector (typically, also the entries of A, b, c are integral in this case).

2 Fig. 15

 215 Fig.[START_REF] Farkas | Über die Theorie der Einfachen Ungleichungen[END_REF] The graphical interpretation of the constraints and the polyhedron P(A, b) (the shaded region) containing the feasible solutions x ∈ Z 2 of the integer linear program given in Example 6.

Fig. 16

 16 Fig.[START_REF] Ford | Maximum flow through a network[END_REF] The feasible points of an integer linear program (a) and a linear constraint system for the convex hull of all its integral solutions (b).

Definition 8 .

 8 For an integer linear program max c T x, Ax ≤ b, x ∈ Z n the linear program max c T x, Ax ≤ b, x ∈ R n obtained by dropping the integrality requirements is called a linear relaxation as its feasible region P(A, b) contains all integral feasible points x ∈ P(A, b) ∩ Z n of the corresponding integer linear program.

Theorem 15 .

 15 Consider a matrix A ∈ Z m×n . • For A with full row rank, P = (A, b) = x ∈ R n + : Ax = b is integral for all right hand side vectors b ∈ Z m with P = (A, b) = / 0 if and only if A has full row rank and is unimodular. • P (A, b) = x ∈ R n + : Ax ≤ b is integral for all right hand side vectors b ∈ Z m with P (A, b) = / 0 if and only if A is totally unimodular.

Theorem 16 .

 16 If the system Ax ≤ b is totally dual integral, A ∈ R m×n and b ∈ R m , then we have: • The primal problem max c T x s.t. Ax ≤ b has an integral optimal solution for all c ∈ Z n ; • The polytope P(A, b) = {x ∈ R n : Ax ≤ b} is integral.

Fig. 17

 17 Fig.[START_REF] Ford | Network Flow Theory[END_REF] The feasible points of an integer linear program and additional linear constraints (cutting planes) approximating the convex hull of all its integral solutions.

Problem 4 (

 4 Thus, the problem of finding an integral (s,t)-flow f : A → Z of maximal value val( f ) leads to: Integer Maximum Network Flow Problem). Given a network N = (D; s,t; c) with digraph D = (V, A). Finding an (s,t)-flow f : A → Z maximizing the value val( f ) by solving the following integer linear program:max ∑ a∈δ + (s) x a s.t. ∑ a∈δ -(v) x a = ∑ a∈δ + (v) x a ∀v ∈ V \ {s,t} x a ≤ c a ∀a ∈ A x a ≥ 0 ∀a ∈ A x a ∈ Z ∀a ∈ A With V ′ = V \ {s,t} denoting the set of internal nodes of the digraph, let again • F ∈ Z A×V ′ be the matrix of the flow conservation constraints, • d ∈ Z A with d a = 1 if a ∈ δ + (s), d a = 0 otherwise be the objective vector. Then the program encoding the Integer Maximum Network Flow Problem reads in matrix notation: max d T x s.t. F x = 0 I x ≤ c x ∈ Z A +

FCorollary 1 .

 1 The column of F for arc a = (u, v) ∈ A reads as follows: is the node/arc incidence matrix of a digraph and, thus indeed totally unimodular. As adding the identity matrix I to a totally unimodular matrix yields again a totally unimodular matrix, this implies: The Maximum Network Flow Problemmax d T x s.t. F x = 0 I x ≤ c, x ≥ 0has for all integral capacities c ∈ Z A + an integral optimum.

Corollary 2 .

 2 The Minimum Cut Problem min c T y s.t. F T z+ I T y ≥ d y ≥ 0 has for all integral vectors d ∈ Z A + an integral optimum.

  every vector x ∈ R A satisfying all the above constraints corresponds to a valid (s,t)-flow f , an optimal solution of this linear program corresponds to a maximal flow.

	Example 2. The Maximum Network Flow Problem with the network from Figure 2
	reads as explicit linear program:
	max x sw +x sx +x sy
	s.t. x sw	x sx	x sy	-x wt -x wy +x wy +x xy -x xy -x xz	-x yt -x yz	= 0 = 0