Integer Programming & Combinatorial Optimization Solutions to Problem Set 5 1. BW 7.6 (a) From (7.5), we deﬁne the problem P(y, b1 ) without any loss of generality: min y = c� x � s.t. a1 x − b1 = 0 a�i x = bi i = 2, . . . , m x2j = xj j = 1, . . . , n. where we want to ﬁnd the optimal function value y as a function of the right hand side coeﬃcient b1 . We can solve this optimization problem as follows: • Deﬁne x, y and b1 as decision variable. • Use the lex order x1 > · · · > xn > y > b1 Using the above approach, and following from the fact that the underlying term order is an elimination order, we can partition polynomials in G into set S1 , . . . , Sn+2 where Sn+2 and Sn+1 respectively contain polynomials in b1 only, and in b1 and y only. Together, Sn+2 and Sn+1 deﬁne the feasible range of b1 and the optimal function value y as a function of b1 . (b) Deﬁne ideal J = � 2x1 +2x2 +4x3 −b, x1 +2x2 +3x3 −y, x21 −x1 , x22 −x2 , x23 −x3 , (b−4).(b−5).(b−6) � From part (a), we use lex order: x1 > x2 > x3 > y > b, and using Maple, we obtain the Grobner basis, G = { − 10b + b2 + 24, yb − 6y − 3b + 18, y 2 − 9y + b + 14, x3 b − 4x3 − b + 4, x3 y − 3x3 − y + 3, x23 − x3 , 2x2 + 2x3 − 2y + b, x1 + x3 + y − b } Therefore, we can obtain the following solutions: b 4 6 y 3 4 x (0, 0, 1) or (1, 1, 0) (1, 0, 1) 2. BW 7.7 It is easy to argue that xi = x1 , ∀i odd, xi = x2 , ∀i even. The output when Algorithm 7.2 is applied is equivalent to the output when Algorithm 7.2 is applied to the following problem: x1 + x2 = 1 x21 = x1 x22 = x2 1 with xi = x1 , ∀i odd, xi = x2 , ∀i even. G = { x22 − x2 , x1 + x2 − 1 } is a Grobner basis of this problem since x21 − x1 = (x1 − x2 ) · (x1 + x2 − 1) − (x22 − x2 ). Part 2 of the algorithm gives us xi = x1 , ∀i odd 0 1 xi = x2 , ∀i even 1 0 3. BW 7.10 Proposition 1 f (x, y, z) is nonnegative. Proof : For positive arguments, where A and G are the arithmetic and the geometric mean respec tively, A ≥ G. Since x4 y 2 , x2 y 4 , z 6 ≥ 0, � 1 4 2 (x y + x2 y 4 + z 6 ) ≥ 3 x4 y 2 · x2 y 4 · z 6 , 3 x4 y 2 + x2 y 4 + z 6 ≥ 3x2 y 2 z 2 f (x, y, z) = x4 y 2 + x2 y 4 + z 6 − 3x2 y 2 z 2 ≥ 0 Proposition 2 f (x, y, z) cannot be expressed as a sum of squares of polynomials. Proof : By Proposition 4, a proof that f (x, y, z) �= v d (x, y, z)� Qv d (x, y, z) where Q � 0 is suﬃcient. Let Qij be the entry in row i and column j of Q. For Q � 0, if Qii = 0 for some i, Qij = Qji = 0, ∀j. Therefore, we just need to consider ⎞ x2 y ⎜ xy 2 ⎟ ⎟ v d (x, y, z) = ⎜ ⎝ z3 ⎠ xyz ⎛ Since f (x, y, z) is uniquely ⎛ 1 ⎜ �⎜ 0 v d (x, y, z) ⎝ 0 0 0 1 0 0 and Q �� 0, we are done. 2 ⎞ 0 0 0 0 ⎟ ⎟ v (x, y, z) 1 0 ⎠ d 0 −3 4. BW 7.12 � m x = m∈S ∞ � a−1 � xλ1 a+λ2 b since a ≥ 1 λ1 =0 λ2 =0 a−1 ∞ � � xλ1 a xλ2 b λ1 =0 λ2 =0 ⎛ ⎞ ∞ a−1 � � = xλ1 a · ⎝ xλ2 b ⎠ = = λ1 =0 ∞ � xλ1 a · λ1 =0 = = λ2 =0 − xab 1 1 − xb 1 1 − xab · 1 − xa 1 − xb 1 − xab (1 − xa )(1 − xb ) since |x| < 1 since |x| < 1 5. Multiattribute Knapsack (a) The 1 attribute problem (without cuts) i. Study the provided matlab code knapsack.m. Execute knapsack.m to generate the 1attribute data ﬁle knapsack.dat . ii. Formulate knapsack.mod and solve the 1attribute instance without the MIP cover cuts. Note that this is diﬀerent from the ﬂow covers cut. You should include the instruction setting covers = 1; in your model ﬁle. Ensure that the log ﬁle is printed as well. You may want to take a look at the provided ﬁle knapsackN.mod. iii. How long does it take to solve the problem? How many nodes were evaluated? Time taken = 0.36s 3967 nodes were evaluated. iv. Is the problem solved to optimality or did we terminate because the gap tolerance limit was met? The gap tolerance limit is at the default level. What is the default level? (You can ﬁnd this information by going to help > contents > Studio User’s Manual > OPL Parameters and look for the parameter epGap) Explain in your own words what this value means, and what is its impact on solving a MIP with CPLEX? In particular, if the value is reduced, does it take longer or shorter to solve a problem? If so, why can we not just choose a large value like epGap = 0.3? What %gap does epGap = 0.3 translate to? The problem is solved to optimality. The gap used in 1e04, or 0.01%. The gap integer solution| is calculated by | |best bound−best |. When the gap is less than the value best integer solution set, CPLEX would terminate giving the best integer solution attained (value and variables) as the solution. Decreasing it increases the time. Increasing the gap un necessarily may degrade the quality of the solution attained. egGap = 0.3 translates to a 30% gap. 3 v. Looking at the CPLEX log ﬁle, what is the meaning of ’infeasible’ ? During branch & bound, some of the subproblems encountered are infeasible. (b) The 2 attributes problem i. Study the formulation ﬁle knapsackN.mod that reads a Nattribute dataﬁle to solve a Nattribute instance. Note that N is deﬁned as NbAttribute, N > 1 and it is to be read from the appropriate dataﬁle. ii. Modify exp2.m so that it can generate a Nattributes problem that can be read from knapsackN.mod. Note that you should be using the expressions attribute = [ [ w11 w12 · · · ] [ w21 w22 · · · ] .. . ] [ .. . [ wN 1 wN 2 · · · ] ]; in specifying the constraints parameters wi j in the dataﬁle. iii. Generate 5 instances of the 2 attributes problem. Still with the cuts generation disabled, solve them. What can you observe regarding the runtime taken to solve these 5 instances? Is the longest time taken a large multiple of the shortest time? As the number of attributes increases, do you think the solution times would be predictable? The solution times range from 1.3s to 0.89s. They are not predictable. iv. In all the instances, is the problem solved to optimality or did we terminate because the terminating tolerance was met? In all instances, the problem is solved to optimality. (c) The 4 attributes problem i. Generate and try solving a 4 attributes instance, still with cuts generation disabled. What is the gap achieved after a 2 minute solution time? (You can terminate by choosing abort) Note: If you can solve this instance to optimality (there is a tiny probability that the instance generated is easy), generate another instance. 10.34%. ii. At the end of 2 minutes, are we on the way to solving the problem (converging) or is the branch & bound tree still growing (diverging)? (i.e. is the number of nodes left in the branch & bound tree increasing or decreasing?) Can you estimate how much longer it will take to termination? 4 Diverging. The tree is still growing. We cannot estimate it. iii. During the CPLEX runs, how many improving (improving on previous solutions) integral solutions were found? What is preventing the termination? Only 1 solution was found. We cannot ﬁnd a better bound to close the gap be low the required termination gap of 0.01%. iv. Without generating cuts, what can you do if you must make a choice? How good a solution can you guarantee? We can let it run longer but there is not guarantee of termination. We may have to live with the solution obtained, guaranteeing a gap of 10.34%. (d) The 4 attributes problem with cuts i. Enable cuts generation by adding the commenting marks. How long does it take to solve the same 4 attribute instance now? How many nodes do we have to evaluate? How many cover cuts were applied? Note that you should solve this instance right from the beginning and NOT continue from the middle of the branch & bound in the previous part. The same problem was solved in 0.01s. Problem was solved in root relaxation and 0 nodes were evaluated. In other words, the relaxed problem was solved to optimality. 1 cover cut was applied. ii. Can you explain why is there a diﬀerence in the performance with and without cuts? Without the cut, we have a large duality gap and consequently, we have to ex haust the branch & bound tree to solve the problem. With the cut, the formulation is good enough for us to ﬁnd the optimal solution at the root node. iii. Compare the objective function obtained with and without cuts. Is the optimal solution obtained when cover cuts were disabled? They are the same. iv. Can you give a possible reason when no cover cuts were used, if we terminate, we did not terminate because the gap tolerance was met? Without the cover cut, the duality gap is most likely greater than 0.01% and there fore we would not be able to ﬁnd a bound that will reduce the gap suﬃciently. 5