3
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Noam
    Jun 24, 2011 at 4:47
  • $\begingroup$ 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. $\endgroup$
    – Thomas Ahle
    Jun 24, 2011 at 7:47
  • $\begingroup$ It is also known, that there is one unique solution for {a,b,c,...}. $\endgroup$
    – Thomas Ahle
    Jun 24, 2011 at 7:51
  • $\begingroup$ 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???? $\endgroup$
    – Abla
    Jan 3, 2021 at 10:34

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Fantastic, this works like a charm. $\endgroup$
    – Thomas Ahle
    Jun 24, 2011 at 15:47
  • $\begingroup$ Since my solution is unique the 0<=v<=1 inequalities aren't necessary. $\endgroup$
    – Thomas Ahle
    Jun 24, 2011 at 15:47
  • $\begingroup$ 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 $\endgroup$
    – David Harris
    Jun 24, 2011 at 16:56
  • $\begingroup$ is the $0 \leq v \leq 1$ constraint required because all variables are fractions in (0,1)? $\endgroup$
    – evan54
    Mar 18, 2018 at 22:29
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This answer assumes that all variables in your problem can be fractional (non-integer) values. If the assumption is not true, ignore this answer. $\endgroup$
    – Snowie
    Jun 24, 2011 at 5:22
  • $\begingroup$ 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? $\endgroup$
    – Thomas Ahle
    Jun 24, 2011 at 7:55
  • $\begingroup$ @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. $\endgroup$
    – Snowie
    Jun 24, 2011 at 8:15
  • $\begingroup$ You hear about MIP solers solving systems with thousands of variables. Do you think it would do better than a simple solution here? $\endgroup$
    – Thomas Ahle
    Jun 24, 2011 at 12:06

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.