System of equations involving min

Question

Does some scheme exist to solve this seemingly simple system of equations involving minimum operation? Although every symbol should be a positive integer, I put the five variables $a, b, c, d, e$ in bold, other symbols represent constants.

$\mathbf{a} = x_a + min(y_a, \mathbf{b})$

$\mathbf{b} = x_b + min(y_b, \mathbf{a}, \mathbf{c})$

$\mathbf{c} = x_c + min(y_c, \mathbf{b}, \mathbf{d})$

$\mathbf{d} = x_d + min(y_d, \mathbf{c}, \mathbf{e})$

$\mathbf{e} = x_e + min(y_e, \mathbf{d})$

Answer 1

Solution (UPD): Suppose no more than one $x_\imath = 0$ (non-degenerate case). Then at least one of the $\min$ clauses evaluates to $y_\imath$. Otherwise we would have: $$a = x_a + b \\ b = x_b + \min(x_a+b, c) = x_b + c \\ ... \\ e = x_e + x_d + e > e$$ Likewise, if for some letter $\imath$, $\imath = x_\imath + y_\imath$ then for a "neighbour" letter $\jmath$ either $\jmath = x_\jmath + \imath$, $\jmath = x_\jmath + y_\jmath$ or one of the letters $k$ after it also has its $\min$ clause evaluate to $y_k$. Now let's take initial values $\imath_0 = x_\imath + y_\imath$ and start the same iterations as in "old solution" below. After each iteration, at least one variable gets the correct value assigned so no more than $4$ iterations are needed. "Old solution" below requires no more than $5$ iterations for similar reasons.

Old solution: Even for two variables, analytical answer is rather long, so here's the method to find a solution iteratively instead.

1. Let $y_{min} = \min(y_a,...,y_e)$.
2. If $\forall \imath\, x_\imath = 0$ (degenerated case) then $a=b=...=e=k, k \in [0,y_{min}]$
3. Let $a_0=b_0 = ... = e_0 = y_{min}$, then iteratively $$a_{n+1} = x_a + \min(y_a,b_n)\\ b_{n+1} = x_b + \min(y_b,a_{n+1},c_n)\\ c_{n+1} = x_c + \min(y_c,b_{n+1},d_n)\\ d_{n+1} = x_d + \min(y_d,c_{n+1},e_n)\\ e_{n+1} = x_e + \min(y_e,d_{n+1})$$ until we arrive to a solution (if more than one $x_\imath$ equals $0$, there may be several solutions)

Unfortunately I can't provide a strict proof this works, it's purely geometric reasoning: each equality corresponds to two or three hyperplanes; conditions of form $0 \le a \le x_a + min(y_a,b)$ describe a convex volume where point of maximal $a+b+...+e$ is a solution. The method "hops" between facets of this volume, reaching the solution in a finite number of steps.

Answer 2

A brute force solution would be to successively replace the $\min$s by each of their arguments, solve the corresponding linear system and check compatibility with the hypothesis (expressing that the chosen argument is indeed the smallest).

In this case, this leads to the resolution of $108$ systems :-(

One of them is

$\mathbf{a} = x_a + y_a\\ \mathbf{b} = x_b + y_b\\ \mathbf{c} = x_c + y_c\\ \mathbf{d} = x_d + y_d\\ \mathbf{e} = x_e + y_e$

provided that

$y_a\le x_b + y_b\\ y_b\le x_a + y_a, x_c + y_c\\ y_c\le x_b + y_b, x_d + y_d\\ y_d\le x_c + y_c, x_e + y_e\\ y_e\le x_d + y_d.$

Answer 3

Use linear programming (https://en.wikipedia.org/wiki/Linear_programming).

The solution(s) of this problem will be obtained under the 2+3+3+3+2=13 following constraints $$(C) \ \ \begin{cases} a \leq x_a+y_a\\ a \leq x_a+b\\ b \leq x_b+y_b\\ b \leq x_b+a\\ b \leq x_b+c\\ \cdots \\e \leq x_e+d\end{cases}$$

Which can be put under the form:

$$\tag{1}\left(\begin{array}{rrrrr} 1&0&0&0&0\\ 1&-1&0&0&0\\ 0&1&0&0&0\\ -1&1&0&0&0\\ 0&1&-1&0&0\\ 0&0&1&0&0\\ 0&-1&1&0&0\\ 0&0&1&-1&0\\ 0&0&0&1&0\\ 0&0&-1&1&0\\ 0&0&0&1&-1\\ 0&0&0&0&1\\ 0&0&0&-1&1\end{array}\right) \ \ \left(\begin{array}{c} a\\b\\c\\d\\e \end{array}\right) \ \leq \ \left(\begin{array}{l}x_a+y_a\\x_a\\x_b+y_b\\x_b\\x_b\\x_c+y_c\\x_c\\x_c\\x_d+y_d\\x_d\\x_d\\x_e+y_e\\x_e\end{array}\right)$$

That we will describe as being of the form:

$$\tag{2}AX \leq B$$

A possible objective function such as

$$\text{Maximize} \ \ a+b+c+d+e=(1 \ 1 \ 1 \ 1 \ 1)\left(\begin{array}{c} a\\b\\c\\d\\e \end{array}\right) \ \ \text{under constraints (1).}$$

or, in a synthetized form:

$$\tag{3} \text{Maximize} \ \ F^T X \ \ \text{under constraint} \ \ AX \leq B.$$

Here is a Matlab program that implements what has been said before (see comments below) for a particular set of constraints (We stick to notations used in (3)):

xa=6;ya=49;
xb=1;yb=39;
xc=41;yc=44;
xd=5;yd=20;
xe=13;ye=41;
A= [1,0,0,0,0
1,-1,0,0,0
0,1,0,0,0
-1,1,0,0,0
0,1,-1,0,0
0,0,1,0,0
0,-1,1,0,0
0,0,1,-1,0
0,0,0,1,0
0,0,-1,1,0
0,0,0,1,-1
0,0,0,0,1
0,0,0,-1,1];
B=[xa+ya,xa,xb+yb,xb,xb,xc+yc,xc,xc,xd+yd,xd,xd,xe+ye,xe]';
F=[-ones(1,5)]';
x=linprog(F,A,B,[],[],zeros(1,5),Inf*ones(1,5))

The solution $(a,b,c,d,e)=(46,40,66,25,38)$ found by this program verifies the constraints:

$$\begin{cases} a = 6 & + & min(49, b)\\ b = 1 & + & min(39, a, c)\\ c = 41 & + & min(44, b, d)\\ d = 5 & + & min(20, c, e)\\ e = 13 & + & min(41, d)\end{cases}$$

Comment 1 : One may wonder why coefficients $f=(1,1,1,1,1)$ of the objective function as described in (3) have a minus sign : it is because Matlab minimizes the objective function instead of maximizing it.

Comment 2 : The meaning of the different parameters of function linprog are naturel for the first 3, the fourth and fifth (equal to void lists) mean that there no equality constraints, the sixth and seventh parameters are, resp. the lower bounds (all zeros) and upper bounds (all at $+\infty$) expressing the fact that the domains of values taken by $a,b,c,d,e$ is $(0,+\infty)$.