Knowledge that Transforms

The World Health Organization (WHO) recommends which strains of influenza to include in each year’s vaccine to countries around the globe. The current WHO strategy attempts to match the vaccine strains with the expected upcoming epidemic strains, a strategy we refer to as the follow policy. The recently proposed antigenic distance hypothesis suggests that vaccine efficacy can be enhanced by taking into account the antigenic histories of vaccinees. To assess the potential benefit of history-based vaccination, we formulate the annual vaccine-strains selection problem as a stochastic dynamic program using the theory of shape space, which maps each vaccine and epidemic strain into a point in multidimensional space. Computational results show that a near-optimal policy can be derived by approximating the entire antigenic history by a single reduced historical strain, and then solving the multiperiod problem myopically, as a series of single-period problems. The modest suboptimality of the follow policy, together with our current inability to quantitatively link the model’s objective function (a measure of cross-reactivity) with actual vaccine efficacy, leads us to recommend the continued use of the follow policy.

We present a new multiseasonal, multiyear, natural gas market equilibrium model based on the concept of a competitive equilibrium involving the market participants: producers, storage reservoir operators, peak gas operators, pipeline operators, marketers, and consumers. The first three classes are depicted as price-takers consistent with perfect competition. The pipeline operations are described with regulated tariffs, but also involve “congestion pricing” as a mechanism to allocate scarce pipeline capacity. The marketers are price-takers in all markets except in sales to consumers, in which they compete as Nash-Cournot players. Finally, consumers are described by demand curves for each of the four sectors: residential, commercial, industrial, and electric power. We show that the equilibrium model is an instance of a mixed nonlinear complementarity problem (NCP) and provide sufficient detail not generally seen in previous complementarity models of natural gas. The NCP formulation is derived from considering the Karush-Kuhn-Tucker optimality conditions of the optimization problems faced by these participants. Under mild conditions, we show that this NCP has a solution, and under additional reasonable conditions, we show that the market prices are unique. We also validate the model on a representative sample network with nine market participants and three seasons, using four scenarios.

Optimal solutions to Markov decision problems may be very sensitive with respect to the state transition probabilities. In many practical problems, the estimation of these probabilities is far from accurate. Hence, estimation errors are limiting factors in applying Markov decision processes to real-world problems. We consider a robust control problem for a finite-state, finite-action Markov decision process, where uncertainty on the transition matrices is described in terms of possibly nonconvex sets. We show that perfect duality holds for this problem, and that as a consequence, it can be solved with a variant of the classical dynamic programming algorithm, the “robust dynamic programming” algorithm. We show that a particular choice of the uncertainty sets, involving likelihood regions or entropy bounds, leads to both a statistically accurate representation of uncertainty, and a complexity of the robust recursion that is almost the same as that of the classical recursion. Hence, robustness can be added at practically no extra computing cost. We derive similar results for other uncertainty sets, including one with a finite number of possible values for the transition matrices. We describe in a practical path planning example the benefits of using a robust strategy instead of the classical optimal strategy; even if the uncertainty level is only crudely guessed, the robust strategy yields a much better worst-case expected travel time.

In biology, the protein structure alignment problem answers the question of how similar two proteins are. Proteins with strong physical similarities in their tertiary (folded) structure often have similar functions, so understanding physical similarity could be a key to developing protein-based medical treatments. One of the models for protein structure alignment is the maximum contact map overlap (CMO) model. The CMO model of protein structure alignment can be cast as a maximum clique problem on an appropriately defined graph. We exploit properties of these protein-based maximum clique problems to develop specialized preprocessing techniques and show how they can be used to more quickly solve contact map overlap instances to optimality.

This paper presents a simple model to determine the location strategies of two retail firms planning to open a number of stores in a geographical market. Firms try to maximize their profit under a leader-follower type competition in which the number of stores is made endogenous by the introduction of fixed costs. A novel methodology is developed in which firms’ strategies are defined in terms of their location densities. This methodology leads to a model that is solvable analytically, and to several results on competitive location strategies. First, it is shown that if the follower decides to enter a market, he enters at least as strongly as the leader. Second, the leader can effectively deter entry even if she is severely cost-disadvantaged. However, in some cases the leader is better off by allowing the follower to enter the market. Third, the leader may also let the follower enter the market in some situations where she has a cost advantage. It is also shown that in situations where both firms enter the market, their location strategies are quite insensitive to model parameters.

Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large-scale integer programming. We outline and relate the approaches, and survey mainly recent contributions, not yet found in textbooks. We emphasize the growing understanding of the dual point of view, which has brought considerable progress to the column generation theory and practice. It stimulated careful initializations, sophisticated solution techniques for the restricted master problem and subproblem, as well as better overall performance. Thus, the dual perspective is an ever recurring concept in our “selected topics.”

We investigate the polyhedral structure of the lot-sizing problem with inventory bounds. We consider two models, one with linear cost on inventory, the other with linear and fixed costs on inventory. For both models, we identify facet-defining inequalities that make use of the inventory bounds explicitly and give exact separation algorithms. We also describe a linear programming formulation of the problem when the order and inventory costs satisfy the Wagner-Whitin nonspeculative property. We present computational experiments that show the effectiveness of the results in tightening the linear programming relaxations of the lot-sizing problem with inventory bounds and fixed costs.