MATP6620 / DSES6760 Combinatorial Optimization and Integer Programming
Homework 4.

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

Given the complete graph $K_n=:(V,E)$ on $n$ vertices, a clustering of the vertices is obtained by choosing an integer $p$ and a partition of the vertices into $p$ sets $V_1,\ldots,V_p$ satisfying:

$V_s \cap V_t = \emptyset$ for $1\leq s < t \leq p$         and          $\cup_{s=1}^p V_s=V$.
Note that $p$ is not fixed. The incidence vector of this clustering is defined by

\begin{displaymath} x_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{if $i$\ and $j... ... same set $V_s$} \\ 0 & \mbox{otherwise.} \end{array} \right. \end{displaymath}

Let $Q$ be the set of incidence vectors of clusterings for $K_n$. Let edge $(i,j)$ have weight $w_{ij}$. The clustering problem for this set of edge weights is then

\begin{displaymath} \begin{array}{ll} \max & z:=\sum_{i=1}^{n-1} \sum_{j=i+1}^n... ...{ is the incidence vector of a} \mbox{ clustering} \end{array}\end{displaymath}

The edge weights $w_{ij}$ can be positive or negative. This problem is the subject of questions 2-4.

  1. Let $x^1,\ldots,x^k$ be points in $\Re^n$.
    1. Prove that if the points are linearly independent then they are affinely independent.
    2. Assume all $k$ points satisfy the equality $a^Tx=b$, where $a \in \Re^n$ and $b>0$. Prove that if the points are affinely independent then they are linearly independent.

  2. Show that the inequality
    \begin{displaymath} x_{ij} + x_{jk} - x_{ik} \leq 1, \;\; 1 \leq i<j<k \leq n \end{displaymath} (1)

    defines a facet of the convex hull of $Q$. (You may assume that the dimension of $Q$ is $n(n-1)/2$, that is, $Q$ is full dimensional.)
  3. Choose a seed and solve the clustering problem in
    http://www.rpi.edu/~mitchj/matp6620/hw4/clr1.mod
    using a cutting plane algorithm, adding violated triangle inequalities of the form (1) and
    $\displaystyle x_{ij} - x_{jk} + x_{ik} \leq 1,$   $\displaystyle 1 \leq i<j<k \leq n$ (2)
    $\displaystyle - x_{ij} + x_{jk} + x_{ik} \leq 1,$   $\displaystyle 1 \leq i<j<k \leq n$ (3)

  4. Another random clustering problem is in
    http://www.rpi.edu/~mitchj/matp6620/hw4/clr2.mod
    with all the triangle inequalities (1-3) included. For this problem, the triangle inequalities are not sufficient. Find a valid inequality for the clustering problem that is violated by the optimal solution to the LP relaxation with all the triangle inequalities included.

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


John Mitchell
2009-02-22