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

Question

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 1

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

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.

Answer 3

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