<p>To follow up on Snowie's post:</p>

<p>For each term max(v1, v2) introduce a new variable $x_i$, subject to the constraints $x_i \geq v_1, x \geq v_2$</p>

<p>For each term min(v1,v2) introduce a variable $y_i$ subject to $y_i \leq v_1, y_i \leq v_2$.</p>

<p>Next, minimize the linear constraint $l = \sum x_i - \sum y_i$
subject to the inequations $x \geq v, y \geq v$, the linear equations $0 \leq v \leq 1$, AND the original linear system of equations.</p>

<p>This is a linear program, hence solvable in polynomial time. As the number of such constraints is polynomial, the entire system is solved in polynomial time.</p>

CC BY-SA 3.0
2011-06-24T15:47:12.127Z
Fantastic, this works like a charm.
Thomas Ahle
CC BY-SA 3.0
2011-06-24T15:47:59.567Z
Since my solution is unique the `0<=v<=1` inequalities aren't necessary.
Thomas Ahle
CC BY-SA 3.0
2011-06-24T16:56:38.767Z
In general, an equal number of constraints does not imply the solution is uniquely determined. Even generically, given $n$ possible min/max pairs, one can construct $2^n$ determined linear systems. Each has a real solution, which obeys the min/max constraints with probability $2^{-n}$. Hence one expects, generically, a single random solution in addition to the causal solution. (The actual number is Poisson distributed). So, you CANNOT discard the constraints $0 \leq v \leq 1$ and expect to solve uniquely
David Harris
CC BY-SA 3.0
2018-03-18T22:29:33.370Z
is the $0 \leq v \leq 1$ constraint required because all variables are fractions in (0,1)?
evan54
CC BY-SA 3.0
2011-06-24T12:53:22.587Z
2011-06-24T12:53:22.587Z
David Harris
<p>Removing the min/max operations in your problem, you can write your problem in a standard mixed integer programming.  If your problem contains $N$ min/max operations, then your problem can be solved in $O(2^N)$ time, ignoring polynomial factors.</p>

<p>The removal of the min/max operation is easy.  For example, let us remove Max[b,c].  First, add a variable x such that x = Max[b,c], and replace Max[b,c] with x.  The relation x = Max[b,c] can be written as the following inequalities adding another binary variable y (i.e, y=0 or y=1):<br>
x >= b<br>
x >= c<br>
x &lt;= by + c(1-y)<br>
You can remove the min operations in a similar way, and you'll obtain a standard mixed integer programming formulation.</p>

CC BY-SA 3.0
2011-06-24T05:22:09.783Z
This answer assumes that all variables in your problem can be fractional (non-integer) values.  If the assumption is not true, ignore this answer.
Snowie
CC BY-SA 3.0
2011-06-24T07:55:46.857Z
The variables are all fractions in `(0,1)`, so that should be fine. Do you recon that this `O(2^N)` mixed interger solution is faster than just creating `2^N` different equation sets, where each Min/Max has been chosen?
Thomas Ahle
CC BY-SA 3.0
2011-06-24T08:15:27.707Z
@Thomas: Now I understand your problem.  From the theoretical point of view, I don't think my MIP solution is faster than your idea.  However, if you really want to solve your problem in practice, then it is worth trying to use MIP solvers (such as CPLEX) to solve my MIP formulation, because MIP solvers utilize various efficient heuristics.
Snowie
CC BY-SA 3.0
2011-06-24T12:06:33.067Z
You hear about MIP solers solving systems with thousands of variables. Do you think it would do better than a simple solution here?
Thomas Ahle
CC BY-SA 3.0
2011-06-24T05:15:44.000Z
2011-06-24T05:15:44.000Z
Snowie
<p>In solving a certain game, I've ended up with a set of equalities like these:</p>

<pre><code>a == Max[b,c]/2+Max[d,e]/2
b == Min[f,g]/2+Min[h,i]/2
...
o == (1-d)/2+r/2
p == (1-d)/2
q == s/2+1/2
r == Max[1-h,1-i]/2+Max[t,u]/2
...
</code></pre>

<p>I create <code>2^N</code> different equation sets, where <code>N</code> is the number of Max statements, and try to solve them individually using gaussian elimination or something like that. That would be something like $O(2^N*n^3)$.</p>

<p>By considering disjoin cycles and other heuristics, I could perhaps get it a bit faster, but I would still only be able to solve very simple games.</p>

<p>Are you aware of any algorithms, deterministic or approximate, that could make the above problem feasible for 30-50 or maybe even more Max statements?</p>

<p><strong>Update:</strong></p>

<ul>
<li>Each equation is a simple linear combination of variables, constants and Max/Mins of two (or more) variables. The number of terms in each equation is constant</li>
<li>It is known, that there is an unique solution {a,b,c,...}</li>
<li>All variables are fractions in <code>(0,1)</code>.</li>
</ul>

<p>I can reduce the system by using <code>Max[a,b] = (a+b-|a-b|)/2</code> and Snowie showed how to eliminate <code>Max[a,b]</code> by adding two inequalities and a binary variable. The complexity still seams to be <code>O(2^N)</code>.</p>

