This paper presents a new bidirectional search algorithm to solve the shortest path problem. The new algorithm uses an iterative deepening technique with a consistent heuristic to improve lower bounds on path costs. The new algorithm contains a novel technique of filtering nodes to significantly reduce the memory requirements. Computational experiments on the pancake problem, sliding tile problem, and Rubik’s cube show that the new algorithm uses significantly less memory and executes faster than A* and other state-of-the-art bidirectional algorithms. Summary of Contribution: Quickly solving single-source shortest path problems on graphs is important for pathfinding applications and is a core problem in both artificial intelligence and operations research. This paper attempts to solve large problems that do not easily fit into the available memory of a desktop computer, such as finding the optimal shortest set of moves to solve a Rubik’s cube, and solve them faster than existing algorithms.

In this paper, we discuss the one-machine scheduling problem with release and delivery times with the minimum makespan objective. Both heuristics and branch-and-bound algorithms have been formulated for the problem. One such branch-and-bound algorithm solves the problem and a variation that requires a delay between the completion of one job and the start of another (delayed precedence constraints). This paper analyzes key components of this branch-and-bound algorithm and proposes an improved heuristic to be used in conjunction with a different search strategy. Computational experiments demonstrate that the modifications lead to substantial improvements in running time and number of iterations on the one-machine problem instances both with and without delayed precedence constraints.

This paper proves several new properties of the Meet in the Middle (MMe) bidirectional heuristic search algorithm when applied to graphs with unit edge costs. Primarily, it is shown that the length of the first path discovered by MMe never exceeds the optimal length by more than one and that if the length of the first path found is odd, then it must be optimal. These properties suggest that the search strategy should emphasize finding a complete path as soon as possible. Computational experiments demonstrate that fully exploiting these new properties can decrease the number of nodes expanded by anywhere from twofold to over tenfold.

Branch-and-price algorithms combine a branch-and-bound search with an exponentially sized LP formulation that must be solved via column generation. Unfortunately, the standard branching rules used in branch and bound for integer programming interfere with the structure of the column generation routine; therefore, most such algorithms employ alternate branching rules to circumvent this difficulty. This paper shows how a zero-suppressed binary decision diagram can be used to solve the pricing problem in a branch-and-price algorithm for the graph coloring problem, even in the presence of constraints imposed by branching decisions. This approach facilitates a much more direct solution method and can improve convergence of the column generation subroutine.

Branch-and-price algorithms for the graph coloring problem use an exponentially sized independent set-based integer programming formulation to produce usually tight lower bounds to enable more aggressive pruning in the branch-and-bound tree. One major problem inherent to any branch-and-price scheme for graph coloring is that to avoid destroying the pricing problem structure during column generation, difficult-to-implement branching rules that modify the underlying graph must be used. This paper proposes an alternative branching strategy that does not change the graph to solve the pricing problem but rather modifies the search tree to require fewer calls to difficult instances of the pricing problem. This approach, called wide branching, generates many subproblems at each node in the branch-and-price tree; this significantly reduces the length of any path through the search tree. In contrast, traditional deep branching only creates two subproblems per node, assigning a variable to either 0 or 1. A delayed branching procedure is introduced that prevents the branching factor at any particular node from growing too large in this scheme. Finally, computational results are presented that show the wide branching strategy to be competitive with state-of-the-art graph coloring solvers.

