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 |

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

- Show that the constraints

imply . - Given (1)-(4), what is the Chvatal rank of the valid
inequality ?
(this page intentionally left blank)

- 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.

- 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.
(this page intentionally left blank)

- 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?
- 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?
(this page intentionally left blank)

- 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.)

(this page intentionally left blank)

- Show that the following matrix is not totally unimodular:
- (28 points)

Consider the following nonlinear integer programming problem:

- (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. - (8 points) Solve the problem.

(intentionally left blank)

- (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
- (16 points)

Let and .- (6 points) Give an inequality description of the convex hull of .
- (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 .

(this page deliberately left blank)

John Mitchell

2009-03-05