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
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}...
- 2,850
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 ...
- 13.7k
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 ...
- 40.1k
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_{...
- 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 ...
- 168
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
- 11
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