Skip to main content
14 votes
Accepted

What are some "clustering" algorithms? (but not the type of clustering you're thinking about)

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 ...
Ggouvine's user avatar
  • 1,877
11 votes
Accepted

How to partition a graph with optimal number of groups?

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)$ ...
RobPratt's user avatar
  • 32.8k
9 votes

Customer clustering to solve very large-scale VRPs

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 ...
Sune's user avatar
  • 6,647
8 votes
Accepted

A clustering problem with 0 or 1 distances for minimizing the summation of distances

This is a variant of the minimum $k$-cut problem. The node set is $\mathbb{X}$, the edge weights are $1-d(x,y)$, and $k=S$. Also related to the wedding planner problem, where $\mathbb{X}$ is the set ...
RobPratt's user avatar
  • 32.8k
7 votes
Accepted

Customer clustering to solve very large-scale VRPs

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 ...
EhsanK's user avatar
  • 5,874
6 votes
Accepted

An efficient method for zoning bins in a warehouse

Here is a reformulation as MIQP. Minimize $$\sum_{i,j,j'} D_{jj'} x_{ij} x_{ij'}$$ subject to $$\sum_i x_{ij} = 1 \quad \text{for all $j$} \tag1\label1$$ If both $j$ and $j'$ are assigned to the same ...
RobPratt's user avatar
  • 32.8k
5 votes

Clustering problem involving multidepots and customers requiring commodities located exclusively in an specific depot

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 ...
Kuifje's user avatar
  • 13.5k
5 votes

k-means/k-medoids Clustering Implementation in CPLEX Java

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 ...
Marco Lübbecke's user avatar
4 votes

How to solve this clustering problem with heuristic or meta-heuristic approach?

[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 ...
mtanneau's user avatar
  • 4,183
4 votes

Any Solution for $k$-means with minimum and maximum cluster size constraint?

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}...
Erwin Kalvelagen's user avatar
4 votes

Any Solution for $k$-means with minimum and maximum cluster size constraint?

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 ...
Kuifje's user avatar
  • 13.5k
4 votes
Accepted

Optimizing a capacitated clustering problem with Greedy search algorithm

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 ...
prubin's user avatar
  • 39.6k
4 votes
Accepted

Clustering a large ride-matching problem

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_{...
RobPratt's user avatar
  • 32.8k
3 votes

Turning K-Medoids into an optimization problem

Yes, the problem can be solved exactly using common IP algorithms such as branch-and-cut, with the usual qualification that there will be some limit on the size of the problems you can handle. (What ...
prubin's user avatar
  • 39.6k
3 votes

Clustering optimization problem for categorical data: How to solve?

I tried a random key genetic algorithm (in R, using four parallel threads), both as a "standard GA" (single population) and as an "island" model (multiple populations, four in my ...
prubin's user avatar
  • 39.6k
3 votes

Customer clustering to solve very large-scale VRPs

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 ...
Alberto Santini's user avatar
3 votes

Clustering points based on a distance matrix

If you are interested in a model-and-run approach, maybe you can have a look at Hexaly. An example model for basic k-means is given here. Hexaly finds near-optimal solutions in seconds, with up to 100,...
Hexaly's user avatar
  • 2,986
3 votes
Accepted

Clustering points based on a distance matrix

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 & \...
Joris Kinable's user avatar
3 votes

Clustering points based on a distance matrix

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 ...
prubin's user avatar
  • 39.6k
3 votes

Grouping values based on a difference constraint

Some of this may be solver dependent. I just ran your model with only one change -- switching the solver from glpk to CPLEX -- and got a valid solution (the same as yours, changing group 10 to group 2)...
prubin's user avatar
  • 39.6k
3 votes

Grouping values based on a difference constraint

Since you've a threshold (diff) you may pre-define max of diff number of groups, not the full length of the list. As for the if condition try this $L(x_{i,g}+x_{j,g}-1) \le d - (L_j - L_i)$ where $L$ ...
Sutanu Majumdar's user avatar
2 votes

What is the difference between min- cut formulation and (bi) partitioning formulation?

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 ...
Hexaly's user avatar
  • 2,986
2 votes

How to design and scale sales territory?

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 ...
prubin's user avatar
  • 39.6k
2 votes

What are some "clustering" algorithms? (but not the type of clustering you're thinking about)

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 ...
Ilmari Karonen's user avatar
2 votes

How to perform clustering of two different sets of entities?

In preliminary tests, a greedy heuristic seems to do rather well for the problem. The greedy heuristic I tried starts out with each transmitter being a cluster of size 1, and then loops indefinitely. ...
prubin's user avatar
  • 39.6k
2 votes
Accepted

How to perform clustering of two different sets of entities?

This can be formulated as a MIP model using a gaggle of binary variables. First, we introduce some parameters. $\tau(u)$ is the index of the transmitter with highest weight for user $u$. I will ...
prubin's user avatar
  • 39.6k
2 votes

How to write a constraint to define valid agglomerations of sites?

I don't think there is any way to get a single constraint for each group establishing contiguity. Assume that we represent the sites as nodes in a graph, with edges between adjacent sites. The link ...
prubin's user avatar
  • 39.6k
1 vote

Turning K-Medoids into an optimization problem

sure, K-medoids could be expressed as an optimization problem, I recommend you read the paper: Clustering by a means of medoids, Leonard kaufman, peter rousseeuw
Jair Ramos's user avatar
1 vote

An efficient method for zoning bins in a warehouse

As you understood, your zoning problem can be modeled as a clustering problem: discrete decision variables related to assigning items to sets, possible additional constraints on how the items can or ...
Hexaly's user avatar
  • 2,986
1 vote

An efficient method for zoning bins in a warehouse

Rather than summing all the distances, another possible objective function is to minimize the sum of the "diameters" of the zones, where the diameter is the maximum distance between any two ...
prubin's user avatar
  • 39.6k

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