13

You are trying to list all cliques of a graph. You said that $x \in \mathbb{R}^2$, which greatly simplifies the problem: the graph is a unit disk graph, for which the maximum clique problem is polynomial. However, the number of cliques may be exponential. In practice, it is likely easier to apply a heuristic or a generic maximum clique algorithm rather than ...


8

You might find some interesting points in the following two papers C. Walshaw, 2002, A Multilevel Approach to the Travelling Salesman Problem, Operations Research, Vol. 50, nr. 5, pages 862-877. In this paper they present a method which first simplifies the problem by aggregating customers until you have a very simple graph. After the simplification phase, ...


6

You can check the following papers: A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. From the abstract: Phase I aims to identifying a set of cost-effective feasible clusters while Phase II assigns clusters to vehicles and sequences them on each tour by using the cluster-based MILP ...


5

Here is how I would do this: you essentially have a facility location problem, every data point is a potential facility and you decide whether you open it or not (i.e., whether it is the leader of its group). Same goes for the other points, will they be served by the opened facility or not (i.e., will they belong to its group). Standard MILP models don't ...


4

For $i<j$, let $z_{i,j} \ge 0$ indicate whether zones $i$ and $j$ are assigned to the same cluster. You want to minimize $\sum_{i<j} T_{i,j} z_{i,j}$, with additional constraints $$y_{i,c} + y_{j,c} - 1 \le z_{i,j} \quad \text{for $i<j$ and $c\in C$}$$ Note that $z$ will automatically be integer-valued without explicitly declaring it to be binary. ...


3

We (Thibaut Vidal, Daniele Vigo, Michael Schneider, and I) just released a preprint on decomposition methods for Vehicle Routing heuristics. Clustering is one such family of methods and we try different types of clustering in our computational experiments. Indeed, it works very well, as long as: The clusters are based on some existing high-quality solution. ...


3

It depends on what you want to achieve exactly. You could, for example, want to minimize the average distance between a point and the "center" of the cluster. This requires that you first define this center. Assuming it is one of the points, then intoduce a binary variable $y_j$ that takes value $1$ if and only if point $j$ is the center of one of ...


3

This is a tough problem indeed, but I am not sure about the "extremely NP-hard" part :). All problems which are NP-hard are...very hard. This looks like a multi-commodity flow problem, one commodity per depot. It is natural to decompose such a problem as follows. For each customer $v\in V$, for each commodity $k\in K$ we assume that the demand $D_{...


3

If you are interested in a model-and-run approach, maybe you can have a look at LocalSolver. An example model for basic k-means is given here. LocalSolver finds near-optimal solutions in seconds until 10,000 points to be clustered. Instead of the classical Boolean modeling approach, using so-called set variables makes the model natural to read and compact in ...


3

To solve this using a p-center formulation, you could use this base model: \begin{align} P: \min&\quad \sum_{i,j\in I}c_{ij}x_{ij}&\\ \text{s.t.}&\quad \sum_{j\in I} x_{ij} =1 & \forall i\in I\\ &\quad \sum_{i\in I}x_{ii}\leq maxClusters &\\ &\quad x_{ij}\leq x_{jj} &\forall i,j\in I\\ &\quad u\geq \sum_{i\in I}x_{ij} &...


3

I'm not familiar with agglomarative clustering, but in general terms you are dealing with a bicriterion optimization problem. One criterion has to do with the "affinities" of points in a cluster. You may want to maximize (?) something to do with the pairwise weights. That might be the sum of the weights of all pairs sharing a cluster, or the ...


2

The naïve method you describe (loop over all points, select those that have more than $n$ other points within distance $M$ of them) is actually not a bad choice, as long as you store your points in a suitable spatial data structure (such as something based on a quadtree) that makes finding and/or counting nearby points a cheap operation. One advantage of ...


2

Roughly speaking, in minimum cut problems, the goal is generally to find a minimum cut (possibly weighted) between two fixed sets of vertices, called the sources and the sinks. Given one source and one sink in input, the problem can be solved in polynomial time, a famous theorem in combinatorial optimization. On the other hand, in graph partitioning problems,...


2

An approach sometimes used in other contexts is to start with an "optimal" assignment. If the number of sales people increases by one or two, solve a separate model (say a MIP model) that selectively reallocates some territories to the new sales people with constraints on how many they get, how much territory their clientele span, and how many clients each ...


1

I had the following model lying around: $$\begin{aligned} \min&\sum_{i,k}\color{darkred}d_{i,k}\\ & \color{darkred}d_{i,k} \ge \sum_c \left(\color{darkblue}p_{i,c}-\color{darkred}\mu_{k,c}\right)^2-\color{darkblue}M(1-\color{darkred}x_{i,k}) \\ & \sum_k\color{darkred}x_{i,k} = 1 && \forall i\\ & \color{darkred}n_k = \...


Only top voted, non community-wiki answers of a minimum length are eligible