Explicit solution for a linear program with two constraints

Question

This is not a homework problem, although it wouldn't surprise me if it happens to exist in a textbook somewhere. Is there an explicit solution for the linear program $$\max_x c^Tx ~~ s.t. \\ d^Tx = q \\ \mathbf{1}^Tx = 1 \\ x \geq 0$$where $\mathbf{1}$ denotes a vector of all ones? Obviously, we know that there will be at most two non-zero entries $x_i$, and if we were to remove the constraint $d^Tx=q$ then the solution would simply have $x_i=0$ where $i$ is the index of the largest element of $c$.

Answer 1

This post captured my imagination for some reason!

I spent a lot of time looking at the dual problem. I managed to simplify it down to this univariate piecewise-linear minimization: $$\text{minimize} ~ \max_i c_i - (q-d_i) y$$ $y$ is actually the Lagrange multiplier for the $d^Tx=q$ constraint.

Assuming the original problem is feasible and otherwise non-trivial (i.e., $d\neq q\vec{1}$), the solution to the dual problem lies at a vertex: a point at which two of the values of $c_i - (q-d_i) y$ are equal. The two indices $i_1$ and $i_2$ that achieve this equality are the indices of the two non-zero elements of $x$. (Ties can be broken arbitrarily.) You can prove this with complementary slackness, if you are so inclined.

So the faster you can solve this piecewise linear minimization, the faster you can solve the problem.

But once it was clear that you could find a solution with no more than two nonzeros---that is, assuming it is feasible in the first place---the simplest thing to do is just to enumerate the pairs. That is, for each $i,j=1,2,\dots, n$, $i<j$ solve the two-variable problem analytically, and select the best result from all of those. In other words, for each pair of indices, consider the linear system $$\begin{bmatrix} d_i & d_j \\ 1 & 1 \end{bmatrix} \begin{bmatrix} x_i \\ x_j \end{bmatrix} = \begin{bmatrix} q \\ 1 \end{bmatrix}$$ There are three cases:

• If $d_i=d_j=q$, the solution is $\max\{c_i,c_j\}$.
• If $d_i=d_j$ and $d_i\neq q$, there is no solution; do not consider this pair.
• Otherwise, solve for $x_i,x_j$. If $0\leq x_i,x_j\leq 1$, the solution is $c_ix_i+c_jx_j$.

Once you've scanned all the pairs, the candidate with the best objective function is your answer. (If none of the pairs yielded a candidate, the problem is infeasible.) So you have at most $n(n-1)/2$ candidates to consider, each of which costs $O(1)$ flops to solve. That's pretty darn cheap as algorithms go.

You don't have to settle for this brute force method, if you can instead find a way to solve that dual piecewise linear minimization more quickly. But when I began to look at this, I quickly concluded that it was probably an $O(n^2)$ enterprise as well. Once I realized that, I figured that there was little point in wasting my time on anything but the most obvious approach.