0
$\begingroup$

I have a problem that involves finding a bottleneck. It appears to me to be a linear bottleneck assignment problem, but recognizing (and solving) such problems is far outside my area of expertise. If anyone can help, I would appreciate it.

My problem is this: I have a family of $n$ functions $f_i(x_i)$, where $x_i = a_i f_{i-1}(x_{i-1})$ for $i > 0$ and $a_i$ is a known constant. I wish to solve for $x_0$ subject to the constraint that each $f_i(x_i)$ has a (different) maximum value $M_i$ such that $0 \le f_i(x_i) \le M_i$. This then will tell me the values of all of the other $x_i$.

I am doing this within a computer program and can solve it iteratively, of course, but I prefer to solve it directly if I can feasibly do so. However, my efforts so far always seem to contain errors.

$\endgroup$
4
  • $\begingroup$ What assumptions do you have about your functions f_i. What is their domain? Are they particularly nice functions? $\endgroup$
    – Alex R.
    Sep 30, 2010 at 1:40
  • $\begingroup$ It seems to me that even in a very simple special case where all the functions are the same quadratic and all the $a_i$ are 1 and all the $M_i$ are equal, a tiny change in $x_0$ could lead to a huge change in, say, $x_{20}$ (keyphrase: sensitive dependence on initial conditions), making it pretty nearly impossible to find $x_0$ with any confidence. $\endgroup$ Sep 30, 2010 at 4:54
  • $\begingroup$ @Gerry Myerson: Yes, this seems to be much harder than a linear bottleneck assignment problem because it is anything but linear! $\endgroup$
    – Alex R.
    Sep 30, 2010 at 17:58
  • $\begingroup$ This isn't a bottleneck assignment problem (BAP) - linear or not. With a BAP, the bottleneck appears not in the constraints but in the objective function. It's not clear what your objective function is, nor does it appear that anything in your problem is actually being assigned. $\endgroup$ Oct 4, 2010 at 21:04

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.