Integer Program Combination Optimization Midterm

Integer Program Combination Optimization Midterm 1. This is an 1.5 hour exam. 2. You are required to submit both the questions and your answers. 3. You can use the textbook for the class, the notes from the lectures, your homeworks and homeworks solutions. 4. Good luck! Problem 1 (25 points) A company produces a set of K products at I plants. It then ships these products to J market zones. For k = 1 : : : K , i = 1 : : : I , and j = 1 : : : J , the following data are given: vik = variable cost of producing one unit of product k at plant i cijk fik Mik mik = cost of shipping one unit of product k from plant i to zone j = xed cost associated with producing product k at plant i = maximal quantity of product k produced at plant i = minimal quantity of product k that can be produced at plant i if plant i produces a nonzero quantity qik = capacity of plant i used to produce one unit of product k Qi = capacity of plant i djk = demand for product k at market zone j (a) Formulate the problem of minimizing the total cost of production and transportation that the company is facing, as an integer optimization problem. Indicate how your model can incorporate the following additional constraints. (b) (c) (d) (e) No plant may produce more than K1 products. Every product can be produced in at most I1 plants. For a particular product k0, plant 3 must produce it if neither plant 1 nor plant 2 produce it. Each market zone must be sourced by exactly one plant for all products. 1 Problem 2 (45 points) Please answer true or false in the following questions and brie y justify your answer: (a) The separation problem for the minimum matching problem (see Eq. (3.16) in BW) is solvable in polynomial time. (b) Assume that when solving the problem minimize c x +  (b ; Ax) 0 0 subject to x 2 X there exists a value of the multiplier  for which the optimal solution satis es Ax  b. Then, ZIP = ZD : (c) Suppose that when applying the randomized rounding method, we prove that E ZH] = ZLP for all nonnegative vectors c. This proves that the linear relaxation de nes an integral polyhderon. (d) Consider the polyhedron P = fx 2 Rn j Ax  bg with the matrix A being totally unimodular and b 2 Z m . The polyhdedron P is integral. (e) Three vectors are anely independent. Then they are linearly independent. (f ) Let P = fx 2 R5 j Ax  b f x  dg be a full dimensional polyhderon, in which the inequality f x  d de nes a face of dimension 4. Then the inequality f x  d can be deleted from P . (g) Let f (x) be a nonlinear function. The binary nonlinear optimization problem 0 0 0 minimize n X j =1 f (xj ) subject to Ax = b x 2 f0 1gn can be reformulated as a linear integer optimization problem. (h) When we lift a valid inequality, we always produce a facet. (i) We refer to Eq. (4.27) in BW. Suppose that the polyhderon fx 2 Rn j Dx  dg is not integral. Then, we always have that the value of the Lagrangean dual is strictly larger than the value of the linear relaxation. 2 Problem 3 (30 points) Let n t q 2 Z , n  t  q  2 and N = f0 : : : n ; 1g. For i 2 N we denote by N i = fi i + 1 : : : i + t ; 1g the set of t consecutive elements in N , starting with i. All indices are taken modulo n. Let n o I = I  N j jI \ N j j  q ; 1 for all j = 0 : : : n ; 1 : (a) Show that (N I ) is an independence system. (b) Characterize the set C of circuits of (N I ). (c) Show that the inequality
n ( q ; 1) xi  t N X is valid for P . i 2 I 3