14

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 ...


11

Let binary decision variable $x_{i,g}$ indicate whether node $i\in\{1,\dots,N\}$ appears in group $g\in\{1,\dots,N\}$, and let binary decision variable $y_{i,j,g}$ indicate whether edge $(i,j)$ appears in group $g$. You want to maximize $$\sum_{i<j}\sum_g w_{i,j} y_{i,j,g}$$ subject to \begin{align} \sum_g x_{i,g} &= 1 &&\text{for all $i$} \...


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

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_{...


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

[I'm leaving out constraint 0] I see two levels of decisions in your problem: Group servers into clusters Assign each user to one of these clusters (BTW, this way of seeing the problem is heavily inspired by Facility location problems). The second step is actually the easiest: once the clusters are known, you can just compute each user's gain w.r.t to each ...


4

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 = \...


4

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 ...


4

Your distance constraint for each cluster limits the sum of the distance from each cluster point to its nearest neighbor (excluding the last point selected for the cluster, whose nearest neighbor is not taken). It does not look at the total distance between all pairs of points in the cluster, nor the maximum distance between any pair of points (the cluster &...


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

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

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 ...


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 ...


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