Exercise 9

Thu 09.10.2014

Y346

Homework (Assignment 9.1) is due at the beginning of the next week’s exercise session on Friday, and can be returned by email, or handed to the assistant at the exercise session.

Blackboard assignment is 9.2. Students who are willing to present the solution receive extra credit.

9.1 Integer Programming Problem

(HOMEWORK)

Course book Exercise 11.1 (a),(b) and (d)

Consider the problem max x1 + 2x2

s.t.

−3x1 + 4x2 ≤ 4

3x1 + 2x2 ≤ 11

2x1 − x2 ≤ 5 x1 , x2 ≥ 0 x1 , x2 integer

Use a figure to answer the following questions.

(a) What is the optimal cost of the linear programming (LP) relaxation? What is the optimal cost of the integer programming problem?

(b) What is the convex hull of the feasible set of the integer programming problem?

(d) Solve the problem by Branch & Bound. Use the LP relaxation for bounding, and solve the relaxations graphically.

Solution

Homework

9.2 Gomory Cut

(BLACKBOARD ASSIGNMENT)

(a) The Gomory cutting plane algorithm uses cuts of the form aij xj ≤ ¯bi ,

xB(i) +

(1)

j∈N

where aij = (B−1 Aj )i (i-th component of column B−1 Aj ), ¯bi = (B−1 b)i , i is the index of the i:th row of the optimal tableau corresponding to a basic variable xB(i) , N the indices of non-basic variables, and B the optimal basis for the standard form problem

min cT x

s.t

Ax = b x ≥ 0.

Show that if ¯bi is fractional, then the current optimal solution to the LP relaxation does not satisfy the constraint (1).

1

Mat-2.3140 Linear Programming

Exercise 9

Thu 09.10.2014

Y346

(b) Consider the problem max x1 + 2x2

s.t.

−3x1 + 4x2 + x3 = 4

3x1 + 2x2 + x4 = 11

2x1 − x2 + x5 = 5 x1 , x2 , x3 , x4 , x5 ≥ 0 x1 , x2 , x3 , x4 , x5 integer

and the optimal tableau for its LP-relaxation.

7

7/2

5/2

2

x1

0

0

0

1

x2

0

0

1

0

x3

2/9

7/18

1/6

-1/9

x4

5/9

-5/18

1/6

2/9

x5

0

1

0

0

Derive a Gomory cut from the optimal tableau.

Solution

(a) In the current optimal solution, the non-basic variables with indices j ∈ N are zero, and xB(i) =

(B−1 b)i = ¯bi , which yields xB(i) + aij xj = ¯bi . j∈N On the other hand, the cut (1) imposes xB(i) ≤ ¯bi < ¯bi (since ¯bi is fractional), wherefore the current optimal solution does not satisfy this constraint.

(b) The optimal solution is fractional, since x2 = 5/2 and x3 = 7/2. From the second row of the optimal tableau, we get

1

1

5

x2 + x3 + x4 =

6

6

2

and the corresponding Gomory cut is of the form x2 +

1

5

1 x3 + x4 ≤

6

6

2

(2)

After rounding, the final cut (2) is of the form x2 ≤ 2.

9.3 The Caterer Problem

Course book Exercise 7.1

A catering company must provide a client ri tablecloths on each N consecutive days. The catering company can buy new tablecloths at a price of p dollars each, or launder the used ones. Laundering can be done at a fast service facility that makes the tablecloths unavailable for the next n days and costs f dollars per tablecloth, or at a slower facility that makes tablecloths unavailable for the next m days

(with m > n) at a cost of g dollars per tablecloth (g < f ). The caterer’s problem is to decide how to meet the client’s demand at minimum cost, starting with no tablecloths and under the assumption that any leftover tablecloths have no value.

2

Mat-2.3140 Linear Programming

Exercise 9

Thu 09.10.2014

Y346

(a) Show that the problem can be formulated as a network flow problem. Hint: Use a node representing clean tablecloths and a node representing dirty tablecloths for each day; more nodes may also be needed. (b) Show explicitly the form of the network if N = 5, n = 1, m = 3.

Solution

(a) We model the problem on a network with 2N + 1 nodes as follows. There is a supply node s. For each day i = 1, . . . , N , there is a node Ci representing clean tablecloths and a node Di representing dirty tablecloths. For each i we introduce an arc (s, Ci ): the flow on this arc is the number of tablecloths purchased for use on day i with a unit cost p.

For every i, there is an arc (Ci , Di ) with flow ri