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$

st: $\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:

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

st $\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.

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.