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?

  • $\begingroup$ 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 $\endgroup$
    – fontanf
    Aug 3 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

  • $\begingroup$ +1 for referring to Erwin's Ali Baba's cave $\endgroup$
    – Kuifje
    Aug 3 at 13:31
  • $\begingroup$ @sune this is great, are you aware of a simple Python implementation of maximum dispersion? $\endgroup$ Aug 5 at 18:22
  • $\begingroup$ 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 $\endgroup$
    – Sune
    Aug 6 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.