The United States pediatric vaccine manufacturing market is analyzed using a static Bertrand oligopoly pricing model that characterizes oligopolistic interactions between asymmetric firms in a homogeneous multiple product market. Firms satisfy demand by appropriately pricing and selling its given set of bundles, where each bundle contains one or more products. In analyzing the pediatric vaccine market, a bundle is a vaccine, where each vaccine contains one or more immunogenic antigens. Consumers seek to purchase at least one of each antigen at an overall minimum cost. Demand is captured by defining a weighted set covering optimization problem, with the weights (prices) controlled by firms engaged in Bertrand competition. A repeated game version of the model enables multiple interactions between firms, allowing examination of tacit collusion. An iterative improvement algorithm is defined that constructs a pure strategy Nash equilibrium (some in the limiting sense) for the static game. Sufficient conditions for the existence of pure strategy Nash equilibria are provided, indicating that this class of games always yields at least one pure strategy equilibrium. Practical results of the pediatric vaccine market analysis follow from the difference in the repeated game equilibrium prices between two combination vaccines, Pediarix® and Pentacel®. Assuming the manufacturers of these vaccines agree to share the market equally with respect to volume, the equilibrium prices from the repeated game indicate a price difference of $0.86, whereas the difference in price between Pediarix® and Pentacel® for contract prices ending March 31, 2010 was $2.74. Interestingly, the subsequent public sector vaccine price list (contract prices ending March 31, 2011) shows a price difference of $0.95, with the price of Pentacel® actually reduced from the previous year—an unusual occurrence. The results presented in this paper suggest that a smaller price difference between these two important combination vaccines is appropriate, which is what occurred. In general, such results could serve to inform both manufacturers and purchasers on the appropriate pricing of combination vaccines, given the existence of a reasonable set of collusive agreements.

Matching is widely used in the estimation of treatment effects in observational studies. However, the matching paradigm may be too restrictive in many cases because exact matches often do not exist in the available data. One mechanism for overcoming this issue is to relax the requirement of exact matching on some or all of the covariates (attributes that may affect the response to treatment) to a requirement of balance on the covariate distributions for the treatment and control groups. The balance optimization subset selection (BOSS) model can be used to identify a control group featuring optimal covariate balance. This paper explores the relationship between the matching and BOSS models and shows how BOSS subsumes matching. Complexity and approximation results are presented for the resulting models. Computational results demonstrate some of the important trade-offs between matching and BOSS. Data, as supplemental material, are available at http://dx.doi.org/10.1287/ijoc.2013.0583 . There is a video associated with this paper. Click here to view the Video Overview . To save the file, right click and choose “Save Link As” from the menu.

A network simplex algorithm is described for the minimum-cost network flow problem on a generalized network, with the additional constraint that there exist sets of arcs that must carry equal amounts of flow. This problem can be modeled as a linear programming problem and solved using the standard simplex algorithm. However, because of the structure of the problem, more efficient algorithms are possible that solve the problem by operating directly on the network itself. One such algorithm is described that leads to improved asymptotic performance per iteration over the standard simplex algorithm, as long as the number of side constraints is small relative to the size of the network. Computational results are given comparing this algorithm to CPLEX's primal simplex solver on randomly generated graphs.

We present a new exact algorithm for the assembly line balancing problem. The algorithm finds and verifies the optimal solution for every problem in the combined benchmarks of Hoffmann, Talbot, and Scholl in less than one-half second per problem, on average, including one problem that has remained open for over 10 years. The previous best-known algorithm is able to solve 257 of the 269 benchmarks. The new algorithm is based on a branch-and-bound method that uses memory to eliminate redundant subproblems.

Passenger screening is a critical component of aviation security systems. This paper introduces the multistage sequential passenger screening problem (MSPSP), which models passenger and carry-on baggage screening operations in an aviation security system with the capability of dynamically updating the perceived risk of passengers. The passenger screening operation at an airport terminal is subdivided into multiple screening stages, with decisions made to assign each passenger to one of several available security classes at each such stage. Each passenger's assessed threat value (initially determined by an automated passenger prescreening system) is updated after the passenger proceeds through each screening stage. The objective of MSPSP is to maximize the total security of all passenger screening decisions over a fixed time period, given passenger perceived risk levels and security device performance parameters. An optimal policy for screening passengers in MSPSP is obtained using optimal sequential assignment theory. A Monte Carlo simulation-based heuristic is presented and compared with stochastic sequential assignment and feedback control algorithms. Computational analysis of a two-stage security system provides an assessment of the total security performance.

This article describes the motivation, development, and implementation of a software tool, www.vaccineselection.com, introduced to assist health care professionals and public health administrators in managing pediatric vaccine purchase decisions and making economically sound formulary choices. The tool integrates general operations research methodologies with specific local practice choices to solve for the lowest overall cost set of vaccines required to immunize a child according to the Recommended Childhood Immunization Schedule. A description of the tool's capabilities is provided. RESULTS on the use of the software tool are reported and discussed.

