A variant of linear programming 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.
(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


$\max \left\{x_i, x_j\right\} = 1$ for $(x_i,x_j) \in E$
$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.