2
$\begingroup$

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})$

$\endgroup$
4
  • 2
    $\begingroup$ May I ask you in which context you have met such a system ? $\endgroup$
    – Jean Marie
    Commented Sep 7, 2016 at 12:45
  • 1
    $\begingroup$ I would be happy that you answer my question. Besides, could you give me numerical values for the constants in order that I can test a solution with Matlab ? $\endgroup$
    – Jean Marie
    Commented Sep 7, 2016 at 23:24
  • $\begingroup$ @JeanMarie Context is this problem, approached analytically. Apart from the original data matrix, I created an auxiliary distance matrix, and set its first column to the first data column. The next column $(a, b ... e)$ is to be determined, while $(y_a ... y_e)$ is the current column, and $(x_a ... x_e)$ are the original data values, corresponding to the next column. $\endgroup$
    – BoLe
    Commented Sep 8, 2016 at 11:29
  • 1
    $\begingroup$ Thank you very much for your answer. Meanwhile I have checked that my approach using linear programming was thorough by writing the corresponding Matlab program and run it successfuly on many examples. I make now an edit to my answer in order you understand it. @Abstraction $\endgroup$
    – Jean Marie
    Commented Sep 8, 2016 at 21:05

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is a clever little scheme, quite fast too. I'm accepting your answer because its implementation is the simplest. $\endgroup$
    – BoLe
    Commented Sep 10, 2016 at 16:28
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I'm looking for something with lower time-complexity, the problem I mentioned latter has much bigger dimensionality. $\endgroup$
    – BoLe
    Commented Sep 10, 2016 at 14:27
1
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ In this approach, there are constraints like $\epsilon_1 = 0 \vee \epsilon_2 = 0$. $\endgroup$ Commented Sep 7, 2016 at 11:46
  • $\begingroup$ @Abstraction You are perfectly right, if we are looking for an exact solution. If we are not sure, in a first step, that there exist an exact solution, one could run the program, and see how far we are from an exact solution (engineer's approach...). Otherwise, we should take these constraints into account in the objective function for example by maximizing $a+b+c+d+e-\sum_k \epsilon_k$ (the 13 I had incorporated at first was silly...) (I dont see how they could be taken into account as added constraints because of the "or" connective). $\endgroup$
    – Jean Marie
    Commented Sep 7, 2016 at 12:16
  • $\begingroup$ @Abstraction You may have seen that I have taken your remark into account. I look forward for testing my approach with Matlab. Have you tested yours ? $\endgroup$
    – Jean Marie
    Commented Sep 7, 2016 at 23:26
  • $\begingroup$ Yes, it works (wrote a program and tested for several sets of values around $100$). Also, updated my solution with estimate of the number of iterations required. $\endgroup$ Commented Sep 8, 2016 at 10:14
  • $\begingroup$ @Abstraction I am happy that your solution works. As I have said upwards, mine also works and I am relieved... I almost completely rewrote the presentation with inequalities instead of equalities + the corresponding Matlab program. It would be interesting to check that, on the same set of values for $x_a,y_a,$ etc... the two methods give the same solution set. It is almost certain. $\endgroup$
    – Jean Marie
    Commented Sep 8, 2016 at 22:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .