Name:

Final Exam, Tuesday, May 8, 2007.

Please do all three 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 three hours.

 Q1 /56 Q2 /28 Q3 /16 Total /100

1. (56 points; each part is worth 7 points)
1. Show that the following matrix is not totally unimodular:

2. Show that the constraints
 (1) (2) (3) (4)

imply .
3. Given (1)-(4), what is the Chvatal rank of the valid inequality ?

4. The directed graph is as follows:

One unit of commodity A must be shipped from to and one unit of commodity B must be shipped from to . The flows must be integral. The cost of shipping one unit of flow along an arc is indicated in the figure. The cost is the same for each commodity. Each arc in the graph has capacity equal to one; this is the maximum total flow along the arc for the combination of the two commodities. Using the earlier parts of this question, show that the optimal integral multicommodity flow has value equal to 27.

5. Show that the optimal solution to the linear programming relaxation of the multicommodity flow problem in part 1d does not give the optimal solution to the integral multicommodity flow problem.

6. A Lagrangian relaxation for the integer multicommodity flow problem in part 1d could be constructed by placing the upper bound constraints on the arcs in the objective function. If the Lagrangian multipliers are set equal to zero, what is the value of the Lagrangian relaxation?

7. How does the optimal value of the Lagrangian dual problem compare with the value of the LP relaxation of the integer multicommodity flow problem in part 1d?

8. A version of the integer multicommodity flow with lower bound feasibility problem can be stated
Given a directed graph , commodities each with a single origin and destination and with available supply , upper bounds for the total flow on arc , and a positive number , does there exist an integer multicommodity flow of size at least ?
Show this problem is NP-Complete, using the Node Packing with lower bound feasibility problem or otherwise. (The node packing with lower bound feasibility problem can be stated:
Given a graph and a positive integer , find a node packing of cardinality at least .
You can assume this problem is NP-Complete.)

2. (28 points)
Consider the following nonlinear integer programming problem:

1. (20 points) The nonlinear terms can be replaced by binary variables, for example we can use instead of in the first constraint. By introducing extra binary variables, model this problem as an equivalent integer linear program. Try to make the LP relaxation strong, but do not eliminate or fix any of the variables . Argue why your formulation is equivalent to the original problem.
2. (8 points) Solve the problem.

(intentionally left blank)

3. (16 points)
Let and .
1. (6 points) Give an inequality description of the convex hull of .
2. (10 points) For any two scalars and , the set can be written:

Show that there is only one choice of for which the lifted version of the constraint defines a facet of .