Economics Insights @ CBS

Applied mathematical programming problems are often approximations of larger, more detailed problems. One criterion to evaluate an approximating program is the magnitude of the difference between the optimal objective values of the original and the approximating program. The approximation we consider is variable aggregation in a convex program. Bounds are derived on the difference between the two optimal objective values. Previous results of Geoffrion and Zipkin are obtained by specializing our results to linear programming. Also, we apply our bounds to a convex transportation problem.

In continuous review models with a fixed delivery lag T, the state of the system is conveniently described by the net inventory position = (inventory on hand) plus (outstanding orders), in spite of most cost components depending on the actual inventory on hand. To relate these two inventory concepts one observes that the distribution of the inventory on hand at time t + T is determined by the inventory position at time t.

This paper presents methods for solving allocation problems that can be stated as convex knapsack problems with generalized upper bounds. Such bounds may express upper limits on the total amount allocated to each of several subsets of activities. In addition our model arises as a subproblem in more complex mathematical programs. We therefore emphasize efficient procedures to recover optimality when minor changes in the parameters occur from one problem instance to the next. These considerations lead us to propose novel data structures for such problems.