# How to solve this linear program with an exponential number of constraints?

Consider the following convex program:

\begin{align*} \min g(x) && \text{such that} \\ f_i(x) &\geq b_1 && \text{ for } i \in 1,\ldots,n; \\ f_i(x)+f_j(x) &\geq b_1+b_2 && \text{ for } i,j \in 1,\ldots,n; \\ f_i(x)+f_j(x)+f_k(x) &\geq b_1+b_2+b_3 && \text{ for } i,j,k \in 1,\ldots,n; \\ \cdots \\ f_1(x)+\cdots+f_n(x) &\geq b_1+\cdots +b_n \end{align*}

That is: every function $$f_i$$ is at least $$b_1$$; every pair of functions sum up to at least $$b_1+b_2$$; every three functions sum up to at least $$b_1+b_2+b_3$$; etc. The $$b_i$$ are constants: $$0.

The problem is that the number of constraints is exponential in $$n$$. Is there a way to attain the same outcome with a convex program of size polynomial in $$n$$?

• You could try and add the constraints on the fly if they are violated. Sep 7, 2022 at 13:57
• @Kuifje this is a general heuristic for solving programs with many constraints. But in the worst case it might still be exponential. I am looking for a way to convert this specific program into a program of polynomial size. Sep 7, 2022 at 13:58
• True in the worst case you might end up with an exponential number of constraints. But note that it is not a heuristic as optimality is guaranteed if you do add all the necessary cuts dynamically. Sep 7, 2022 at 14:30

For each $$k\in\{1,\dots,n\}$$, you want the sum of the $$k$$ smallest $$f_i(x)$$ to be at least $$\sum_{j=1}^k b_j$$. Equivalently, you want the sum of the $$n-k$$ largest $$f_i(x)$$ to be at most $$\sum_{i=1}^n f_i(x) - \sum_{j=1}^k b_j$$.
Introduce variable $$y_k$$ to represent the $$(n-k)$$th largest $$f_i(x)$$ and nonnegative variable $$z_{ik}$$ to represent $$\max(f_i(x)-y_k,0)$$. Now impose $$n+n^2$$ constraints \begin{align} (n-k)y_k + \sum_{i=1}^n z_{ik} &\le \sum_{i=1}^n f_i(x) - \sum_{j=1}^k b_j &&\text{for all k} \\ z_{ik} &\ge f_i(x) - y_k &&\text{for all i and k} \end{align}
Alternatively, a slightly more direct approach is to introduce variable $$y_k$$ to represent the $$k$$th smallest $$f_i(x)$$ and nonnegative variable $$z_{ik}$$ to represent $$\max(y_k-f_i(x),0)$$. Now impose $$n+n^2$$ constraints \begin{align} k y_k - \sum_{i=1}^n z_{ik} &\ge \sum_{j=1}^k b_j &&\text{for all k} \\ z_{ik} &\ge y_k - f_i(x) &&\text{for all i and k} \end{align}