This paper introduces and studies an optimization problem related to the alias method for discrete random-variate generation. The alias method is an efficient method to generate random variates from a discrete probability distribution. The efficiency of the alias method can be improved by designing the alias table such that the expected number of computations that must be performed per value generated is minimized. The problem of optimizing the construction of the alias table is proven to be strongly NP-hard, even if either of two variations of the alias method relaxing the alias-table-generation restrictions are used. Integer-programming formulations describing these three optimization problems are presented, and insights regarding necessary optimality criteria and relationships among their optimal solutions are discussed.

This paper introduces simultaneous generalized hill-climbing (SGHC) algorithms as a framework for simultaneously addressing a set of related discrete optimization problems using heuristics. Many well-known heuristics can be embedded within the SGHC algorithm framework, including simulated annealing, pure local search, and threshold accepting (among others). SGHC algorithms probabilistically move between a set of related discrete optimization problems during their execution according to a problem probability mass function. When an SGHC algorithm moves between discrete optimization problems, information gained while optimizing the current problem is used to set the initial solution in the subsequent problem. The information used is determined by the practitioner for the particular set of problems under study. However, effective strategies are often apparent based on the problem description. SGHC algorithms are motivated by a discrete manufacturing process design optimization problem (that is used throughout the paper to illustrate the concepts needed to implement a SGHC algorithm). This paper discusses effective strategies for three examples of sets of related discrete optimization problems (a set of traveling salesman problems, a set of permutation flow shop problems, and a set of MAX 3-satisfiability problems). Computational results using the SGHC algorithm for randomly generated problems for two of these examples are presented. For comparison purposes, the associated generalized hill-climbing (GHC) algorithms are applied to the individual discrete optimization problems in the sets. These computational results suggest that near-optimal solutions can be reached more effectively and efficiently using SGHC algorithms.

This paper presents a new gradient estimator for the steady-state expected sojourn (system) time in a nonpreemptive priority queueing system. The estimator uses the concept of a phantom system, together with the basic ideas in harmonic gradient estimation, to develop a single simulation run estimator, termed the phantom harmonic gradient (PHG) estimator. The estimator is shown to be strongly consistent and strongly consistent in the average sense as the sample size grows. An upper bound for the variance of the PHG estimator is presented. This bound is used to show that under mild conditions, the variance of the PHG estimator tends to zero as both the number of phantom systems and the sample size approach infinity. A variance-reduction technique that simultaneously uses both common and antithetic random numbers is presented. Computational results on several nonpreemptive queueing systems illustrate the effectiveness of the method and show that common and antithetic random numbers can be used simultaneously to reduce the variance of the phantom harmonic gradient estimator.

This article presents an empirical approach that demonstrates a theoretical connection between (information theoretic) entropy measures and the finite-time performance of the simulated annealing algorithm. The methodology developed leads to several computational approaches for creating problem instances useful in testing and demonstrating the entropy/performance connection: use of generic configuration spaces, polynomial transformations between NP-hard problems, and modification of penalty parameters. In particular, the computational results show that higher entropy measures are associated with superior finite-time performance of the simulated annealing algorithm.

Sensitivity analysis of steady state simulation outputs typically involves estimating gradients. This paper presents convergence results for the harmonic gradient estimators. Sufficient conditions are formulated that validate the interchange of the derivative and the expectation operators for these estimators. The relationship between these estimators and finite differences gradient estimators is discussed. In particular, the harmonic estimators are shown to be variations of finite differences gradient estimators. Exploiting the orthogonal property of the trigonometric basis results in harmonic gradient estimation procedures requiring two simulation runs. Computational results with various queueing system simulation models are included to compare and illustrate the different estimators. These results suggest that the harmonic gradient estimation procedures requiring two simulation runs may be an alternative to forward (symmetric) finite differences gradient estimation procedures with common random number streams requiring p + 1 (2p) simulation runs. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.