How to solve such an optimization problem efficiently？?

Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation?

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

• Answer:

  This problem is strongly reminiscent of 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.