<p>I am given constants $c_{i,j}$ as inputs.  I want to find values for the variables $x_i$ that satisfy a system of equations, where each equation either takes the form</p>

<p>$$x_i = \max\{x_j + c_{i,j} : j \ne i\}$$</p>

<p>or the form</p>

<p>$$x_i = \min\{x_j + c_{i,j} : j \ne i\}.$$</p>

<p>Is there an efficient algorithm to test this system of equations for feasibility, and if feasible, find a solution?  Can this be solved using linear programming somehow?</p>

CC BY-SA 3.0
2017-09-21T21:31:58.700Z
You can use LaTeX here to typeset mathematics in a more readable way. See [here](https://cs.meta.stackexchange.com/questions/271/add-short-reference-for-latex-commands) for a short introduction.
D.W.
CC BY-SA 3.0
2017-09-22T07:01:10.500Z
My apologies/ Let me provide an example. 

I have 9 scalar constants that are all known and are inputs: a,b,c,d,e,f,g,h and i. 
 
I have five variables that I need to solve for them, X,Y,Z,S and T. These variables are locked in 5 equations:

X=max(a,S-b,T-c),

Y=max(d,S-e,T-f),

Z=max(g,S-h,T-i),

S=min(X+b,Y+e,Z+h),

T=min(X+c,Y+f,Z+i)
Ray
CC BY-SA 3.0
2017-09-22T20:37:07.607Z
Are you looking for a practical algorithm? Are you looking for the theoretical complexity? If a practical algorithm, about how large is the problem (how many variables)?  This can be expressed as an instance of integer linear programming, but that won't lead to any useful guarantees on worst-case running time (ILP can take exponential time to solve in the worst case).
D.W.
CC BY-SA 3.0
2017-09-22T20:37:49.487Z
Also, rather than trying to clarify in the comments, please edit the question to make it clear (and read well for someone who encounters it for the first time). Don't just add "edit: ...stuff", but revise the question. There is an 'edit' link under the question you can use to edit your post.  I've taken the opportunity to edit your question; check to see if it accurately represents your intent.
D.W.
CC BY-SA 3.0
2017-09-22T21:06:55.840Z
The problem is NP-complete, so you won't find faster than exponential algorithms.
Emil Jeřábek
CC BY-SA 3.0
2017-09-22T22:09:21.860Z
@EmilJeřábek, interesting.   Can you share the reduction?
D.W.
CC BY-SA 3.0
2017-09-25T15:28:29.263Z
For example, here is a reduction from CIRCUIT-SAT. Consider a circuit built from positive and negative literals $x_i,\overline{x_i}$ using AND and OR. We can represent it by a system of equations using variables $x_i$, $\overline{x_i}$, $t$, $f$ (standing for the constants true and false), and one variable per each node of the circuit. It includes the equations $t\ge f+1$ (i.e., $t=\max\{t,f+1\}$), $t=\max\{x_i,\overline{x_i}\}$, $f=\min\{x_i,\overline{x_i}\}$, $t=y$ where $y$ is the output node of the circuit, and one equation for each node of the circuit using max/min in place of OR/AND.
Emil Jeřábek
CC BY-SA 3.0
2017-09-27T07:59:26.630Z
@D.W., Thank you for editing the question and, yes that's the correct representation of my question
Ray
CC BY-SA 3.0
2017-09-27T08:01:47.710Z
@EmilJeřábek, thanks for the insight. Now I understand. I believe I am using a representation that's too complex for the original problem, and need to revisit to simplify.
Ray
CC BY-SA 3.0
2017-09-27T15:22:42.380Z
@EmilJeřábek, nice!  Thank you!  Seems like that answers the question; would you like to write it as an answer?  Nitpick: $t = \max\{t,f+1\}$ is not of the permitted form (take a look at the condition $j \ne i$ in the question, which prohibits $t$ from appearing on the right-hand-side if it appears on the left-hand-side), but I guess that $t = \max\{f+1\}$ would work just as well.
D.W.
<linear-programming>
Max and Min Equations with Linear Programing
Ray
# Max and Min Equations with Linear Programing

(Asked by: username_0 on 2017-09-20)

I am given constants $c\_{i,j}$ as inputs. I want to find values for the variables $x\_i$ that satisfy a system of equations, where each equation either takes the form

$$x\_i = \max\{x\_j + c\_{i,j} : j \ne i\}$$

or the form

$$x\_i = \min\{x\_j + c\_{i,j} : j \ne i\}.$$

Is there an efficient algorithm to test this system of equations for feasibility, and if feasible, find a solution? Can this be solved using linear programming somehow?

**Tags:** linear-programming
> **Comments:**
> **username_1**: You can use LaTeX here to typeset mathematics in a more readable way. See [here](https://cs.meta.stackexchange.com/questions/271/add-short-reference-for-latex-commands) for a short introduction.  
> **username_0**: My apologies/ Let me provide an example.   I have 9 scalar constants that are all known and are inputs: a,b,c,d,e,f,g,h and i.    I have five variables that I need to solve for them, X,Y,Z,S and T. These variables are locked in 5 equations:  X=max(a,S-b,T-c),  Y=max(d,S-e,T-f),  Z=max(g,S-h,T-i),  S=min(X+b,Y+e,Z+h),  T=min(X+c,Y+f,Z+i)  
> **username_1**: Are you looking for a practical algorithm? Are you looking for the theoretical complexity? If a practical algorithm, about how large is the problem (how many variables)?  This can be expressed as an instance of integer linear programming, but that won't lead to any useful guarantees on worst-case running time (ILP can take exponential time to solve in the worst case).  
> **username_1**: Also, rather than trying to clarify in the comments, please edit the question to make it clear (and read well for someone who encounters it for the first time). Don't just add "edit: ...stuff", but revise the question. There is an 'edit' link under the question you can use to edit your post.  I've taken the opportunity to edit your question; check to see if it accurately represents your intent.  
> **username_2**: The problem is NP-complete, so you won't find faster than exponential algorithms.  
> **username_1**: @EmilJeřábek, interesting.   Can you share the reduction?  
> **username_2**: For example, here is a reduction from CIRCUIT-SAT. Consider a circuit built from positive and negative literals $x_i,\overline{x_i}$ using AND and OR. We can represent it by a system of equations using variables $x_i$, $\overline{x_i}$, $t$, $f$ (standing for the constants true and false), and one variable per each node of the circuit. It includes the equations $t\ge f+1$ (i.e., $t=\max\{t,f+1\}$), $t=\max\{x_i,\overline{x_i}\}$, $f=\min\{x_i,\overline{x_i}\}$, $t=y$ where $y$ is the output node of the circuit, and one equation for each node of the circuit using max/min in place of OR/AND.  
> **username_0**: @D.W., Thank you for editing the question and, yes that's the correct representation of my question  
> **username_0**: @EmilJeřábek, thanks for the insight. Now I understand. I believe I am using a representation that's too complex for the original problem, and need to revisit to simplify.  
> **username_1**: @EmilJeřábek, nice!  Thank you!  Seems like that answers the question; would you like to write it as an answer?  Nitpick: $t = \max\{t,f+1\}$ is not of the permitted form (take a look at the condition $j \ne i$ in the question, which prohibits $t$ from appearing on the right-hand-side if it appears on the left-hand-side), but I guess that $t = \max\{f+1\}$ would work just as well.  

---

## 0 answers

