Optimizing sum of discrete minimum

Question

Please consider the following optimization problem: Given a fixed positive natural $n < N$, and a set of functions $f_i$ over a finite domain of nonnegative outputs, s.t. $1 \le i \le N$, then we optimize \begin{align*} \min&\sum_x(\min_i (b_i \cdot f_i(x)) ) \\ \text{s.t. }&\sum_i b_i = n \\ & b_i \in \{0, 1\}. \end{align*} In short, the objective is to choose $n$ functions from $f_i$, such that the sum of the minimal outputs is optimized. My question is: is there a name for this problem and is there an existing solver for it?

My followup thought is that this is not an integer programming problem. Let's try to eliminate the minimization within the objective function. Let's introduce another set of variables $c_{i,x}$ to choose the minimum over $x$. Then the problem becomes \begin{align*} \min&\sum_x \sum_i (b_ic_{i,x} \cdot f_i(x)) \\ \text{s.t. }&\sum_i b_i = n \\ & \sum_xb_ic_{i,x} = 1 \\ & b_i,c_{i,x} \in \{0, 1\}. \end{align*} Clearly, it cannot be an IP problem because we are multiplying the variables. Please let me know what are your thoughts and how would you go about solving this problem.

---

Example: consider the following functions over $\{1, 2, 3\}$, with matching outputs in this order:

\begin{align*} f_1 &= \{1, 2, 3\} \\ f_2 &= \{3, 1, 3\} \\ f_3 &= \{3, 3, 1\}. \end{align*} If we may choose all three of them, then it's quite clear that the overall minimal function is just $\{1, 1, 1\}$, and therefore the objective value is $3$ (total of all three $1$'s).

Now we need to choose $2$ from them to minimize the sum of minima. We just verify them exhaustively:

• if we choose $f_1$ and $f_2$, then we have $1 + 1 + 3 = 5$;

• if we choose $f_1$ and $f_3$, then we have $1 + 2 + 1 = 4$;

• if we choose $f_2$ and $f_3$, then we have $3 + 1 + 1 = 5$.

In this case, choosing $f_1$ and $f_3$ produces the minimal sum, so this is our desired result.

Answer 1

Your example shows that your objective function is instead $$\sum_x \min_{i: b_i = 1} f_i(x)$$

You can linearize the problem as follows: \begin{align} &\text{minimize} &\sum_x \sum_i c_{i,x} f_i(x) \\ &\text{subject to} &\sum_i b_i &= n \\ &&\sum_i c_{i,x} &= 1 &&\text{for all $x$} \\ &&c_{i,x} &\le b_i &&\text{for all $i$ and $x$} \\ &&b_i &\in \{0, 1\} &&\text{for all $i$} \\ &&c_{i,x} &\in \{0, 1\} &&\text{for all $i$ and $x$} \end{align}

Now you can use an integer linear programming solver, which for your example yields optimal solution $b_1=b_3=c_{1,1}=c_{1,2}=c_{3,3}=1$ and all other variables $0$.