A sample input file is contained in
fort.17;
this produces the output contained in
in40a.
The output produced by my cutting plane code for this problem
is contained in out40a.
In general, an input file must be placed in `fort.17`,
and the generated problem will be sent to the standard output.

The code generates some *observations*, each with various
*characteristics*.
The input file `fort.17` contains these two parameters
and also a parameter for a random seed.
The first three rows of output returns the value of these three
parameters.
The remaining rows contain the observations and their characteristics.
Each characteristic can take the value 0, 1, or 2.
It is desired to identify observations that are similar to one another.

The method we use to formulate this problem as an integer programming problem is due to Grotschel and Wakabayashi:

AUTHOR = {M. Gr{\"{o}}tschel and Y. Wakabayashi}, TITLE = {A cutting plane algorithm for a clustering problem}, JOURNAL = {Mathematical Programming}, YEAR = 1989, VOLUME = 45, PAGES = {59--96}The observations can be regarded as vertices of a graph. The length of the edge connecting two graphs is given by

We then wish to choose a subset of the edges such that:

- The cost of the chosen edges is as small as possible.
- The chosen edges correspond to the edges of cliques,
that is, if edges
`(i,j)`and`(j,k)`are chosen then edge`(i,k)`must also be chosen.

Seeds and optimal values for selected problems are available:

A paper describing the problem in more detail and giving computational results is "Computational experience with an interior point cutting plane algorithm."

Back to my homepage.