Integer Program Combination Optimization - Midterm Solutions

Integer Programming & Combinatorial Optimization Solutions to Midterm Examination 1. Problem 1 ­ BW 1.10 (25 points) A production and distribution problem (a) (6 points) We define the following decision variables: • xijk ∈ R+ , quantity of product k produced at plant i and shipped to market zone j. • yik ∈ {0, 1}, 1 if product k is produced at plant i, 0 otherwise. • zik ∈ R+ , quantity of product k produced at plant i. A possible model is: min I � K � (fik yik + vik zik ) + I � J � K � cijk xijk i=1 j=1 k=1 i=1 k=1 �J − zik ≤ 0, zik − Mik yik ≤ 0, zik − mik yik ≥ 0, K � qik zik ≤ Qi , s.t. j=1 xijk k=1 I � ∀ i, k ∀ i, k ∀ i, k ∀i ∀ j, k xijk = djk , i=1 xijk ≥ 0, yik ∈ {0, 1}, zik ≥ 0. Note that assuming zik = J � ∀ i, j, k ∀ i, k ∀ i, k xijk is wrong. Because of the presence of mik , the optimal j=1 solution may require one to produce more than the demand. (b) (4 points) This can be modelled as follows: K � yik ≤ K1 , ∀i k=1 (c) (4 points) This can be modelled as follows: I � yik ≤ I1 , i=1 1 ∀k (d) (4 points) This can be modelled as follows: y1k0 + y2k0 + y3k0 ≥ 1 (e) (7 points) Define new variables: • uij ∈ {0, 1}, if market j is supplied by plant i, and 0 otherwise. The constraint can be modelled as follows: I � ∀j uij = 1, i=1 xijk ≤ djk uij , ∀ i, j, k 2. Problem 2 (45 points) (a) (5 points) From Eq. (3.16) in BW, and discussions in the class, we know that minimum matching is an optimization problem that is solvable in polynomial time. From the discus­ sion in Section 5.4, a separation problem is solvable in polynomial time if and only if the optimization problem is solvable in polynomial time. True. (b) (5 points) Consider a problem where ZIP = � ZD , and there exists a decision x∗ in X where ∗ ∗ � Ax ≥ b, and ai x > bi , for some i. If we choose a λ that is sufficiently large, x∗ , or another ˆ > bi for some i, will be the optimal solution. False. decision x ˆ where Aˆ x ≥ b, and a�i x (c) (5 points) The statement proves that all the extreme points are integral if we restrict our­ selves to nonnegative vector c. One can easily construct an example with the above property, but has a non­integral extreme point that will be minimize an objective function c with neg­ ative components. False. (d) (5 points) This is true due to Corollary 3.1(b) Note that A has to be an integral matrix if it is totally unimodular due to Definition 3.1(b). True. (e) (5 points) This is clearly not true. Pick any 3 affinely independent vectors in a 2­D space. False. (f) (5 points) Since P is full dimensional in a space with 5 dimensions, dim(P) = 5. Since the inequality defines a face of dimension 4, it is facet defining by Definition A.6. By Theorem A.1(a), one of the inequality defining this facet is necessary in the description of P. Since we do not know of any other inequalities in Ax ≥ b defining the same facet, we cannot assume that this can be deleted. False. (g) (5 points) Consider n � min yj j=1 s.t. ∀j yj ≥ M̂ xj , yj ≥ M̌ (1 − xj ), ∀ j Ax = b x ∈ 0, 1n 2 ˆ = f (1), M ˇ = f (0). True. where M (h) (5 points) A valid inequality with a F = ∅ cannot be lifted to be facet defining. Note that the validity of the statement is independent of the number of lifting to be carried out. False. (i) (5 points) Consider P = {x ∈ Rn+ | Dx ≥ d, Ax ≥ b}, x = 0 is a feasible extreme point and P is not integral. Consider a minimization problem with c > 0 and Ax ≥ b being redundant constraints with respect to this set of objective functions. False. 3. Problem 3 ­ BW 2.12 (30 points) (a) (10 points) Let J ∈ I and I ⊆ J. Then |I ∩ N i | ≤ |J ∩ N i | ≤ q − 1 for all i = 0, . . . , n − 1 and hence, I ∈ I. Consequently, ∅ ∈ I as well. Thus, I is an independence system. (b) (10 points) The set C of all circuits of (N, A(n, t, q)) is equal to C := {C ⊆ N : |C | = q, C ⊆ N j for some j ∈ {0, . . . , n − 1}}. � (c) (10 points) By summing all constraints i∈N j xi ≤ q − 1 for j = 0, . . . , n − 1, we obtain � that i∈N txi ≤ n(q − 1). By rounding we obtain that the inequality � � � n(q − 1) xi ≤ t i∈N is valid for PI . 3