Solving a Min/Max equation set - Theoretical Computer Science Stack Exchange most recent 30 from cstheory.stackexchange.com 2022-01-20T10:14:14Z https://cstheory.stackexchange.com/feeds/question/7095 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cstheory.stackexchange.com/q/7095 3 Solving a Min/Max equation set Thomas Ahle https://cstheory.stackexchange.com/users/4310 2011-06-23T20:28:59Z 2021-01-03T10:34:30Z <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> https://cstheory.stackexchange.com/questions/7095/-/7097#7097 2 Answer by Snowie for Solving a Min/Max equation set Snowie https://cstheory.stackexchange.com/users/3825 2011-06-24T05:15:44Z 2011-06-24T05:15:44Z <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> https://cstheory.stackexchange.com/questions/7095/-/7102#7102 5 Answer by David Harris for Solving a Min/Max equation set David Harris https://cstheory.stackexchange.com/users/5538 2011-06-24T12:53:22Z 2011-06-24T12:53:22Z <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>