A variant of linear programming

Question

Consider this "variant" of linear programming:

Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$;

minimize $\sum a_i x_i$

such that $\max\{x_i\mid i\in J_k\}=b_k$ where $1\leq k\leq m$ and $J_k\subseteq \{1, \cdots, n\}$

For example:

minimize $0.1 x_1+ 0.2x_2 +0.3x_3+0.4 x_4$

such that $\max\{x_1, x_4\}=0.7$ and $\max\{x_1, x_2, x_3\}=0.5$

What's the complexity of solving this problem? Can it be reduced to linear programming? Is there any efficient approach? Or is there any deep theory behind this problem?

Many thanks.

Answer 1

(This following is just my comment above migrated into solution form).

We construct a Karp reduction from Vertex Cover into your problem. Given a graph $G = (V,E)$ in which we want to find the size of a minimum vertex cover, construct the following program

minimize $\sum x_i$

subject to

1. $\max \left\{x_i, x_j\right\} = 1$ for $(x_i,x_j) \in E$

2. $x_i \geq 0$ for all $i \in \{1, 2, \cdots, |V|\}$.

This is just an instance of your linear programming variant, with $\vec a = \vec b = 1$ and $\mathcal{J} = \left\{\{u,v\} | (u,v) \in E\right\}$ along with your assumption from the comments that all variables are positive (which, as @AustinBuchanan and @SureshVenkat point out, is important).

It's easy to see that each vertex cover satisfies (1), and that anything that satisfies (1) and (2) can be transformed into a vertex cover by decreasing all variables until they hit $1$ or $0$ (whichever comes first). Thus, the two problems have the same objective value (enough to show NP-hardness), and in fact such a program immediately reveals the optimal vertex cover itself.

Answer 2

M(G)ods, if you deem this response unfit to be an answer, please move it to a comment.

FWIW, one could write a binary integer linear program model for the problem:

$$ \begin{array}{lrcll} \min & \sum_j a_j x_j \\ \mbox{s.t.} & x_i & \leq & b_k, & \forall i \in J_k,~ k=1,\dots,m; \\ & x_i & \geq & b_k - M (1-z_{ik}), & \forall i \in J_k,~ k=1,\dots,m; \\ & \sum_{i \in J_k} z_{ik} & = & 1 & k=1,\dots,m; ~\mbox{and}\\ & z_{ik} & \in & \{0,1\} & \forall i,k. \end{array} $$

The constraints with the extra binary variables $z_{ik}$ force a/the largest of the $x_i, i \in J_k$ to equal $b_k$.

Typically, constraints of the $\min$-$\max$ or $\max$-$\min$ forms (i.e., minimize the maximum of a set of linear functions, or vice versa) could be modeled as linear inequalities, i.e., as linear programs, without requiring extra binary variables. In this case, we have to set the maximum of a set of variables ($x_i, i\in J_k$) to some predefined value ($b_k$). AFAICS, one could not avoid the use of extra binary variables when writing these maximum constraints as linear (in)equalities, for instance, as shown above.