Integer Programming & Combinatorial Optimization Solutions to Problem Set 3 1. BW 4.9 Comparison of relaxations for an assignment problem with a side con straint If we relax the third constraint, the remaining constraints deﬁne an integral polyhedron. Sim ilarly, if we relax the third constraint and the ﬁrst set of constraints, the remaining constraints form an integral polyhedron. Hence Z = ZD1 = ZD4 . Let X 3 be the polyhedron deﬁned when only the ﬁrst set of constraints are relaxed, and X 2 be the one deﬁned when the ﬁrst and the second set of constraints are relaxed. Since X 3 ⊆ X 2 , Z ≤ ZD2 ≤ ZD3 ≤ ZIP . 2. BW 4.10 Let P denote the convex hull of the vectors of start times t = (t1 , . . . , tn ) under all possible sequence ordering of jobs and r be the vector of release times. Then, a lower bound for the problem with release times is given by the optimal value of the linear program � wj tj Zlo = min j s.t. tj ≥ rj t ∈ P. j = 1, . . . , n Dualizing the constraints tj ≥ rj , we obtain the Lagrangian dual � � (wj − λj )tj + λ j rj ZLD (λ) = min j s.t. j t ∈ P, whose optimal value ZLD (λ) is a lower bound for Zlo , for any λ ≥ 0. Furthermore, this Lagrangian dual can be solved by Smith’s rule. The best lower bound in this family is Zlo = max ZLD (λ). λ≥0 3. BW 4.11 Lagrangean decomposition Apply Theorem 4.9, the value ZLD of the Lagrangean dual produced by the decomposition method is given by minimize c� x subject to x − y = o (x, y) ∈ conv(X) × conv(Y ). 1 This yields minimize c� x subject to (x, x) ∈ conv(X) × conv(Y ). Since (x, x) ∈ conv(X) × conv(Y ) is equivalent to x ∈ conv(X) ∩ conv(Y ), the result follows. 4. BW 5.8 (a) Given a vector x, we want to check if � xe ≥ max re ∀S ⊂ V, S �= ∅, V e∈δ(S) e∈δ(S) or � xe ≥ rf ∀f ∈ δ(S), ∀S ⊂ V, S �= ∅, V e∈δ(S) Therefore, min S:f ∈δ(S) � xe ≥ rf ∀f ∈ E e∈δ(S) The above condition can be checked as follows: Construct a graph G� = (N , E) with edge capacities xe . For every pair i, j ∈ N (since G is fully connected) solve the minimum cut problem. If for any pair i, j the minimum cut has value less that rij a violated inequality has been identiﬁed; else, x is feasible. (b) This problem is a special case of part (a), where rij = 1 if both i, j ∈ T and zero other wise. With this deﬁnition, Case S ∩ T = ∅: maxe∈δ(S) re = 0 ⇒ f (S) = 0 as required. Case S ∩ T = T : maxe∈δ(S) re = 0 ⇒ f (S) = 0 as required. Case S ∩ T �= ∅, T : maxe∈δ(S) re = 1 ⇒ f (S) = 1 as required. 2