MATP6620/ISYE6770
Combinatorial Optimization and Integer Programming
Spring 2017
Midterm Exam, Friday, March 31, 2017.
Please do all four problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.
Model this as a 0-1 integer programming feasibility problem.
Solution:
The model is
For the final constraint for condition (e), we need
or equivalently, we need
The corresponding disjunctive cut is
from taking the larger coefficient for each x_{i}. We can confirm the constraint is equivalent to the required logical condition by examining cases.
An alternative approach for constraint (e): this is the more standard approach, and doesn’t need to exploit the disjunctive cut structure. We introduce a new binary variable z_{e} and impose two constraints:
Assume that at most one item can be selected from each subset of size k. Show that the constraint
has Chvatal rank at most one.
Show that the clique constraint
has Chvatal rank at most 4.
Solution:
Adding the inequalities, we get
where the term on the right hand side is the number of subsets of cardinality k and the term on the left is the number containing any particular x_{i}. Dividing by the term on the left and rounding, we get
An alternative approach, which uses only a linear number of subsets:
Consider the following 2k - 1 subsets of the items, each of cardinality k:
Dividing by k and rounding down gives the valid inequality
so the required inequality indeed has Chvatal rank no larger than one.
has an LP relaxation which has optimal form
with optimal basic feasible solution x = (0, 5.2, 0, 2.6) with value 7.2.
Solution:
If x_{3} ≥ 5 then the objective function value is at least 10.7. So we must have x_{3} ≤ 4 in any optimal solution.
Solution
The solution uses 10 edges and has at least one edge incident to each vertex.
There is a better feasible solution to the relaxation: replace edges (d,h) and (d,j) by edges (g,p) and (h,j), which has value 35.