Combinatorial optimization, implementation needed

Question

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?

Answer 1

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

Answer 2

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.