# Which JuMP.jl solver for this problem?

**URL:** https://discourse.julialang.org/t/which-jump-jl-solver-for-this-problem/43350
**Category:** Optimization (Mathematical)
**Tags:** jump, optimization
**Created:** [July 19, 2020, 8:21pm UTC](https://discourse.julialang.org/t/which-jump-jl-solver-for-this-problem/43350 "2020-07-19T20:21:13Z")
**Posts on this page:** 1
**Showing post:** 17

<div class="post-metadata">

### Author: ![mtanneau](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mtanneau/32/17787_2.png) [@mtanneau](https://discourse.julialang.org/u/mtanneau)
#### Post date: [July 23, 2020, 2:07am UTC](https://discourse.julialang.org/t/which-jump-jl-solver-for-this-problem/43350/17 "2020-07-23T02:07:28Z")

</div>

Start with a binary variable x\_{i, k} that takes value 1 if city i is in group k and 0 otherwise.  
Each city must be in a group, so we add the constraint \sum\_{k} x\_{i, k} = 1 for every i.

The total population of group k is then Q\_{k} = \sum\_{i} x\_{i, k} q\_{i}.  
Adding bounds Q\_{min} \leq Q\_{k} \leq Q\_{max} (as you suggested initially) will ensure that groups have similar population levels.

Then, there’s the question of the distance. We want to minimize the sum of distances between pairs of cities in a same group.  
Let z\_{i, j} be a binary variable that takes value 1 if cities i and j are in the same group, and 0 otherwise. Then the total distance is just \sum\_{i, j} d\_{i, j} z\_{i, j}. (note that I’m counting each pair twice here).

To ensure that z\_{i, j} = 1 if and only if cities i and j are in the same group, one way is to add the constraints z\_{i, j} \geq x\_{i, k} + x\_{j, k} - 1 for every pair i, j and every k.  
It is easy to verify that, if cities i, j are in group k, then z\_{i, j} \>= 1+ 1 - 1 = 1.  
Otherwise, x\_{i, k} + x\_{j, k} cannot exceed 1, thus z\_{i, j} \geq 0 and, since we are minimizing and z\_{i, j} has positive objective coefficient, we get z\_{i, j} = 0 in any optimal solution.

The size of this model is thus:

- N \times k + k + N \times N variables
- N + N \times N \times k constraints

I tried this with 10 cities, CPLEX solved the model in a fraction of second.  
For 30 cities, it took CPLEX 10s.

I let you imagine what happens with 3,000 cities…

---

_[View the full topic](https://discourse.julialang.org/t/which-jump-jl-solver-for-this-problem/43350)._