MATP6620/DSES6760
Combinatorial Optimization & Integer Programming

Homework 3.

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

1. Consider the constraints
   
   $$\begin{array}{rcl} t_1 & \geq & \vert x_1 - x_2 \vert \\ ... ..._2 && \mbox{integer} \\ x_1,x_2&& \mbox{binary} \end{array}$$
   
   
   1. By considering the different possibilities for $x$, show that $t_1+t_2 \geq 1$.
   2. The constraints can be modeled equivalently as
      
      $$\begin{array}{rcrcrcc} t_1 & \geq & x_1 & - & x_2 \\ t_1... ... \\ x_1,x_2&& \multicolumn{5}{l}{\mbox{binary}} \end{array}$$
      
      
      Show that the valid constraint $t_1+t_2 \geq 1$ has Chvatal rank equal to 2.

2. The optimal tableau to the linear programming relaxation of the integer program
   
   $$\begin{array}{lrcrcl} \min & -10x_1 & - & x_2 \\ \mbox{s.t.... ...mn{4}{r}{x_1, \, x_2} & \geq & 0, \, \mbox{integer} \end{array}$$
   
   
   is
   
   $$\begin{array}{lrrcrcrcl} \min & \multicolumn{2}{l}{-18} & + ... ...olumn{7}{r}{x_1, \, x_2, \, x_3, \, x_4} & \geq & 0 \end{array}$$
   
   
   where $x_3$ and $x_4$ are the slack variables in the two constraints. Find the Gomory and strong Gomory cutting planes implied by the two constraints. Express these constraints in terms of the original variables $x_1$ and $x_2$ and draw them on a graph of the feasible region.

3. The AMPL model of the LP relaxation of a random weighted node packing problem with 15 nodes is contained in the file
       http://www.rpi.edu/~mitchj/matp6620/hw3/nodepack.mod

   The initial model contains only the adjacency constraint that just one endpoint of an edge can appear in the node packing. Pick a seed and then solve the problem using a cutting plane algorithm:

   • Solve the LP relaxation
   • If necessary, add one or more valid inequalities. These inequalities can be clique inequalities or odd hole inequalities or lifted odd hole inequalities.
   (It is highly likely that you will need to use both clique inequalities and odd hole inequalities, and that you will not need to use lifted odd hole inequalities.)

4. A particular graph $G=(V,E)$ consists of six vertices. Vertices 1-5 form a cycle and vertex 6 is adjacent to three of the other vertices. Any node packing on this graph must satisfy the odd hole inequality
   
   $$\sum_{i=1}^5 x_i \leq 2.$$
   
   
   How does the structure of the edges connecting vertex 6 to the rest of the graph affect the lifted odd hole inequality
   
   $$\sum_{i=1}^5 x_i \, + \, \alpha x_6 \, \leq 2?$$
   
   

	John Mitchell
	Amos Eaton 325
	x6915.
	mitchj at rpi dot edu
	Office hours: Tuesday Feb 17, 1-3pm, or by appointment.
	We will have class on Tuesday and Thursday next week.