2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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: eecs.berkeley.edu/~brecht/papers/maxnorm.NIPS10.pdf $\endgroup$ – Victor May Jan 24 '14 at 16:37
  • 4
    $\begingroup$ 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. $\endgroup$ – Yonatan N Jan 24 '14 at 20:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Austin Buchanan Jan 25 '14 at 0:09
  • 1
    $\begingroup$ As written, this LP might not be bounded. Do you also assume that all $x_i \ge 0$ ? $\endgroup$ – Suresh Venkat Jan 25 '14 at 0:46
  • 3
    $\begingroup$ In that case doesn't @YonatanN's solution apply ? because your assumption fixes the problem raised by Austin. $\endgroup$ – Suresh Venkat Jan 30 '14 at 2:23
2
$\begingroup$

(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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.