1

Notation: $\max( x_1, \cdots, x_n )$ denotes the maximal number among $x_1, \cdots, x_n$. $\min( x_1, \cdots, x_n )$ denotes the minimal number among $x_1, \cdots, x_n$.

Assumption: $x_i, a_i, b_k$ are all in $[0,1]$

minimize $\max( \{ \min(a_i, x_i) \mid i \in I\})$

$\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 $\max( \{ \min(0.2, x_1) , \min(0.8, x_3)\})$

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

What's the complexity of this problem?

user124986
  • 31
  • The question is from linear programming. If one replaces + by max and * by min, the OP seems to be a very natural question. I suspect that there is a polynomial algorithm to solve this problem, but I could not obtain a very neat solution. Moreover I am wondering whether there is a general theory regarding this type of questions. – user124986 Jan 30 '14 at 15:59
  • These kinds of problems have a name... which I cannot for the life of me summon up. They are not linear programming problems, (see http://mathoverflow.net/questions/72735/linear-program-to-maximize-the-minimum-absolute-value-of-linear-functions) and are harder than ordinary optimization problems. I will post again once I recall the name of the type of problem. – Jeff Snider Jan 30 '14 at 18:43
  • On the other hand, this answer suggests a way to linearize: http://stackoverflow.com/questions/10792139/using-min-max-within-an-integer-linear-program – Jeff Snider Jan 30 '14 at 18:44

1 Answers1

0

On finding the maximum of $$\min(a_i, x_i).$$ Create extra variables $y_i$, add the constraints $$y_i\ge a_i, \text{ and } y_i\ge x_i,$$ and add one more variable $z$ plus the constraints $z\le y_i$ for all $i$. Your objective function is now $$z$$ which you want to maximize subject to the constraints.

This may not be a linear programming problem because the domain is non-convex, but a wide variety of solvers and techniques exist which can find the solution for you.

Jeff Snider
  • 2,817