CS 573: Algorithms, Fall 2012 Homework 5, due Monday, Nov. 26, 23:59, 2012 Version 0.1 Name: Net ID: Neatly print your name(s), NetID(s). Please...

CS 573: Algorithms, Fall 2012 Homework 5, due Monday, Nov. 26, 23:59:59, 2012 Version 0.1 Name:

Net ID:

Neatly print your name(s), NetID(s). If you are o campus, please submit the homework on moodle, otherwise submit the homework in SC 3306 (or sliding it under the door). Please solve each problem on a separate page.

Long ago in our home, before a fool struck re, we were so - roaming without whatever may be named save the sun, the night, and each other. Now we are so again, for are gods, and things made by hands do not concern us. { The Fifth Head of Cerberus, Gene Wolfe.

Required Problems 1. Tedious Computations [20 Points] Provide detailedsolutions for the following problems, showing each pivoting stage sep- arately.

(A) [5 Points] maximize 6 x 1 + 8 x 2 + 5 x 3 + 9 x 4 subject to 2 x 1 + x 2 + x 3 + 3 x 4 ≤ 5 x 1 + 3 x 2 + x 3 + 2 x 4 ≤ 3 x 1; x 2; x 3; x 4≥ 0.

(B) [5 Points] maximize 2 x 1 + x 2 subject to 2 x 1 + x 2 ≤ 4 2 x 1 + 3 x 2 ≤ 3 4 x 1 + x 2 ≤ 5 x 1 + 5 x 2 ≤ 1 x 1; x 2≥ 0.

1 (D) [5 Points] minimize x 12 + 8 x 13 + 9 x 14 + 2 x 23 + 7 x 24 + 3 x 34 subject to x 12 + x 13 + x 14 ≥ 1 − x 12 + x 23 + x 24 = 0 − x 13 − x 23 + x 34 = 0 x 14 + x 24 + x 34 ≤ 1 x 12 ; x 13; : : : ; x 34≥ 0.

2. Linear Programming for a Graph.

[20 Points] (A) [6 Points] Given a weighted, directed graph G= ( V ; E ), with weight function w :E → R mapping edges to real-valued weights, a source vertex s, and a destination vertex t. Show how to compute the value d[t ], which is the weight of a shortest path from sto t, by linear programming.

(B) [6 Points] Given a graph Gas in (a), write a linear program to compute d[v ], which is the shortest-path weight from sto v, for each vertex v∈ V.

(C) [8 Points] In theminimum-cost multicommodity- ow problem , we are given a directed graph G= ( V ; E ), in which each edge ( u; v)∈ E has a nonnegative capacity c(u; v )≥ 0 and a cost (u; v ). As in the multicommodity- ow problem, we are given kdi erent commodities, K 1, K 2, . . . , K k, where commodity iis speci ed by the triple K i= ( s i; t i; d i). Here s i is the source of commodity i, t i is the sink of commodity i, and d i is the demand, which is the desired ow value for commodity ifrom s i to t i. We de ne a ow for commodity i, denoted by f i, (so that f i( u; v ) is the ow of commodity ifrom vertex uto vertex v) to be a real- valued function that satis es the ow-conservation, skew-symmetry, and capacity constraints. We now de ne f(u; v ) , the aggregate ow , to be sum of the various commodity ows, so that f(u; v ) = ∑ k i =1 f i( u; v ). The aggregate ow on edge ( u; v) must be no more than the capacity of edge ( u; v).

The cost of a ow is ∑ u;v ∈V f (u; v ), and the goal is to nd the feasible ow of minimum cost. Express this problem as a linear program.

3. Linear programming [40 Points] (A) [10 Points] LetLbe a linear program given in slack form, with nnonbasic variables N, and mbasic variables B. Let N′ and B′ be a di erent partition of N ∪B, such that |N ′ ∪ B′ | = |N ∪B|. Show a polynomial time algorithm that computes an equivalent slack form that has N′ as the nonbasic variables and b′ as the basic variables. How fast is your algorithm?

(B) [10 Points] Show the following problem in NP-hard.

2 Integer Linear Programming Instance : A linear program in standard form, in which Aand Bcontain only integers.

Question:

Is there a solution for the linear program, in which the xmust take integer values?

(C) [5 Points] A steel company must decide how to allocate next week's time on a rolling mill, which is a machine that takes un nished slabs of steel as input and produce either of two semi- nished products: bands and coils. The mill's two products come o the rolling line at di erent rates:

Bands 200 tons/hrCoils 140 tons/hr.

They also produce di erent pro ts:

Bands $ 25/tonCoils $ 30/ton.

Based on current booked orders, the following upper bounds are placed on the amount of each product to produce:

Bands 6000 tonsCoils 4000 tons.

Given that there are 40 hours of production time available this week, the problem is to decide how many tons of bands and how many tons of coils should be produced to yield the greatest pro t. Formulate this problem as a linear programming problem. Can you solve this problem by inspection?

(D) [5 Points] A small airline, Ivy Air, ies between three cities: Ithaca (a small town in upstate New York), Newark (an eyesore in beautiful New Jersey), and Boston (a yuppie town in Massachusetts). They o er several ights but, for this problem, let us focus on the Friday afternoon ight that departs from Ithaca, stops in Newark, and continues to Boston. There are three types of passengers:

i. Those traveling from Ithaca to Newark (god only knows why).

ii. Those traveling from Newark to Boston (a very good idea).

iii. Those traveling from Ithaca to Boston (it depends on who you know).

The aircraft is a small commuter plane that seats 30 passengers. The airline o ers three fare classes:

i. Y class: full coach.

ii. B class: nonrefundable.

iii. M class: nonrefundable, 3-week advanced purchase.

Ticket prices, which are largely determined by external in uences (i.e., competi- tors), have been set and advertised as follows:

Ithaca-Newark Newark-Boston Ithaca-Boston Y 300160360 B 220130280 M 10080140 Based on past experience, demand forecasters at Ivy Air have determined the 3 following upper bounds on the number of potential customers in each of the 9 possible origin-destination/fare-class combinations:

Ithaca-Newark Newark-Boston Ithaca-Boston Y 483 B 81310 M 222018 The goal is to decide how many tickets from each of the 9 origin/destination/fare- class combinations to sell. The constraints are that the place cannot be overbooked on either the two legs of the ight and that the number of tickets made available cannot exceed the forecasted maximum demand. The objective is to maximize the revenue. Formulate this problem as a linear programming problem.

(E) Distinguishing between probabilities [10 Points] Suppose that Yis a random variable taking on one of the nknow values:

a1; a 2; : : : ; a n.

Suppose we know that Yeither has distribution pgiven by P(Y =a j) = p j or it has distribution qgiven by P(Y =a j) = q j.

Of course, the numbers p j; j = 1 ;2 ; : : : ; n are nonnegative and sum to one. The same is true for the q j's. Based on a single observation of Y, we wish to guess whether it has distribution por distribution q. That is, for each possible outcome a j, we will assert with probability x j that the distribution is pand with probability 1 − x j that the distribution is q. We wish to determine the probabilities x j; j = 1 ;2 ; : : : ; n , such that the probability of saying the distribution is pwhen in fact it is qhas probability no larger than , where is some small positive value (such as 0.05). Furthermore, given this constraint, we wish to maximize the probability that we say the distribution is pwhen in fact it is p. Formulate this maximization problem as a linear programming problem.

4. Strong duality.

[20 Points] Consider a directed graph Gwith source vertex sand target vertex tand associated costs cost( ·) ≥ 0 on the edges. Let Pdenote the set of all the directed (simple) paths from sto tin G.

Consider the following (very large) integer program:

minimize∑ e ∈ E (G )cost( e) x e subject to x e ∈ { 0;1 } ∀ e∈ E(G ) ∑ e ∈ x e ≥ 1 ∀ ∈ P:

(A) [5 Points] What does this IP computes?

(B) [5 Points] Write down the relaxation of this IP into a linear program.

4 (C) [5 Points] Write down the dual of the LP from (B). What is the interpretation of this new LP? What is it computing for the graph G(prove your answer)?

(D) [5 Points] The strong duality theorem states the following.

Theorem 0.1 If the primal LP problem has an optimal solution x ∗ = ( x∗ 1 ; : : : ; x ∗ n ) then the dual also has an optimal solution, y∗ = ( y ∗ 1 ; : : : ; y ∗ m ) , such that ∑ j c jx ∗ j = ∑ i b iy ∗ i :

In the context of (A)-(C) what result is implied by this theorem if we apply it to the primal LP and its dual above? (For this, you can assume that the optimal solution to the LP of (B) is integral { which is not quite true { things are slightly more complicated than that.) 5