15h30 - 15h55
A Column Generation Approach to the Capacitated Centered Clustering Problem
We propose a column generation based heuristic to calculate approximate solutions to the capacitated centered clustering problem. The proposed approach uses a stabilization technique derived from the lagrangean/surrogate relaxation of the corresponding capacitated p-median problem. Computational results will be presented to show the effectiveness of the method.
15h55 - 16h20
A Clustering Problem with Capacity and Side Constraints
A set of weighted items must be grouped into stacks, of given height and weight, such that the weight of the items decreases from the bottom to the top. The assignment costs depend on the position items will have within the stacks. An assignment model with side constraints is investigated.
16h20 - 16h45
Clustering Using Several Diameter Criteria
We present a short study on two criteria that may be used to partition a subset of points: the diameter criterion, and the sum of diameter criterion. The diameter of a subset is the maximal distance between two of its points; the former criterion minimize the smallest diameter among resulting subsets, and the later the sum of the subset's diameters. We present a graphical comparison of the results obtained with the two criteria and some of their extensions.
16h45 - 17h10
Exact Normalized Cut Clustering by Column Generation
Clustering addresses the following problem: given a set of entities, find subsets, or clusters, which are homogeneous and/or well separated. Many criteria have been proposed to express homogeneity and/or separation of the clusters. We focus on the normalized cut criterion and present an exact solution method based on the column generation techniques of linear programming applied to a set partitioning formulation of the problem.