# Combinatorial optimization, implementation needed

I have k sets of items. I want to choose n items from each set, $$n \cdot k$$ items total.

I would like to choose the $$n \cdot k$$ items under some optimization criterion, e.g. that the sum of the $$\ell_1$$ distance between every pair of items is maximized.

I am okay slightly relaxing the criterion that $$n$$ items must be drawn from each set, as long as $$n \cdot k$$ items total are chosen.

What is this kind of optimization specifically? Where can I find an implementation, preferably a python implementation?

• To answer the last question, it is unlikely that a Python implementation exists. There are some packages implementing algorithms for very classical optimization problems, but not for too specific ones. So, you can either use a generic solver for which you need to describe your problem mathematically (MIP, MIQP...) as suggested in the answers, or implement your own algorithm (or ask someone to do it for you, but it might not be free). If your problem is not too large, the first solution should work well with free solvers Aug 3, 2021 at 20:06

It seems what you are looking for, is the maximum dispersion problem. The following blog post discusses a MIQP formulation along with a number of different MILP formulations http://yetanothermathprogrammingconsultant.blogspot.com/2019/06/maximum-dispersion.html?m=1

• +1 for referring to Erwin's Ali Baba's cave Aug 3, 2021 at 13:31
• @sune this is great, are you aware of a simple Python implementation of maximum dispersion? Aug 5, 2021 at 18:22
• No, unfortunately not. A quick Google search lead to this answer to a stackexchange question, which includes a python implementation using gurobi as solver stackoverflow.com/a/56877469/1597775
– Sune
Aug 6, 2021 at 6:04

Let $$x_{i}$$ be a binary variable that takes value $$1$$ if item $$i \in I_k$$ is selected.

You want to choose $$n$$ items from each set $$I_k$$, so impose $$\sum_{i\in I_k} x_{i} = n \quad \forall k$$ You can optimize whatever you want with these variables. If you want to maximize the $$\ell_1$$ distance between each pair of items, you are going to need a pairwise variable as well. So introduce a binary variable $$y_{ij}$$ that takes value $$1$$ if items $$i$$ and $$j$$ are simultaneously selected: $$x_i + x_j \le y_{ij} +1 \\ y_{ij} \le x_i \\ y_{ij} \le x_j$$

and use the following objective function: $$\sum_{i,j} d_{ij}^{\ell^1} y_{ij}$$

I don't know if this is a known optimization problem. But the above formulation is linear (with integer variables), commonly refered to as a MIP. You can easily implement this in Python with PuLp or Pyomo.