<p>This problem is strongly reminiscent of <a href="http://en.wikipedia.org/wiki/Optimal_stopping">"Optimal stopping"</a> of stochastic processes.  These are frequently solved by dynamic programming.  References even to this specialized literature are extensive, due to its applications in decision theory and finance.</p>

CC BY-SA 2.5
2010-10-11T15:11:27.407Z
2010-10-11T15:11:27.407Z
whuber
<p>Without further examples, it's hard to suggest what one might do. But for these kinds of problems, it's often possible to apply an alternating optimization paradigm where you:</p>

<ol>
<li>Fix x and optimize for n</li>
<li>Fix n and optimize for x</li>
<li>repeat till convergence</li>
</ol>

<p>In certain settings depending on G and the feasible region, this can yield an optimal solution (for example, if you're measuring the distance between two convex polygons), but in general, it's hard to get anything except a local optimum. </p>

<p><strong>Update:</strong> </p>

<p>Based on the OP's clarification, I think a different direction might be more useful. What you're describing begins to sound like a lagrange relaxation of the constrained version of the problem (with a fixed budget). One example of this is a facility-location problem where you want to open facilities to "serve" locations, and while adding more facilities reduces the service cost, it costs more to open each one. There are also variants of this (the buy-at-bulk problem) where the cost for opening more "facilities" is a concave function. I don't understand the stochastic aspects of the problem though. </p>

CC BY-SA 2.5
2010-10-12T04:26:36.960Z
Once we have the expected waiting times, we can ignore the stochastic nature of the problem. But your suggestion is an interesting one.
user1725
CC BY-SA 2.5
2010-10-11T07:18:13.580Z
2010-10-12T04:07:04.313Z
2010-10-12T04:07:04.313Z
Suresh Venkat
<p>You need to clarify how "$x$ in some feasible region" is described analytically. The constraint $n \geq 1$ is usually called a "bound constraint". So if your "feasible region" for $x$ has the form $\ell \leq x \leq u$ you are in the realm of bound-constrained optimization. If there are conditions of the form $Ax=b$, you are in <em>linearly-constrained optimization</em>. You can narrow down further what precise area you are in based on the structure of your objective function $\sum G(x,n)$ (e.g., is it a sum of linear terms, quadratic terms, squares of linear terms, convex, concave, neither, etc.) There are many different methods out there for all categories.</p>

<p>You will find quite a bit of information at <a href="http://www.neos-guide.org/NEOS" rel="nofollow">http://www.neos-guide.org/NEOS</a>. Check the Wiki and the Optimization Software Guide. Check also the Decision Tree for Optimization Software (google it, it's one of the first results at University of Arizona; I can't post more than one hyperlink.)</p>

CC BY-SA 2.5
2010-12-28T18:13:00.137Z
2010-12-28T18:13:00.137Z
Dominique
<p><strong>minimize/maximize</strong> $\displaystyle \sum_{i=0}^{f(n)} G(x,n)$
s.t. $n \ge 1$ and $x$ in some feasible region</p>

<p>The decision variables are $x$ (a vector) and $n$ (a scalar).
How is this type of optimization problem classified? 
Has it been studied? Any references?</p>

<p>Here is an example of how an unconstrained version of the problem arises:</p>

<p><em><strong>"Optimizing capacity of buses, K, on a bus route"</em></strong></p>

<ul>
<li>The bus route is a loop. One point on
the loop is designated the “bus
station,” the only place passengers
can get on the bus.</li>
<li>Passengers can get off the bus at any
point on the bus route (other than
the bus station).</li>
<li>By the time a bus returns to the bus
station, all of its passengers will
have gotten off.</li>
<li>Passengers arrive by a Poisson
process with rate lambda (per hour). </li>
<li>A bus cannot take off from the bus
station until it has K passengers on
board.</li>
<li>There are N buses that operate on the
one route. When a bus arrives at the
bus station, it waits in line behind
buses that are already there. It’s a
FIFO system where the first bus in
line gets first K arriving
passengers, and so on…  </li>
<li>When a passenger arrives at the
station, s/he gets on the first bus
in line and waits until enough
passengers have gotten on the bus to
make a total of K passengers before
the bus takes off. Passengers get on
the bus in a FIFO manner as well.</li>
<li>The waiting time for a passenger is
the length of time from when that
passenger arrived at the bus station
until a bus with that passenger on
board takes off.</li>
<li>The waiting time for a bus is the
length of time from when the bus
arrives at the station until it has K
passengers on board, at which point
it takes off.  </li>
<li>It is assumed that the “loading” of
passengers takes zero time.  </li>
<li>Also, it takes C(K) time for buses to
travel the length of the bus route. This is a function of K because there is time lost for each passenger that is dropped off.</li>
</ul>

<p><strong>What is the expected waiting time for passengers? For buses?</strong></p>

<p>The <strong>optimization</strong> aspect is as follows. Bus drivers want to make the most amount of money in an hour. The higher K is, the more money a bus driver makes per trip on the bus route, but the number of trips per hour goes down. There is a monetary cost (to bus drivers) for each minute that a passenger waits at the stop for a bus (as in loss of goodwill). So the objective function is dependent on both the expected waiting time of buses (which determines how much money buses make per hour) and the expected waiting time of passengers.</p>

<p>I was able to get an expression for the expected waiting time of buses and it is of the form:</p>

<p><strong>E[Waiting time for a bus]</strong> = $\displaystyle\sum_{j=0}^{KN} \frac{KN-j}{\lambda}\frac{(\lambda C(K))^j}{j!}e^{-\lambda C(K)}$</p>

<p><strong>E[Waiting time for a passenger] = ??</strong></p>

<p>I have not been able to get an expression for the waiting time of passengers, but I suspect it will also have the upper bound of summation as some function of K.</p>

CC BY-SA 2.5
2010-10-11T07:16:10.933Z
it would be helpful if you had an example of this kind of framework ?
Suresh Venkat
CC BY-SA 2.5
2010-10-12T02:45:45.017Z
Let me give another example of where this would seem to arise (if I understand correctly).  Consider a generalized version of the art gallery problem where we seek to minimize the number of cameras placed but in which we remove the requirement that guards lie on vertices. In this setting, we may want to minimize the number of possible placement locations considered as well as the number of guards, leading to a sum over a variable number of terms.
Anand Kulkarni
CC BY-SA 2.5
2010-10-12T04:03:41.627Z
that begins to sound more like a facility-location-style problem
Suresh Venkat
<ds.algorithms><cg.comp-geom><optimization>
Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation?
user1725
# Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation?

(Asked by: username_0 on 2010-10-11)

**minimize/maximize** $\displaystyle \sum\_{i=0}^{f(n)} G(x,n)$
s.t. $n \ge 1$ and $x$ in some feasible region

The decision variables are $x$ (a vector) and $n$ (a scalar).
How is this type of optimization problem classified?
Has it been studied? Any references?

Here is an example of how an unconstrained version of the problem arises:

***"Optimizing capacity of buses, K, on a bus route"***

* The bus route is a loop. One point on
  the loop is designated the “bus
  station,” the only place passengers
  can get on the bus.
* Passengers can get off the bus at any
  point on the bus route (other than
  the bus station).
* By the time a bus returns to the bus
  station, all of its passengers will
  have gotten off.
* Passengers arrive by a Poisson
  process with rate lambda (per hour).
* A bus cannot take off from the bus
  station until it has K passengers on
  board.
* There are N buses that operate on the
  one route. When a bus arrives at the
  bus station, it waits in line behind
  buses that are already there. It’s a
  FIFO system where the first bus in
  line gets first K arriving
  passengers, and so on…
* When a passenger arrives at the
  station, s/he gets on the first bus
  in line and waits until enough
  passengers have gotten on the bus to
  make a total of K passengers before
  the bus takes off. Passengers get on
  the bus in a FIFO manner as well.
* The waiting time for a passenger is
  the length of time from when that
  passenger arrived at the bus station
  until a bus with that passenger on
  board takes off.
* The waiting time for a bus is the
  length of time from when the bus
  arrives at the station until it has K
  passengers on board, at which point
  it takes off.
* It is assumed that the “loading” of
  passengers takes zero time.
* Also, it takes C(K) time for buses to
  travel the length of the bus route. This is a function of K because there is time lost for each passenger that is dropped off.

**What is the expected waiting time for passengers? For buses?**

The **optimization** aspect is as follows. Bus drivers want to make the most amount of money in an hour. The higher K is, the more money a bus driver makes per trip on the bus route, but the number of trips per hour goes down. There is a monetary cost (to bus drivers) for each minute that a passenger waits at the stop for a bus (as in loss of goodwill). So the objective function is dependent on both the expected waiting time of buses (which determines how much money buses make per hour) and the expected waiting time of passengers.

I was able to get an expression for the expected waiting time of buses and it is of the form:

**E[Waiting time for a bus]** = $\displaystyle\sum\_{j=0}^{KN} \frac{KN-j}{\lambda}\frac{(\lambda C(K))^j}{j!}e^{-\lambda C(K)}$

**E[Waiting time for a passenger] = ??**

I have not been able to get an expression for the waiting time of passengers, but I suspect it will also have the upper bound of summation as some function of K.

**Tags:** ds.algorithms, cg.comp-geom, optimization

> **Comments:**
> **username_1**: it would be helpful if you had an example of this kind of framework ?  
> **username_2**: Let me give another example of where this would seem to arise (if I understand correctly).  Consider a generalized version of the art gallery problem where we seek to minimize the number of cameras placed but in which we remove the requirement that guards lie on vertices. In this setting, we may want to minimize the number of possible placement locations considered as well as the number of guards, leading to a sum over a variable number of terms.  
> **username_1**: that begins to sound more like a facility-location-style problem  

---

## 3 answers

### Answer by username_3 on 2010-10-11. Score: 5

This problem is strongly reminiscent of ["Optimal stopping"](http://en.wikipedia.org/wiki/Optimal_stopping) of stochastic processes. These are frequently solved by dynamic programming. References even to this specialized literature are extensive, due to its applications in decision theory and finance.


---

### Answer by username_1 on 2010-10-11. Score: 3

Without further examples, it's hard to suggest what one might do. But for these kinds of problems, it's often possible to apply an alternating optimization paradigm where you:

1. Fix x and optimize for n
2. Fix n and optimize for x
3. repeat till convergence

In certain settings depending on G and the feasible region, this can yield an optimal solution (for example, if you're measuring the distance between two convex polygons), but in general, it's hard to get anything except a local optimum.

**Update:**

Based on the OP's clarification, I think a different direction might be more useful. What you're describing begins to sound like a lagrange relaxation of the constrained version of the problem (with a fixed budget). One example of this is a facility-location problem where you want to open facilities to "serve" locations, and while adding more facilities reduces the service cost, it costs more to open each one. There are also variants of this (the buy-at-bulk problem) where the cost for opening more "facilities" is a concave function. I don't understand the stochastic aspects of the problem though.

> **Comments:**
> **username_0**: Once we have the expected waiting times, we can ignore the stochastic nature of the problem. But your suggestion is an interesting one.  

---

### Answer by username_4 on 2010-12-28. Score: 2

You need to clarify how "$x$ in some feasible region" is described analytically. The constraint $n \geq 1$ is usually called a "bound constraint". So if your "feasible region" for $x$ has the form $\ell \leq x \leq u$ you are in the realm of bound-constrained optimization. If there are conditions of the form $Ax=b$, you are in *linearly-constrained optimization*. You can narrow down further what precise area you are in based on the structure of your objective function $\sum G(x,n)$ (e.g., is it a sum of linear terms, quadratic terms, squares of linear terms, convex, concave, neither, etc.) There are many different methods out there for all categories.

You will find quite a bit of information at <http://www.neos-guide.org/NEOS>. Check the Wiki and the Optimization Software Guide. Check also the Decision Tree for Optimization Software (google it, it's one of the first results at University of Arizona; I can't post more than one hyperlink.)


---

