Solve for $\alpha$ if solution exists: $\min(r_1, s_1 \alpha_1) + \min(r_2, s_2\alpha_1) = d_1$, where $r_1,r_2,s_1,s_2,d_1$ are integer constants.

One way seems to be enumerate all possible outcomes, e.g., $r_1 + s_2\alpha_1 = d_1$. However, for a larger problem ($\sum_{i=1}^{k} \min(r_i,s_i\alpha)$), enumerating all options becomes exponential. Is there a better way to reformulate this problem?

  • 2
    $\begingroup$ 1. Over what domain? Over $\mathbb{R}$ (the real numbers)? Over $\mathbb{Q}$ (the rational numbers)? $\mathbb{Z}$ (the integers)? The integers modulo $p$ or modulo $n$? Something else? 2. What do you mean by "a larger problem"? Please state the actual problem you want solved explicitly. By "larger", do you mean the values of $r_1,r_2,s_1,s_2,d_1$; or do you mean the number of $\min$-terms on the left-hand-side of the equation? Can you edit the question to clarify these points? $\endgroup$ – D.W. Mar 3 '17 at 1:13

I assume the generalization you are thinking of is the following:

Given value $d$, and values $s_i$ and $r_i$ for $i = 1,2,...,k$, find (if possible) an $\alpha$ such that $$\sum_{i = 1}^k\min(r_i, s_i\alpha) = d$$

Consider the expression $\min(r_i, s_i\alpha)$. This expression is sometimes equal to $r_i$ and sometimes equal to $s_i\alpha$, with a threshold between these two behaviors at $\alpha = \frac{r_i}{s_i}$.

Then consider the $k$ thresholds of this form for the $k$ different $\min(r_i, s_i\alpha)$ expressions. These thresholds separate the number line into $k+1$ sections. In each section, the behavior of each $\min(r_i, s_i\alpha)$ expression is known. Therefore, we can rewrite the expression $\sum_{i = 1}^k\min(r_i, s_i\alpha)$ for each section without the $\min$s. Then in each section we get an expression of the form $a+b\alpha = d$ which we can solve for $\alpha$; if in any section we find a value $\alpha$ that is both a solution to the equation in that section and a value within the section of the number line, then that $\alpha$ solves the whole problem.

Another way of thinking about this is in terms of your idea of trying every combination of which expressions the $\min$s evaluate to. If you do it by brute force, you have to try exponentially many cases, but using the idea of these threshold values it is possible to narrow down the possibilities to just $k+1$ cases.


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.