This paper addresses a general class of capacity planning problems under uncertainty, which arises, for example, in semiconductor tool purchase planning. Using a scenario tree to model the evolution of the uncertainties, we develop a multi-stage stochastic integer programming formulation for the problem. In contrast to earlier two-stage approaches, the multi-stage model allows for revision … Read more
Multi-leader-follower games arise when modeling competition between two or more dominant firms and lead in a natural way to equilibrium problems with equilibrium constraints (EPECs). We examine a variety of nonlinear optimization and nonlinear complementarity formulations of EPECs. We distinguish two broad cases: problems where the leaders can cost-differentiate and problems with price-consistent followers. We … Read more
We present mixed integer linear programming models that are robust in the face of uncertain traffic demands known to lie in a certain polyhedron for the problem of dense wavelength division multiplexing network routing and provisioning at minimal cost. We investigate the solution of the problem in a set of numerical experiments for two models … Read more
Working with an integer bilinear programming formulation of a one-dimensional cutting-stock problem, we develop an ILP-based local-search heuristic. The ILPs holistically integrate the master and subproblem of the usual price driven pattern-generation paradigm, resulting in a unified model that generates new patterns in situ. We work harder to generate new columns, but we are guaranteed … Read more
We study a problem faced by a major beverage producer. The company produces and distributes several brands to various customers from its regional distributors. For some of these brands, most customers do not have enough demand to justify full pallet shipments. Therefore, the company decided to design a number of mixed or “rainbow” pallets so … Read more
Several ‘tubechallenges’ have been attempted on the London Underground network, often gaining vast press coverage. The most famous of them consists of trying to travel to all 275 stations of the London Underground network (known as ‘the tube’) in the shortest possible time. In this article we examine how Operational Research can assist potential record-breakers, … Read more
We study a single-machine sequencing problem with both release dates and deadlines to minimize the total weighted completion time. We propose a branch-and-bound algorithm for this problem. The algorithm exploits an effective lower bound and a dynamic programming dominance technique. As a byproduct of the lower bound, we have developed a new algorithm for the … Read more
Dynamic programming, branch-and-bound, and constraint programming are the standard solution principles for finding optimal solutions to machine scheduling problems. We propose a new hybrid optimization framework that integrates all three methodologies. The hybrid framework leads to powerful solution procedures. We demonstrate our approach through the optimal solution of the single-machine total weighted completion time scheduling … Read more
New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer … Read more
In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results … Read more