<p>(This following is just my comment above migrated into solution form).</p>

<p>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</p>

<p>minimize $\sum x_i$</p>

<p>subject to</p>

<ol>
<li><p>$\max \left\{x_i, x_j\right\} = 1$ for $(x_i,x_j) \in E$</p></li>
<li><p>$x_i \geq 0$ for all $i \in \{1, 2, \cdots, |V|\}$.</p></li>
</ol>

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2014-01-31T22:57:52.880Z
2014-01-31T22:57:52.880Z
Yonatan N
<p>M(G)ods, if you deem this response unfit to be an <em>answer</em>, please move it to a comment.</p>

<p>FWIW, one could write a <em>binary</em> integer linear program model for the problem:</p>

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

<p>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$.</p>

<p>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. </p>

CC BY-SA 3.0
2014-01-31T01:18:49.250Z
2014-01-31T01:18:49.250Z
kbala
<p>Consider this "variant" of linear programming:</p>

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

<p>minimize $\sum a_i x_i$</p>

<p>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\}$</p>

<p>For example: </p>

<p>minimize $0.1 x_1+ 0.2x_2 +0.3x_3+0.4 x_4$</p>

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

<p>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?</p>

<p>Many thanks. </p>

CC BY-SA 3.0
2014-01-24T16:37:04.390Z
If you can relax the requirement to $max\{|x_i|\}=b_k$, it's called the max-norm constraint. In that case, the following paper proposes discusses a solution method: http://www.eecs.berkeley.edu/~brecht/papers/maxnorm.NIPS10.pdf
nojka_kruva
CC BY-SA 3.0
2014-01-24T20:02:05.833Z
This can encode vertex cover by setting $a_i = b_j = 1$ for all $i,j$ and having one $J_k$ for each pair of endpoints of an edge in the graph.
Yonatan N
CC BY-SA 3.0
2014-01-25T00:09:54.730Z
@YonatanN Close, but not quite. A feasible solution to your formulation would be to set $x_1=-\infty$ and all other $x$ variables to 1. You would need to do something like $\max \{-x_1, ..., -x_n \}=0$ to enforce nonnegativity, but this is not allowed in the problem statement.
Austin Buchanan
CC BY-SA 3.0
2014-01-25T00:46:20.873Z
As written, this LP might not be bounded. Do you also assume that all $x_i \ge 0$ ?
Suresh Venkat
CC BY-SA 3.0
2014-01-28T11:13:02.160Z
@SureshVenkat, yes, I assume that $x_i\geq 0$. Sorry for the confusion.
maomao
CC BY-SA 3.0
2014-01-30T02:23:30.867Z
In that case doesn't @YonatanN's solution apply ? because your assumption fixes the problem raised by Austin.
Suresh Venkat
<cc.complexity-theory><linear-programming>
A variant of linear programming
maomao
# A variant of linear programming

(Asked by: username_0 on 2014-01-24)

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.

**Tags:** cc.complexity-theory, linear-programming

> **Comments:**
> **username_1**: If you can relax the requirement to $max\{|x_i|\}=b_k$, it's called the max-norm constraint. In that case, the following paper proposes discusses a solution method: http://www.eecs.berkeley.edu/~brecht/papers/maxnorm.NIPS10.pdf  
> **username_2**: This can encode vertex cover by setting $a_i = b_j = 1$ for all $i,j$ and having one $J_k$ for each pair of endpoints of an edge in the graph.  
> **username_3**: @YonatanN Close, but not quite. A feasible solution to your formulation would be to set $x_1=-\infty$ and all other $x$ variables to 1. You would need to do something like $\max \{-x_1, ..., -x_n \}=0$ to enforce nonnegativity, but this is not allowed in the problem statement.  
> **username_4**: As written, this LP might not be bounded. Do you also assume that all $x_i \ge 0$ ?  
> **username_0**: @SureshVenkat, yes, I assume that $x_i\geq 0$. Sorry for the confusion.  
> **username_4**: In that case doesn't @YonatanN's solution apply ? because your assumption fixes the problem raised by Austin.  

---

## 2 answers

### Answer by username_2 on 2014-01-31. Score: 3

(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 by username_5 on 2014-01-31. Score: 0

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.


---