CC BY-SA 3.0
2011-06-24T04:47:51.217Z
I suppose that we are talking about n variables and m equations.  The simplest case is where every equation is a linear function of min/max of variables, although it seems that this examples requires handling also min/max of linear functions of variables -- or some restricted subset of these?
Noam
CC BY-SA 3.0
2011-06-24T07:47:34.930Z
You are right, n variables, n equations. Each equation is a simple linear combination of variables, constants and Max/Mins of two (or more) variables. The number of terms in each equation is constant.
Thomas Ahle
CC BY-SA 3.0
2011-06-24T07:51:45.473Z
It is also known, that there is one unique solution for {a,b,c,...}.
Thomas Ahle
CC BY-SA 4.0
2021-01-03T10:34:30.030Z
If we have x=Max(0,y+α) so we have x=0 or x=y+α how can we write y?. Only Y=x-α or we add y=-α ???????Both????
Abla
<optimization><linear-programming><gt.game-theory>
Solving a Min/Max equation set
Thomas Ahle
# Solving a Min/Max equation set

(Asked by: username_0 on 2011-06-23)

In solving a certain game, I've ended up with a set of equalities like these:
a == Max[b,c]/2+Max[d,e]/2
b == Min[f,g]/2+Min[h,i]/2
...
o == (1-d)/2+r/2
p == (1-d)/2
q == s/2+1/2
r == Max[1-h,1-i]/2+Max[t,u]/2
...

I create 2^N different equation sets, where N is the number of Max statements, and try to solve them individually using gaussian elimination or something like that. That would be something like $O(2^N*n^3)$.
By considering disjoin cycles and other heuristics, I could perhaps get it a bit faster, but I would still only be able to solve very simple games.
Are you aware of any algorithms, deterministic or approximate, that could make the above problem feasible for 30-50 or maybe even more Max statements?
Update:

Each equation is a simple linear combination of variables, constants and Max/Mins of two (or more) variables. The number of terms in each equation is constant
It is known, that there is an unique solution {a,b,c,...}
All variables are fractions in (0,1).

I can reduce the system by using Max[a,b] = (a+b-|a-b|)/2 and Snowie showed how to eliminate Max[a,b] by adding two inequalities and a binary variable. The complexity still seams to be O(2^N).

**Tags:** optimization, linear-programming, gt.game-theory
> **Comments:**
> **username_1**: I suppose that we are talking about n variables and m equations.  The simplest case is where every equation is a linear function of min/max of variables, although it seems that this examples requires handling also min/max of linear functions of variables -- or some restricted subset of these?  
> **username_0**: You are right, n variables, n equations. Each equation is a simple linear combination of variables, constants and Max/Mins of two (or more) variables. The number of terms in each equation is constant.  
> **username_0**: It is also known, that there is one unique solution for {a,b,c,...}.  
> **username_2**: If we have x=Max(0,y+α) so we have x=0 or x=y+α how can we write y?. Only Y=x-α or we add y=-α ???????Both????  

---

## 2 answers

### Answer by username_3 on 2011-06-24. Score: 6 | Accepted answer

To follow up on Snowie's post:

For each term max(v1, v2) introduce a new variable $x\_i$, subject to the constraints $x\_i \geq v\_1, x \geq v\_2$

For each term min(v1,v2) introduce a variable $y\_i$ subject to $y\_i \leq v\_1, y\_i \leq v\_2$.

Next, minimize the linear constraint $l = \sum x\_i - \sum y\_i$
subject to the inequations $x \geq v, y \geq v$, the linear equations $0 \leq v \leq 1$, AND the original linear system of equations.

This is a linear program, hence solvable in polynomial time. As the number of such constraints is polynomial, the entire system is solved in polynomial time.

> **Comments:**
> **username_0**: Fantastic, this works like a charm.  
> **username_0**: Since my solution is unique the `0<=v<=1` inequalities aren't necessary.  
> **username_3**: In general, an equal number of constraints does not imply the solution is uniquely determined. Even generically, given $n$ possible min/max pairs, one can construct $2^n$ determined linear systems. Each has a real solution, which obeys the min/max constraints with probability $2^{-n}$. Hence one expects, generically, a single random solution in addition to the causal solution. (The actual number is Poisson distributed). So, you CANNOT discard the constraints $0 \leq v \leq 1$ and expect to solve uniquely  
> **username_4**: is the $0 \leq v \leq 1$ constraint required because all variables are fractions in (0,1)?  

---

### Answer by username_5 on 2011-06-24. Score: 2

Removing the min/max operations in your problem, you can write your problem in a standard mixed integer programming. If your problem contains $N$ min/max operations, then your problem can be solved in $O(2^N)$ time, ignoring polynomial factors.

The removal of the min/max operation is easy. For example, let us remove Max[b,c]. First, add a variable x such that x = Max[b,c], and replace Max[b,c] with x. The relation x = Max[b,c] can be written as the following inequalities adding another binary variable y (i.e, y=0 or y=1):  
x >= b  
x >= c  
x <= by + c(1-y)  
You can remove the min operations in a similar way, and you'll obtain a standard mixed integer programming formulation.

> **Comments:**
> **username_5**: This answer assumes that all variables in your problem can be fractional (non-integer) values.  If the assumption is not true, ignore this answer.  
> **username_0**: The variables are all fractions in `(0,1)`, so that should be fine. Do you recon that this `O(2^N)` mixed interger solution is faster than just creating `2^N` different equation sets, where each Min/Max has been chosen?  
> **username_5**: @Thomas: Now I understand your problem.  From the theoretical point of view, I don't think my MIP solution is faster than your idea.  However, if you really want to solve your problem in practice, then it is worth trying to use MIP solvers (such as CPLEX) to solve my MIP formulation, because MIP solvers utilize various efficient heuristics.  
> **username_0**: You hear about MIP solers solving systems with thousands of variables. Do you think it would do better than a simple solution here?  

---

