Mechanical engineer here with little to no formal training in optimisation. Recently though, I've spent some time looking into optimisation and dynamic programming due to a problem I wanted to solve at work (and for learning purposes).
The problem is as follows: Given a set of N real numbers and a number k <= N, find the subset of k numbers that "maximizes spread"
I guess "maximising spread" can mean maximising the minimum distance between all numbers. To me, this looks like textbook minimax, even though I havent found any posts with the same problem.
My attempt to solve it:
$$X_{i,j} = \max\limits_{i=0..k \\ j=i..n}\{\min\limits_{k=0..j}(X_{i-1,k}, A_i - A_k)\}$$
where $X_{i,j}$ is the solution for choosing $k$ numbers from the first $i$ input numbers and $A_i$ is the ith number in the input.
I've written an algorithm using dynamic programming with lookup table and "parent pointers" 1. Python solution can be found here: https://pastebin.com/EsEhyChc
So my questions are
- Have I expressed the problem rigorously?
- Is my analysis correct?
- Is my solution correct?
Learning a lot here. Any help and insights are greatly appreciated! Thanks!
Here is an alternative approach that uses integer linear programming. Maybe you can use it to validate optimality of your DP solution.
First sort so that $A_i < A_j$ if $i < j$. Let binary decision variable $x_i$ indicate whether the $i$th number is selected. Let binary decision variable $y_{i,j}$ represent $x_i x_j$. The problem is to maximize $z$ subject to linear constraints: \begin{align} \sum_{i=1}^N x_i &=k \tag1\\ x_i + x_j - 1 &\le y_{i,j} &&\text{for $i < j$} \tag2\\ z - A_j + A_i &\le (A_N - A_1 - A_j + A_i)(1 - y_{i,j}) &&\text{for $i < j$} \tag3 \end{align} Constraint $(1)$ enforces that exactly $k$ numbers are selected. Constraint $(2)$ enforces $(x_i = 1 \land x_j = 1) \implies y_{i,j} = 1$. Constraint $(3)$ enforces $y_{i,j} = 1 \implies z \le A_j - A_i$.