Skip to main content

# Tag Info

## Hot answers tagged clustering

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 ...
• 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)$ ...
• 33.6k
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 ...
• 6,667
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 ...
• 33.6k
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 ...
• 5,894
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 ...
• 33.6k
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 ...
• 13.7k
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 ...
• 5,949
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 ...
• 4,268
4 votes

• 33.6k
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 ...
• 40.1k
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 ...
• 40.1k
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 ...
• 2,133
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,...
• 3,031
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 & \...
• 3,481
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 ...
• 40.1k
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)...
• 40.1k
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$ ...
• 3,513
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 ...
• 3,031
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 ...
• 40.1k
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 ...
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. ...
• 40.1k
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 ...
• 40.1k
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 ...
• 40.1k
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
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 ...
• 3,031
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 ...
• 40.1k

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