Knowledge that Transforms

The weapon-target assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. This problem consists of optimally assigning n weapons to m targets so that the total expected survival value of the targets after all the engagements is minimal. The WTA problem can be formulated as a nonlinear integer programming problem and is known to be NP-complete. No exact methods exist for the WTA problem that can solve even small-size problems (for example, with 20 weapons and 20 targets). Although several heuristic methods have been proposed to solve the WTA problem, due to the absence of exact methods, no estimates are available on the quality of solutions produced by such heuristics. In this paper, we suggest integer programming and network flow-based lower-bounding methods that we obtain using a branch-and-bound algorithm for the WTA problem. We also propose a network flow-based construction heuristic and a very large-scale neighborhood (VLSN) search algorithm. We present computational results of our algorithms, which indicate that we can solve moderately large instances (up to 80 weapons and 80 targets) of the WTA problem optimally and obtain almost optimal solutions of fairly large instances (up to 200 weapons and 200 targets) within a few seconds.

We consider the dynamic pricing problem of a monopolist firm in a market with repeated interactions, where demand is sensitive to the firm’s pricing history. Consumers have memory and are prone to human decision-making biases and cognitive limitations. As the firm manipulates prices, consumers form a reference price that adjusts as an anchoring standard based on price perceptions. Purchase decisions are made by assessing prices as discounts or surcharges relative to the reference price in the spirit of prospect theory. We prove that optimal pricing policies induce a perception of monotonic prices, whereby consumers always perceive a discount, respectively surcharge, relative to their expectations. The effect is that of a skimming or penetration strategy. The firm’s optimal pricing path is monotonic on the long run, but not necessarily at the introductory stage. If consumers are loss averse, we show that optimal prices converge to a constant steady-state price, characterized by a simple implicit equation; otherwise, the optimal policy cycles. The range of steady states is wider the more loss averse consumers are. Steady-state prices decrease with the strength of the reference effect and with customers’ memory, all else equal. Offering lower prices to frequent customers may be suboptimal, however, if these are less sensitive to price changes than occasional buyers. If managers ignore such long-term implications of their pricing strategy, the model indicates that they will systematically price too low and lose revenue. Our results hold under very general reference dependent demand models.

Assortment planning at a retailer entails both selecting the set of products to be carried and setting inventory levels for each product. We study an assortment planning model in which consumers might accept substitutes when their favorite product is unavailable. We develop an algorithmic process to help retailers compute the best assortment for each store. First, we present a procedure for estimating the parameters of substitution behavior and demand for products in each store, including the products that have not been previously carried in that store. Second, we propose an iterative optimization heuristic for solving the assortment planning problem. In a computational study, we find that its solutions, on average, are within 0.5% of the optimal solution. Third, we establish new structural properties (based on the heuristic solution) that relate the products included in the assortment and their inventory levels to product characteristics such as gross margin, case-pack sizes, and demand variability. We applied our method at Albert Heijn, a supermarket chain in The Netherlands. Comparing the recommendations of our system with the existing assortments suggests a more than 50% increase in profits.

In this paper, we introduce an approach for constructing uncertainty sets for robust optimization using new deviation measures for random variables termed the forward and backward deviations. These deviation measures capture distributional asymmetry and lead to better approximations of chance constraints. Using a linear decision rule, we also propose a tractable approximation approach for solving a class of multistage chance-constrained stochastic linear optimization problems. An attractive feature of the framework is that we convert the original model into a second-order cone program, which is computationally tractable both in theory and in practice. We demonstrate the framework through an application of a project management problem with uncertain activity completion time.

Most previous Nash-Cournot models of competition among electricity generators have assumed smooth demand (price) functions, facilitating computation and proofs of existence and uniqueness. However, nonsmooth demand functions are an important feature of real power markets due, for example, to price caps and generator recognition of transmission constraints that limit exports. A more general model of Nash-Cournot competition on networks is proposed that accounts for these features by including (1) concave piecewise-linear demand curves and (2) joint constraints that include variables from other generating companies within the profit maximization problems for individual generators. The piecewise demand curves imply, in general, a nonmonotone multivalued variational inequality problem. Thus, for instance, imposition of a price cap can destroy the uniqueness properties found in previous models, so that distinct solutions can yield different sets of profits for market participants. The joint constraints turn the equilibrium problem into a quasi-variational inequality, which also can yield multiple solutions. The formulation poses computational challenges that can cause Lemke’s algorithm to fail; a restricted formulation is proposed that can be solved by that algorithm.

The Capacitated m-Ring-Star Problem (CmRSP) is the problem of designing a set of rings that pass through a central depot and through some transition points and/or customers, and then assigning each nonvisited customer to a visited point or customer. The number of customers visited and assigned to a ring is bounded by an upper limit: the capacity of the ring. The objective is to minimize the total routing cost plus assignment costs. The problem has practical applications in the design of urban optical telecommunication networks. This paper presents and discusses two integer programming formulations for the CmRSP. Valid inequalities are proposed to strengthen the linear programming relaxation and are used as cutting planes in a branch-and-cut approach. The procedure is implemented and tested on a large family of instances, including real-world instances, and the good performance of the proposed approach is demonstrated.

We combine mixed-integer linear programming (MILP) and constraint programming (CP) to solve an important class of planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. Tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). We solve problems in which the objective is to minimize cost, makespan, or total tardiness. We obtain significant computational speedups, of several orders of magnitude for the first two objectives, relative to the state of the art in both MILP and CP. We also obtain better solutions and bounds for problems than cannot be solved to optimality.

The focus of this “OR framing paper” is to introduce the operations research (OR) community to the need for new mathematical modeling of an influenza pandemic and its control. By reviewing relevant history and literature, one key concern that emerges relates to how a population’s heterogeneity may affect disease progression. Another is to explore within a modeling framework “social distancing” as a disease progression control method, where social distancing refers to steps aimed at reducing the frequency and intensity of daily human-to-human contacts. To depict social contact behavior of a heterogeneous population susceptible to infection, a nonhomogeneous probabilistic mixing model is developed. Partitioning the population of susceptibles into subgroups, based on frequency of daily human contacts and infection propensities, a stylistic difference equation model is then developed depicting the day-to-day evolution of the disease. This simple model is then used to develop a preliminary set of results. Two key findings are (1) early exponential growth of the disease may be dominated by susceptibles with high human contact frequencies and may not be indicative of the general population’s susceptibility to the disease, and (2) social distancing may be an effective nonmedical way to limit and perhaps even eradicate the disease. Much more decision-focused research needs to be done before any of these preliminary findings may be used in practice.