Knowledge that Transforms

This paper presents an improved mixed-integer programming (MIP) model and effective solution strategies for the facility layout problem and is motivated by the work of Meller et al. (1999). This class of problems seeks to determine a least-cost layout of departments having various size and area requirements within a rectangular building, and it is challenging even for small instances. The difficulty arises from the disjunctive constraints that prevent departmental overlaps and the nonlinear area constraints for each department, which existing models have failed to approximate with adequate accuracy. We develop several modeling and algorithmic enhancements that are demonstrated to produce more accurate solutions while also decreasing the solution effort required. We begin by deriving a novel polyhedral outer approximation scheme that can provide as accurate a representation of the area requirements as desired. We also design alternative methods for reducing problem symmetry, evaluate the performance of several classes of valid inequalities, explore the construction of partial convex hull representations for the disjunctive constraints, and investigate judicious branching variable selection priority schemes. The results indicate a substantial increase in the accuracy of the layout produced, while at the same time providing a dramatic reduction in computational effort. In particular, three previously unsolved test problems from the literature for which Meller et al.'s algorithm terminated prematurely after 24 cpu hours of computation (on a SUN Ultra 2 workstation with 390 MB RAM) with respective optimality gaps of 10.14%, 26.45%, and 40%, have been solved to exact optimality with reasonable effort using our proposed approach.

This paper presents a modeling framework for analyzing competition between multiple firms that each possess a mixture of hydroelectric and thermal generation resources. Based upon the concept of a Cournot oligopoly with a competitive fringe, the model characterizes the Cournot equilibrium conditions of a multiperiod hydrothermal scheduling problem. Using data from the western United States electricity market, this framework is implemented as a mixed linear complementarity model. The results show that some firms may find it profitable to allocate considerably more hydro production to off-peak periods then they would under perfect competition. This strategy is a marked contrast to the optimal hydroschedules that would arise if no firms were acting strategically. These results highlight the need to explicitly consider profit-maximizing behavior when examining the impact of regulatory and environmental policies on electricity market outcomes.

We study strategic capacity planning in the semiconductor industry. Working with a major US semiconductor manufacturer on the configuration of their worldwide production facilities, we identify two unique characteristics of this problem as follows: (1) wafer demands and manufacturing capacity are both main sources of uncertainty, and (2) capacity planning must consider the distinct viewpoints from marketing and manufacturing. We formulate a multi-stage stochastic program with demand and capacity uncertainties. To reconcile the marketing and manufacturing perspectives, we consider a decomposition of the planning problem resembling decentralized decision-making. We develop recourse approximation schemes representing different decentralization schemes, which vary in information requirements and complexity. We show that it is possible to arrive at near optimal solutions (within 6.5%) with information decentralization while using a fraction (16.2%) of the computer time.

A standard problem in operations literature is optimal stocking of substitutable products. We consider a consumer-driven substitution problem with an arbitrary number of products under both centralized inventory management and competition. Substitution is modeled by letting the unsatisfied demand for a product flow to other products in deterministic proportions. We obtain analytically tractable solutions that facilitate comparisons between centralized and competitive inventory management under substitution. For the centralized problem we show that, when demand is multivariate normal, the total profit is decreasing in demand correlation.

The curse of dimensionality gives rise to prohibitive computational requirements that render infeasible the exact solution of large-scale stochastic control problems. We study an efficient method based on linear programming for approximating solutions to such problems. The approach “fits” a linear combination of pre-selected basis functions to the dynamic programming cost-to-go function. We develop error bounds that offer performance guarantees and also guide the selection of both basis functions and “state-relevance weights” that influence quality of the approximation. Experimental results in the domain of queueing network control provide empirical support for the methodology.

Certain aspects of traffic flow measurements imply the existence of a phase transition. Models known from chaos and fractals, such as nonlinear analysis of coupled differential equations, cellular automata, or coupled maps, can generate behavior which indeed resembles a phase transition in the flow behavior. Other measurements point out that the same behavior could be generated by geometrical constraints of the scenario. This paper looks at some of the empirical evidence, but mostly focuses on different modeling approaches. The theory of traffic jam dynamics is reviewed in some detail, starting from the well-established theory of kinematic waves and then veering into the area of phase transitions. One aspect of the theory of phase transitions is that, by changing one single parameter, a system can be moved from displaying a phase transition to not displaying a phase transition. This implies that models for traffic can be tuned so that they display a phase transition or not. This paper focuses on microscopic modeling, i.e., coupled differential equations, cellular automata, and coupled maps. The phase transition behavior of these models, as far as it is known, is discussed. Similarly, fluid-dynamical models for the same questions are considered. A large portion of this paper is given to the discussion of extensions and open questions, which makes clear that the question of traffic jam dynamics is, albeit important, only a small part of an interesting and vibrant field. As our outlook shows, the whole field is moving away from a rather static view of traffic toward a dynamic view, which uses simulation as an important tool.

In this paper we address the problem of finding the simulated system with the best (maximum or minimum) expected performance when the number of systems is large and initial samples from each system have already been taken. This problem may be encountered when a heuristic search procedure—perhaps one originally designed for use in a deterministic environment—has been applied in a simulation-optimization context. Because of stochastic variation, the system with the best sample mean at the end of the search procedure may not coincide with the true best system encountered during the search. This paper develops statistical procedures that return the best system encountered by the search (or one near the best) with a prespecified probability. We approach this problem using combinations of statistical subset selection and indifference-zone ranking procedures. The subset-selection procedures, which use only the data already collected, screen out the obviously inferior systems, while the indifference-zone procedures, which require additional simulation effort, distinguish the best from the less obviously inferior systems.