Optimizing the Societal Benefits of the Annual Influenza Vaccine: A Stochastic Programming Approach

O. Y. Özaltın, O. A. Prokopyev, A. J. Schaefer and M. S. Roberts. To appear in Operations Research (2010).

Seasonal influenza is a major public health concern, and the first line of defense is the flu shot. Antigenic drifts and the high rate of influenza transmission require annual updates to the flu shot composition. The World Health Organization recommends which flu strains to include in the annual vaccine based on surveillance and epidemiological analysis. There are two critical decisions regarding the flu shot design. One is its composition; currently, three strains constitute the flu shot, and they influence vaccine effectiveness. Another critical decision is the timing of the composition decisions, which affects the flu shot production. Both of these decisions have to be made under uncertainty long before the flu season starts. We quantify the trade offs involved through a multi-stage stochastic mixed-integer program that determines the optimal flu shot composition and its timing in a stochastic and dynamic environment. We incorporate risk-sensitivity through mean-risk models. Our results provide valuable insights for pressing policy issues.

Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides

O. Y. Özaltın, O. A. Prokopyev, A. J. Schaefer. To appear in Mathematical Programming (2010).

We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We propose a two-phase solution approach. The first phase constructs value functions of quadratic integer programs in both stages. The second phase solves the reformulation using a global branch-and-bound algorithm or a level-set approach. We derive some basic properties of value functions of quadratic integer programs and utilize them in our algorithms. We show that our approach can solve instances whose extensive forms are hundreds of orders of magnitude larger than the largest quadratic integer programming instances solved in the literature.

Supplementary Materials

Predicting the Solution Time of Branch-and-Bound Algorithms for Mixed-Integer Programs

O. Y. Özaltın, B. Hunsaker, A. J. Schaefer. To appear in INFORMS Journal on Computing (2010).

The most widely used progress measure for branch-and-bound (B&B) algorithms when solving mixed-integer programs (MIPs) is the MIP gap. We introduce a new progress measure that is often much smoother than the MIP gap. We propose a double exponential smoothing technique to predict the solution time of B&B algorithms. We evaluate the prediction method using three MIP solvers. We show that making accurate predictions of the solution time based on the new progress measure is possible for many MIP instances even in the early stages.

Supplementary Materials

The Bilevel Knapsack Problem with Stochastic Right-Hand Sides

O. Y. Özaltın, O. A. Prokopyev, A. J. Schaefer. Operations Research Letters, 38(4):328-333, 2010.

We introduce the bilevel knapsack problem with stochastic right-hand sides, and provide necessary and sufficient conditions for the existence of an optimal solution. When the leader's decisions can take only integer values, we present an equivalent two-stage stochastic programming reformulation with binary recourse. We develop a branch-and-cut algorithm for solving this reformulation, and a branch-and-backtrack algorithm for solving the scenario subproblems. Computational experiments indicate that our approach can solve large instances in a reasonable amount of time.

Senior Center Network Redesign Under Demand Uncertainty

with Michael P. Johnson and Andrew J. Schaefer                                                          (under review)

Senior centers offer a variety of services to facilitate independent living of older adults. In the U.S., increasing suburbanization and aging of suburban residents necessitate reconfiguring senior services. In response, we propose a two-echelon network of senior centers. We formulate a two-stage stochastic facility location/allocation model with mixed-integer recourse to design such a two-echelon network across large study areas. We apply our model to Allegheny County, Pennsylvania, which has one of the oldest population in the U.S.

Supplementary Materials

Visualizing the Progress of Branch-and-Bound Algorithms

with Brady Hunsaker, Ted K. Ralphs and Oleg A. Prokopyev                                            (under review)

We present a suite of tools for visualizing the status and progress of branch-and-bound algorithms for mixed integer programs. By integrating these tools with the open-source codes CBC 1.01 (Forrest, 2007), SYMPHONY 5.1 (Ralphs, 2007), and GLPK 4.15 (Makhorin, 2007), we demonstrate the potential usefulness of visual representations in helping a user predict future progress of the algorithm or analyzing the algorithm's performance. We have also implemented a flexible toolkit, called the Branch and Cut Analysis Kit (BAK) that can be used in conjunction with any instrumented solver to create visual representations in the form of image files. The kit will be made available under an open-source license.

Supplementary Materials