MATP6620/DSES6760 Combinatorial Optimization & Integer Programming
Homework 2.

Due: Thursday, February 5, 2009.
Penalty for late homeworks: 10% for each day or part of a day.

1. In an uncapacitated facility location problem, the constraint that material can only be shipped from an open facility can be modeled using either aggregated or disaggregated constraints. AMPL model files for these two alternatives can be found at

   http://www.rpi.edu/~mitchj/matp6620/hw2/uflRagg.mod
   http://www.rpi.edu/~mitchj/matp6620/hw2/uflRdisagg.mod

   Generate a problem instance with $m\geq 10$ warehouses and $n\geq 40$ customers, changing the seed used in the model from 421415. Use the AMPL command let m := 10; to set $m$ and $n$. Solve your problem with each of the two models. Next, turn off cplex's cut generation subroutines using the command:

   option cplex_options 'mipcuts=-1';
   

   and solve your problem again with the two models. What do you conclude? (Include your values of $m$, $n$, and randseed in the solution you hand in.)

2. Assume that we have a polynomial time algorithm for computing the length of the shortest TSP tour, so given any graph $G=(V,E)$ with edge lengths $c_e$, this algorithm will tell us the length of the optimal tour, but it will not tell us the edges that are used in the optimal tour. Prove that we can use this algorithm as a subroutine in a polynomial time algorithm for finding the edges in the shortest TSP tour.
3. Show that the following problem is ${\cal N}{\cal P}$-complete.

   Matching with bonds: Given a graph $G=(V,E)$, pairwise disjoint subsets $B_i$ for $i=1,\ldots,p$ of $E$, and an integer $K$, does there exist a matching $M$ in $G$ with $\vert M\vert \geq K$ and, for $i=1,\ldots,p$, either $B_i\cap M=B_i$ or $B_i\cap M=\emptyset$ (i.e., either all edges in $B_i$ are in the matching or none are)? The subsets $B_i$ are called bonds.

4. Consider the optimization problem
   
   $$\begin{array}{lccl} \max & x_{12} \\ \mbox{subject to} &... ...] & \mbox{is} & \mbox{positive semidefinite} \\ \end{array}$$
   
   
   Show that the optimal value is irrational. Can this problem be solved in polynomial time?

	John Mitchell
	Amos Eaton 325
	x6915.
	mitchj at rpi dot edu
	Office hours: Monday 1-3pm, or by appointment.