Search

In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear optimization problems. We first show that disjoint bilinear optimization problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, which enables us to apply robust optimization techniques to solve the resulting problems. To this end, a solution scheme based on a blending of three popular robust optimization techniques is proposed. For disjoint bilinear optimization problems with a polyhedral feasible region and a general convex feasible region, we show that, under mild regularity conditions, the convex relaxations of the original bilinear formulation and its two-stage robust reformulation obtained from a reformulation-linearization-based technique and linear decision rules, respectively, are equivalent. For generic bilinear optimization problems, the convex relaxations from the reformulation-linearization-based technique are generally tighter than the one from linear decision rules. Numerical experiments on bimatrix games, synthetic disjoint bilinear problem instances, and convex maximization problems demonstrate the efficiency and effectiveness of the proposed solution scheme. Summary of Contribution: Computing solutions for disjoint bilinear optimization problems are of much interest in real-life applications, yet they are, in general, computationally intractable. This paper proposes a computationally tractable approximation as well as a convergent algorithm to the optimal values of such problems. Extensive computational experiments on (i) (constrained) bimatrix games, (ii) synthetic disjoint bilinear problems, and (iii) convex maximization problems are conducted to demonstrate the effectiveness and efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a mixed-integer linear programming solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, we present the basic concept of having two parallel extensions, and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator), including an implementation of deterministic parallelization. Second, we discuss the difficulties in achieving a good performance that utilizes all resources on an actual computing environment, and the difficulties of performance evaluation of the parallel solvers. Third, we present a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions. Finally, we demonstrate the current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer nonlinear programs (MINLPs) in parallel. The online appendix is available at . [ABSTRACT FROM AUTHOR]

In this paper, we consider a variant of adaptive robust combinatorial optimization problems where the decision maker can prepare K solutions and choose the best among them upon knowledge of the true data realizations. We suppose that the uncertainty may affect the objective and the constraints through functions that are not necessarily linear. We propose a new exact algorithm for solving these problems when the feasible set of the nominal optimization problem does not contain too many good solutions. Our algorithm enumerates these good solutions, generates dynamically a set of scenarios from the uncertainty set, and assigns the solutions to the generated scenarios using a vertex p-center formulation, solved by a binary search algorithm. Our numerical results on adaptive shortest path and knapsack with conflicts problems show that our algorithm compares favorably with the methods proposed in the literature. We additionally propose a heuristic extension of our method to handle problems where it is prohibitive to enumerate all good solutions. This heuristic is shown to provide good solutions within a reasonable solution time limit on the adaptive knapsack with conflicts problem. Finally, we illustrate how our approach handles nonlinear functions on an all-or-nothing subset problem taken from the literature. Summary of Contribution: Our paper describes a new exact algorithm for solving adaptive robust combinatorial optimization problems when the feasible set of the nominal optimization problems does not contain too many good solutions. Its development relies on a progressive relaxation of the problem augmented with a row-and-column generation technique. Its efficient execution requires a reformulation of this progressive relaxation, coupled with dominance rules and a binary search algorithm. The proposed algorithm is amenable to exploiting the special structures of the problems considered as illustrated with various applications throughout the paper. A practical view is provided by the proposition of a heuristic variant. Our computational experiments show that our proposed exact solution method outperforms the existing methodologies and therefore pushes the computational envelope for the class of problems considered. [ABSTRACT FROM AUTHOR]

The subgame perfect equilibrium in stationary strategies (SSPE) is the most important solution concept in applications of stochastic games, making it imperative to develop efficient methods to compute an SSPE. For this purpose, this paper develops an interior-point differentiable path-following method (IPM), which establishes a connection between an artificial logarithmic barrier game and the stochastic game of interest by adding a homotopy variable. IPM brings several advantages over the existing methods for stochastic games. On the one hand, IPM provides a bridge between differentiable path-following methods and interior-point methods and remedies several issues of an existing homotopy method called the stochastic linear tracing procedure (SLTP). First, the starting stationary strategy profile can be arbitrarily chosen. Second, IPM does not need switching between different systems of equations. Third, the use of a perturbation term makes IPM applicable to all stochastic games rather than generic games only. Moreover, a well-chosen transformation of variables reduces the number of equations and variables by roughly one half. Numerical results show that the proposed method is more than three times as efficient as SLTP. On the other hand, the stochastic game can be reformulated as a mixed complementarity problem and solved by the PATH solver. We employ the proposed IPM and the PATH solver to compute SSPEs. Numerical results evince that for some stochastic games the PATH solver may fail to find an SSPE, whereas IPM is successful in doing so for all stochastic games, which confirms the reliability and stability of the proposed method. Summary of Contribution: This paper incorporates the interior-point methods into a differentiable path-following method for computing stationary equilibria for stochastic games. This novel method brings excellent computational advantages and remedies several issues with the existing methods for stochastic games. We prove the global convergence of the proposed method and employ this method to solve numerous randomly generated stochastic games with different scales. Numerical results further confirm the high efficiency, stability, and universality of this method for stochastic games. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The minimum connected dominating set (MCDS) problem consists of selecting a minimum set of vertices from an undirected graph, such that each vertex not in this set is adjacent to at least one of the vertices in it, and the subgraph induced by this vertex set is connected. This paper presents a fast vertex weighting (FVW) algorithm for solving the MCDS problem, which integrates several distinguishing features, such as a vertex weighting-based local search with tabu and perturbation strategies to help the search to jump out of the local optima, as well as a search space reduction strategy to improve the search efficiency. Computational experiments on four sets of 112 commonly used public benchmark instances, as well as 15 newly introduced sparse instances, show that FVW is highly competitive compared with the state-of-the-art algorithms in the literature despite its simplicity. FVW improves the previous best-known results for 20 large public benchmark instances while matching the best-known results for all but 2 of the remaining ones. Several ingredients of FVW are investigated to demonstrate the importance of the proposed ideas and techniques. Summary of Contribution: As a challenging classical NP-hard problem, the minimum connected dominating set (MCDS) problem has been studied for decades in the areas of both operations research and computer science, although there does not exist an exact polynomial algorithm for solving it. Thus, the new breakthrough on this classical NP-hard problem in terms of the computational results on classical benchmark instances is significant. This paper presents a new fast vertex weighting local search for solving the MCDS problem. Computational experiments on four sets of 112 commonly used public benchmark instances show that fast vertex weighting (FVW) is able to improve the previous best-known results for 20 large instances while matching the best-known results for all but 2 of the remaining instances. Several ingredients of FVW are also investigated to demonstrate the importance of the proposed ideas and techniques. [ABSTRACT FROM AUTHOR]

This paper studies the reliable uncapacitated facility location problem in which facilities are subject to uncertain disruptions. A two-stage distributionally robust model is formulated, which optimizes the facility location decisions so as to minimize the fixed facility location cost and the expected transportation cost of serving customers under the worst-case disruption distribution. The model is formulated in a general form, where the uncertain joint distribution of disruptions is partially characterized and is allowed to have any prespecified dependency structure. This model extends several related models in the literature, including the stochastic one with explicitly given disruption distribution and the robust one with moment information on disruptions. An efficient cutting plane algorithm is proposed to solve this model, where the separation problem is solved respectively by a polynomial-time algorithm in the stochastic case and by a column generation approach in the robust case. Extensive numerical study shows that the proposed cutting plane algorithm not only outperforms the best-known algorithm in the literature for the stochastic problem under independent disruptions but also efficiently solves the robust problem under correlated disruptions. The practical performance of the robust models is verified in a simulation based on historical typhoon data in China. The numerical results further indicate that the robust model with even a small amount of information on disruption correlation can mitigate the conservativeness and improve the location decision significantly. Summary of Contribution: In this paper, we study the reliable uncapacitated facility location problem under uncertain facility disruptions. The problem is formulated as a two-stage distributionally robust model, which generalizes several related models in the literature, including the stochastic one with explicitly given disruption distribution and the robust one with moment information on disruptions. To solve this generalized model, we propose a cutting plane algorithm, where the separation problem is solved respectively by a polynomial-time algorithm in the stochastic case and by a column generation approach in the robust case. The efficiency and effectiveness of the proposed algorithm are validated through extensive numerical experiments. We also conduct a data-driven simulation based on historical typhoon data in China to verify the practical performance of the proposed robust model. The numerical results further reveal insights into the value of information on disruption correlation in improving the robust location decisions. [ABSTRACT FROM AUTHOR]

With the rapid development of computing technology, using parallel computing to solve large-scale ranking-and-selection (R&S) problems has emerged as an important research topic. However, direct implementation of traditionally fully sequential procedures in parallel computing environments may encounter various problems. First, the scheme of all-pairwise comparisons, which is commonly used in fully sequential procedures, requires a large amount of computation and significantly slows down the selection process. Second, traditional fully sequential procedures require frequent communication and coordination among processors, which are also not efficient in parallel computing environments. In this paper, we propose three modifications on one classical fully sequential procedure, Paulson's procedure, to speed up its selection process in parallel computing environments. First, we show that if no common random numbers are used, then we can significantly reduce the computation spent on all-pairwise comparisons at each round. Second, by batching different alternatives, we show that we can reduce the communication cost among the processors, leading the procedure to achieve better performance. Third, to boost the procedure's final-stage selection, when the number of surviving alternatives is less than the number of processors, we suggest to sample all surviving alternatives to the maximal number of observations that they should take. We show that, after these modifications, the procedure remains statistically valid and is more efficient compared with existing parallel procedures in the literature. Summary of Contribution: Ranking and selection (R&S) is a branch of simulation optimization, which is an important area of operations research. In recent years, using parallel computing to solve large-scale R&S problems has emerged as an important research topic, and this research topic is naturally situated in the intersection of computing and operations research. In this paper, we consider how to improve a fully sequential R&S procedure, namely, Paulson's procedure, to reduce the high computational complexity of all-pairwise comparisons and the burden of frequent communications and coordination, so that the procedure is more suitable and more efficient in solving large-scale R&S problems using parallel computing environments that are becoming ubiquitous and accessible for ordinary users. The procedure designed in this paper appears more efficient than the ones available in the literature and is capable of solving R&S problems with over a million alternatives in a parallel computing environment with 96 processors. The paper also extended the theory of R&S by showing that the all-pairwise comparisons may be decomposed so that the computational complexity may be reduced significantly, which drastically improves the efficiency of all-pairwise comparisons as observed in numerical experiments. [ABSTRACT FROM AUTHOR]

Randomized decision making refers to the process of making decisions randomly according to the outcome of an independent randomization device, such as a dice roll or a coin flip. The concept is unconventional, and somehow counterintuitive, in the domain of mathematical programming, in which deterministic decisions are usually sought even when the problem parameters are uncertain. However, it has recently been shown that using a randomized, rather than a deterministic, strategy in nonconvex distributionally robust optimization (DRO) problems can lead to improvements in their objective values. It is still unknown, though, what is the magnitude of improvement that can be attained through randomization or how to numerically find the optimal randomized strategy. In this paper, we study the value of randomization in mixed-integer DRO problems and show that it is bounded by the improvement achievable through its continuous relaxation. Furthermore, we identify conditions under which the bound is tight. We then develop algorithmic procedures, based on column generation, for solving both single- and two-stage linear DRO problems with randomization that can be used with both moment-based and Wasserstein ambiguity sets. Finally, we apply the proposed algorithm to solve three classical discrete DRO problems: the assignment problem, the uncapacitated facility location problem, and the capacitated facility location problem and report numerical results that show the quality of our bounds, the computational efficiency of the proposed solution method, and the magnitude of performance improvement achieved by randomized decisions. Summary of Contribution: In this paper, we present both theoretical results and algorithmic tools to identify optimal randomized strategies for discrete distributionally robust optimization (DRO) problems and evaluate the performance improvements that can be achieved when using them rather than classical deterministic strategies. On the theory side, we provide improvement bounds based on continuous relaxation and identify the conditions under which these bound are tight. On the algorithmic side, we propose a finitely convergent, two-layer, column-generation algorithm that iterates between identifying feasible solutions and finding extreme realizations of the uncertain parameter. The proposed algorithm was implemented to solve distributionally robust stochastic versions of three classical optimization problems and extensive numerical results are reported. The paper extends a previous, purely theoretical work of the first author on the idea of randomized strategies in nonconvex DRO problems by providing useful bounds and algorithms to solve this kind of problems. [ABSTRACT FROM AUTHOR]

We study the chance-constrained bin packing problem, with an application to hospital operating room planning. The bin packing problem allocates items of random sizes that follow a discrete distribution to a set of bins with limited capacity, while minimizing the total cost. The bin capacity constraints are satisfied with a given probability. We investigate a big-M and a 0-1 bilinear formulation of this problem. We analyze the bilinear structure of the formulation and use the lifting techniques to identify cover, clique, and projection inequalities to strengthen the formulation. We show that in certain cases these inequalities are facet-defining for a bilinear knapsack constraint that arises in the reformulation. An extensive computational study is conducted for the operating room planning problem that minimizes the number of open operating rooms. The computational tests are performed using problems generated based on real data from a hospital. A lower-bound improvement heuristic is combined with the cuts proposed in this paper in a branch-and-cut framework. The computations illustrate that the techniques developed in this paper can significantly improve the performance of the branch-and-cut method. Problems with up to 1,000 scenarios are solved to optimality in less than an hour. A safe approximation based on conditional value at risk (CVaR) is also solved. The computations show that the CVaR approximation typically leaves a gap of one operating room (e.g., six instead of five) to satisfy the chance constraint. Summary of Contribution: This paper investigates a branch-and-cut algorithm for a chance-constrained bin packing problem with multiple bins. The chance-constrained bin packing provides a modeling framework for applied operations research problems, such as health care, scheduling, and so on. This paper studies alternative computational approaches to solve this problem. Moreover, this paper uses real data from a hospital operating room planning setting as an application to test the algorithmic ideas. This work, therefore, is at the intersection of computing and operations research. Several interesting ideas are developed and studied. These include a strengthened big-M reformulation, analysis of a bilinear reformulation, and identifying certain facet-defining inequalities for this formulation. This paper also gives a lower-bound generation heuristic for a model that minimizes the number of bins. Computational experiments for an operating room planning model that uses data from a hospital demonstrate the computational improvement and importance of the proposed approaches. The techniques proposed in this paper and computational experiments further enhance the interface of computing and operations research. [ABSTRACT FROM AUTHOR]

We address a dynamic covering location problem of an unmanned aerial vehicle base station (UAV-BS), in which the location sequence of a single UAV-BS in a wireless communication network is determined to satisfy data demand arising from ground users. This problem is especially relevant in the context of smart grid and disaster relief. The vertical movement ability of the UAV-BS and nonconvex covering functions in wireless communication restrict utilizing classical planar covering location approaches. Therefore, we develop new formulations to this emerging problem for a finite time horizon to maximize the total coverage. In particular, we develop a mixed-integer nonlinear programming formulation that is nonconvex in nature and propose a Lagrangean decomposition algorithm (LDA) to solve this formulation. Because of the high complexity of the problem, the LDA is still unable to find good local solutions to large-scale problems. Therefore, we develop a continuum approximation (CA) model and show that CA would be a promising approach in terms of both computational time and solution accuracy. Our numerical study also shows that the CA model can be a remedy to build efficient initial solutions for exact solution algorithms. Summary of Contribution: This paper addresses a facet of mixed integer nonlinear programming formulations. Dynamic facility location problems (DFLPs) arise in a wide range of applications. However, classical DFLPs typically focus on the two-dimensional spaces. Emerging technologies in wireless communication and some other promising application areas, such as smart grids, have brought new location problems that cannot be solved with classical approaches. For practical reasons, many research attempts to solve this new problem, especially by researchers whose primary research area is not OR, have seemed far from analyzing the characteristics of the formulations. Rather, solution-oriented greedy heuristics have been proposed. This paper has two main objectives: (i) to close the gap between practical and theoretical sides of this new problem with the help of current knowledge that OR possesses to solve facility location problems and (ii) to support the findings with an exhaustive computational study to show how these findings can be applied to practice. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The unit commitment problem with uncertainty is considered one of the most challenging power system scheduling problems. Different stochastic models have been proposed to solve the problem, but such approaches have yet to be applied in industry practice because of computational challenges. In practice, the problem is formulated as a deterministic model with reserve requirements to hedge against uncertainty. However, simply requiring a certain level of reserves cannot ensure power system reliability as the procured reserves may be nondispatchable because of transmission limitations. In this paper, we derive a set of feasibility cuts (constraints) for managing the unit commitment problem with uncertainty. These cuts eliminate unreliable scheduling solutions and reallocate reserves in the power system; they are induced by the extreme rays of a polyhedral dual cone. This paper shows that, with the proposed reformulation, the extreme rays of the dual cone can be characterized by combinatorial selections of transmission lines (arcs) and buses (nodes) of the power system. As a result, the cuts can then be characterized using engineering insights. The unit commitment problem with uncertainty is formulated as a deterministic model with the identified extreme ray feasibility cuts. Test results show that, with the proposed extreme ray feasibility cuts, the problem can be solved more efficiently, and the resulting scheduling decision is also more reliable. [ABSTRACT FROM AUTHOR]

This research proposes and analyzes new models for a stochastic resource allocation problem that arises in a variety of operations contexts. One of the primary contributions of the paper lies in providing a succinct, robust, and general model that can address a range of different risk-based objectives and cost assumptions under uncertainty. Although the model expression is relatively simple, it embeds a reasonably high degree of underlying complexity, as the analysis shows. In addition, in-depth analysis of the model, both in its general form and under various specific risk measures, uncovers some interesting and powerful insights regarding the problem trade-offs. Furthermore, this analysis leads to a highly efficient class of heuristic algorithms for solving the problem, which we demonstrate via numerical experimentation to provide close-to-optimal solutions. This computational benefit is a critical element for solving a class of broadly applicable larger problems for which our problem arises as a subproblem that requires repeated solution. This paper considers a single-resource allocation problem for multiple items with random, independent resource consumption values, known as the static stochastic knapsack problem (SSKP). Whereas the existing SSKP literature generally assumes a risk-neutral objective using an expected value approach, such an approach can maximize expected profit while admitting the possibility of very high losses in some unfavorable scenarios. Because of this, we consider two popular risk measures, conditional value-at-risk (CVaR) and a mean-standard deviation trade-off, in order to address risk within this problem class. Optimizing the trade-offs associated with these risk measures presents significant modeling and computational challenges. To address these challenges, we first provide mixed-integer linear programming models using a scenario-based approach, which can be exploited to provide exact solutions for discrete distributions. For general distributions, a sample average approximation method provides approximate solutions. We then propose a general mixed integer nonlinear optimization modeling approach for the special case of normally distributed resource requirements. This modeling approach incorporates a new class of normalized penalty functions that account for both the expected costs and risks associated with uncertainty, and it can be specialized to a broad class of risk measures, including CVaR and mean-standard deviation. Our results characterize key optimality properties for the associated continuous relaxation of the proposed general model and provide insights on valuable rank-ordering mechanisms for items with uncertain resource needs under different risk measures. For this broadly applicable case, we present a class of efficient and high-performing asymptotically optimal heuristic methods based on these optimality conditions. An extensive numerical study evaluates the efficiency and quality of the proposed solution methods, identifies optimal item selection strategies, and examines the sensitivity of the solution to varying levels of risk, excess weight penalty values, and knapsack capacity values. Summary of Contribution: This research proposes and analyzes new models for a stochastic resource allocation problem that arises in a variety of operations contexts. One of the primary contributions of the paper lies in providing a succinct, robust, and general model that can address a range of different risk-based objectives and cost assumptions under uncertainty. While the model expression is relatively simple, it embeds a reasonably high degree of underlying complexity, as the analysis shows. In addition, in-depth analysis of the model, both in its general form and under various specific risk measures, uncovers some interesting and powerful insights regarding the problem tradeoffs. Furthermore, this analysis leads to a highly efficient class of heuristic algorithms for solving the problem, which we demonstrate via numerical experimentation to provide close-to-optimal solutions. This computational benefit is a critical element for solving a class of broadly applicable larger problems for which our problem arises as a subproblem that requires repeated solution. [ABSTRACT FROM AUTHOR]

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed-form expression. In this paper, we use the lift-and-project framework introduced by Balas and Perregaard to provide the basis, and the reduce-and-split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed-integer cut and alternates between lift-and-project and reduce-and-split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce-and-split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods. [ABSTRACT FROM AUTHOR]

In recent years, with the rapid development of computing technology, developing parallel procedures to solve large-scale ranking and selection (R&S) problems has attracted a lot of research attention. In this paper, we take fixed-budget R&S procedure as an example to investigate potential issues of developing parallel procedures. We argue that to measure the performance of a fixed-budget R&S procedure in solving large-scale problems, it is important to quantify the minimal growth rate of the total sampling budget such that as the number of alternatives increases, the probability of correct selection (PCS) would not decrease to zero. We call such a growth rate of the total sampling budget the rate for maintaining correct selection (RMCS). We show that a tight lower bound for the RMCS of a broad class of existing fixed-budget procedures is in the order of k log k , where k is the number of alternatives. Then, we propose a new type of fixed-budget procedure, namely the fixed-budget knockout-tournament (F B K T) procedure. We prove that, in terms of the RMCS, our procedure outperforms existing fixed-budget procedures and achieves the optimal order, that is, the order of k. Moreover, we demonstrate that our procedure can be easily implemented in parallel computing environments with almost no nonparallelizable calculations. Last, a comprehensive numerical study shows that our procedure is indeed suitable for solving large-scale problems in parallel computing environments. History: Accepted by Bruno Tuffin, Area Editor for Simulation. Funding: Y. Zhong was supported by the National Natural Science Foundation of China [Grant 72101047]. L. J. Hong was supported by the National Natural Science Foundation of China [Grants 72091211 and 72161160340]. G. Jiang was supported by the National Natural Science Foundation of China [Grants 72121001 and 72171060]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1221. [ABSTRACT FROM AUTHOR]

Floating-point computations are quickly finding their way in the design of safety- and mission-critical systems, despite the fact that designing floating-point algorithms is significantly more difficult than designing integer algorithms. For this reason, verification and validation of floating-point computations are hot research topics. An important verification technique, especially in some industrial sectors, is testing. However, generating test data for floating-point intensive programs proved to be a challenging problem. Existing approaches usually resort to random or search-based test data generation, but without symbolic reasoning it is almost impossible to generate test inputs that execute complex paths controlled by floating-point computations. Moreover, because constraint solvers over the reals or the rationals do not natively support the handling of rounding errors, the need arises for efficient constraint solvers over floating-point domains. In this paper, we present and fully justify improved algorithms for the propagation of arithmetic IEEE 754 binary floating-point constraints. The key point of these algorithms is a generalization of an idea by B. Marre and C. Michel that exploits a property of the representation of floating-point numbers. [ABSTRACT FROM AUTHOR]

In the last decade, decision diagrams (DDs) have been the basis for a large array of novel approaches for modeling and solving optimization problems. Many techniques now use DDs as a key tool to achieve state-of-the-art performance within other optimization paradigms, such as integer programming and constraint programming. This paper provides a survey of the use of DDs in discrete optimization, particularly focusing on recent developments. We classify these works into two groups based on the type of diagram (i.e., exact or approximate) and present a thorough description of their use. We discuss the main advantages of DDs, point out major challenges, and provide directions for future work. [ABSTRACT FROM AUTHOR]

Multiperiod blending has a number of important applications in a range of industrial sectors. It is typically formulated as a nonconvex mixed integer nonlinear program (MINLP), which involves binary variables and bilinear terms. In this study, we first propose a reformulation of the constraints involving bilinear terms using lifting. We introduce a method for calculating tight bounds on the lifted variables calculated by aggregating multiple constraints. We propose valid constraints derived from the reformulation-linearization technique (RLT) that use the bounds on the lifted variables to further tighten the formulation. Computational results indicate our method can substantially reduce the solution time and optimality gap. Summary of Contribution: In this paper, we study the multiperiod blending problem, which has a number of important applications in a range of industrial sectors, such as refining, chemical production, mining, and wastewater management. Solving this problem efficiently leads to significant economic and environmental benefits. However, solving even medium-scale instances to global optimality remains challenging. To address this challenge, we propose a variable bound tightening algorithm and tightening constraints for multiperiod blending. Computational results show that our methods can substantially reduce the solution time and optimality gap. [ABSTRACT FROM AUTHOR]

We propose a general logic-based Benders decomposition (LBBD) for production planning problems with process configuration decisions. This family of problems appears in contexts where the machines are set up according to specific patterns, templates, or, in general, process configurations that allow for simultaneously producing products of different types. The problem requires determining feasible configurations for the machines and their corresponding production levels to fulfill the demand at the minimum total cost. The structure of this problem contains nonlinear constraints that link the number of units produced of each product with the used configurations and their production levels. We decompose the original problem into a master problem, where the configurations are determined, and a subproblem, where the production amounts are determined. This allows us to apply the LBBD technique to solve the problem using a standard LBBD implementation and a branch-and-check algorithm. LBBD enhancements through logic-based inequalities generated for subsets of products with common characteristics are proposed. Such inequalities represent a form of the subproblem relaxation added to the master problem during its resolution. In our computational experiments, we apply the proposed LBBD approaches to two different applications from the literature: cutting stock problems in the steel industry and a printing problem. Results show that the LBBD methods find optimal solutions much faster than the solution approaches in the literature and have a superior performance with respect to the number of instances solved to optimality and the solution quality. Summary of Contribution: In this work, we introduce a unified exact solution algorithm based on logic-based Benders decomposition to solve a class of integrated production planning problems that include process configuration decisions. We propose a general mathematical representation of the original integrated planning problem and logic-based Benders reformulations that can be applied to solve several problems within the studied class. Our implementation frameworks provide guidelines to practitioners in the field. The solution approaches in this paper together with the proposed methodological enhancements can be adapted to solve other integrated planning problems in a similar context, including the case when the original problem has a complex combinatorial and nonlinear structure. [ABSTRACT FROM AUTHOR]

In the bin-packing problem with minimum color fragmentation (BPPMCF), we are given a fixed number of bins and a collection of items, each associated with a size and a color, and the goal is to avoid color fragmentation by packing items with the same color within as few bins as possible. This problem emerges in areas as diverse as surgical scheduling and group event seating. We present several optimization models for the BPPMCF, including baseline integer programming formulations, alternative integer programming formulations based on two recursive decomposition strategies that utilize decision diagrams, and a branch-and-price algorithm. Using the results from an extensive computational evaluation on synthetic instances, we train a decision tree model that predicts which algorithm should be chosen to solve a given instance of the problem based on a collection of derived features. Our insights are validated through experiments on the aforementioned applications on real-world data. Summary of Contribution: In this paper, we investigate a colored variant of the bin-packing problem. We present and evaluate several exact mixed-integer programming formulations to solve the problem, including models that explore recursive decomposition strategies based on decision diagrams and a set partitioning model that we solve using branch and price. Our results show that the computational performance of the algorithms depends on features of the input data, such as the average number of items per bin. Our algorithms and featured applications suggest that the problem is of practical relevance and that instances of reasonable size can be solved efficiently. [ABSTRACT FROM AUTHOR]

We investigate the discrete parallel machine scheduling and location problem, which consists of locating multiple machines to a set of candidate locations, assigning jobs from different locations to the located machines, and sequencing the assigned jobs. The objective is to minimize the maximum completion time of all jobs, that is, the makespan. Though the problem is of theoretical significance with a wide range of practical applications, it has not been well studied as reported in the literature. For this problem, we first propose three new mixed-integer linear programs that outperform state-of-the-art formulations. Then, we develop a new logic-based Benders decomposition algorithm for practical-sized instances, which splits the problem into a master problem that determines machine locations and job assignments to machines and a subproblem that sequences jobs on each machine. The master problem is solved by a branch-and-cut procedure that operates on a single search tree. Once an incumbent solution to the master problem is found, the subproblem is solved to generate cuts that are dynamically added to the master problem. A generic no-good cut is first proposed, which is later improved by some strengthening techniques. Two optimality cuts are also developed based on optimality conditions of the subproblem and improved by strengthening techniques. Numerical results on small-sized instances show that the proposed formulations outperform state-of-the-art ones. Computational results on 1,400 benchmark instances with up to 300 jobs, 50 machines, and 300 locations demonstrate the effectiveness and efficiency of the algorithm compared with current approaches. Summary of Contribution: This paper employs operations research methods and computing techniques to address an NP-hard combinatorial optimization problem: the parallel discrete machine scheduling and location problem. The problem is of practical significance but has not been well studied in the literature. For the problem, we formulate three novel mixed-integer linear programs that outperform state-of-the-art formulations and develop a new logic-based Benders decomposition algorithm. Extensive computational experiments on 1,400 benchmark instances with up to 300 jobs, 50 machines, and 300 locations are conducted to evaluate the performance of the proposed models and algorithms. [ABSTRACT FROM AUTHOR]

We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the decision variables, akin to single objective problems, although we also sometimes split gaps and branch in the objective space. The various algorithms are implemented using a data structure for storing Pareto sets. Computational experiments are carried out on literature instances and on a new set of instances that we generate using a benchmark library (MIPLIB2017) for single objective problems. We also perform comparisons against the triangle splitting method from literature, which is an objective space search algorithm. Summary of Contribution: Biobjective mixed-integer optimization problems have two linear objectives and a mixed-integer feasible region. Such problems have many applications in operations research, because many real-world optimization problems naturally comprise two conflicting objectives to optimize or can be approximated in such a manner and are even harder than single objective mixed-integer programs. Solving them exactly requires the computation of all the nondominated solutions in the objective space, whereas some applications may also require finding at least one solution in the decision space corresponding to each nondominated solution. This paper provides an exact algorithm for solving these problems using the branch-and-bound method, which works predominantly in the decision space. Of the many ingredients of this algorithm, some parts are direct extensions of the single-objective version, but the main parts are newly designed algorithms to handle the distinct challenges of optimizing over two objectives. The goal of this study is to improve solution quality and speed and show that decision-space algorithms perform comparably to, and sometimes better than, algorithms that work mainly in the objective-space. [ABSTRACT FROM AUTHOR]

Dynamic pricing for a network of resources over a finite selling horizon has received considerable attention in recent years, yet few papers provide effective computational approaches to solve the problem. We consider a resource decomposition approach to solve the problem and investigate the performance of the approach in a computational study. We compare the performance of the approach to static pricing and choice-based availability control. Our numerical results show that dynamic pricing policies from network resource decomposition can achieve significant revenue lift compared with choice-based availability control and static pricing, even when the latter is frequently resolved. As a by-product of our approach, network decomposition provides an upper bound in revenue, which is provably tighter than the well-known upper bound from a deterministic approximation. [ABSTRACT FROM AUTHOR]

A facility with frontroom and backroom operations has the option of hiring specialized or cross-trained workers. Cross-trained workers can be switched between the two rooms depending on demand but are more expensive than specialized ones. Assuming stochastic customer arrival and service times, we seek a smallestcost combination of cross-trained and specialized workers, together with a policy for switching the cross-trained workers between the rooms, which satisfies constraints on the expected customer waiting time and expected number of workers in the back room. Aconstraint programming approach using logic-based Benders' decomposition is presented. Experimental results demonstrate the strong performance of this approach across a wide variety of problem parameters. This paper provides one of the first links between queueing optimization problems and constraint programming. [ABSTRACT FROM AUTHOR]

This paper puts forth a general method to optimize constrained problems effectively when using tabu search. An adaptive penalty approach is used that exploits the short-term memory structure of the tabu list along with the long-term memory of the search results. It is shown to be effective on a variety of combinatorial problems with different degrees and numbers of constraints. The approach requires few parameters, is robust to their setting, and encourages search in promising regions of the feasible and infeasible regions before converging to a final feasible solution. The method is tested on three diverse NP-hard problems, facility layout, system reliability optimization, and orienteering, and is compared with two other penalty approaches developed explicitly for tabu search. The proposed memory-based approach shows consistent strong performance. [ABSTRACT FROM AUTHOR]

The two-dimensional bin packing problem calls for packing a set of rectangular items into a minimal set of larger rectangular bins. Items must be packed with their edges parallel to the borders of the bins, cannot be rotated, and cannot overlap among them. The problem is of interest because it models many real-world applications, including production, warehouse management, and transportation. It is, unfortunately, very difficult, and instances with just 40 items are unsolved to proven optimality, despite many attempts, since the 1990s. In this paper, we solve the problem with a combinatorial Benders decomposition that is based on a simple model in which the two-dimensional items and bins are just represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but we enrich it with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The resulting algorithm behaved very well on the benchmark sets of instances, improving on average on previous algorithms from the literature and solving for the first time a number of open instances. Summary of Contribution: We address the two-dimensional bin packing problem (2D-BPP), which calls for packing a set of rectangular items into a minimal set of larger rectangular bins. The 2D-BPP is a very difficult generalization of the standard one-dimensional bin packing problem, and it has been widely studied in the past because it models many real-world applications, including production, warehouse management, and transportation. We solve the 2D-BPP with a combinatorial Benders decomposition that is based on a model in which the two-dimensional items and bins are represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but it is enriched with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The algorithm we developed has been extensively tested on the most well-known benchmark set from the literature, which contains 500 instances. It behaved very well, improving on average upon previous algorithms, and solving for the first time a number of open instances. We analyzed in detail several configurations before obtaining the best one and discussed several insights from this analysis in the manuscript. [ABSTRACT FROM AUTHOR]

Maintenance optimization has been extensively studied in the past decades. However, most of the existing maintenance models focus on single-component systems and are not applicable to complex systems consisting of multiple components, due to various interactions among the components. The multicomponent maintenance optimization problem, which joins the stochastic processes regarding the failures of components with the combinatorial problems regarding the grouping of maintenance activities, is challenging in both modeling and solution techniques, and has remained an open issue in the literature. In this paper, we study the multicomponent maintenance problem over a finite planning horizon and formulate the problem as a multistage stochastic integer program with decision-dependent uncertainty. There is a lack of general efficient methods to solve this type of problem. To address this challenge, we use an alternative approach to model the underlying failure process and develop a novel two-stage model without decision-dependent uncertainty. Structural properties of the two-stage problem are investigated, and a progressive-hedging-based heuristic is developed based on the structural properties. Our heuristic algorithm demonstrates a significantly improved capacity to handle large-size two-stage problems comparing to three conventional methods for stochastic integer programming, and solving the two-stage model by our heuristic in a rolling horizon provides a good approximation of the multistage problem. The heuristic is further benchmarked with a dynamic programming approach and a structural policy, which are two commonly adopted approaches in the literature. Numerical results show that our heuristic can lead to significant cost savings compared with the benchmark approaches. [ABSTRACT FROM AUTHOR]

Emerald ash borer (EAB), a wood-boring insect native to Asia and invading North America, has killed untold millions of high-value ash trees that shade streets, homes, and parks and caused significant economic damage in cities of the United States. Local actions to reduce damage include surveillance to find EAB and control to slow its spread. We present a multistage stochastic mixed-integer programming (M-SMIP) model for the optimization of surveillance, treatment, and removal of ash trees in cities. Decision-dependent uncertainty is modeled by representing surveillance decisions and the realizations of the uncertain infestation parameter contingent on surveillance as branches in the M-SMIP scenario tree. The objective is to allocate resources to surveillance and control over space and time to maximize public benefits. We develop a new cutting-plane algorithm to strengthen the M-SMIP formulation and facilitate an optimal solution. We calibrate and validate our model of ash dynamics using seven years of observational data and apply the optimization model to a possible infestation in Burnsville, Minnesota. Proposed cutting planes improve the solution time by an average of seven times over solving the original M-SMIP model without cutting planes. Our comparative analysis shows that the M-SMIP model outperforms six different heuristic approaches proposed for the management of EAB. Results from optimally solving our M-SMIP model imply that under a belief of infestation, it is critical to apply surveillance immediately to locate EAB and then prioritize treatment of minimally infested trees followed by removal of highly infested trees. Summary of Contributions: Emerald ash borer (EAB) is one of the most damaging invasive species ever to reach the United States, damaging millions of ash trees. Much of the economic impact of EAB occurs in cities, where high-value ash trees grow in abundance along streets and in yards and parks. This paper addresses the joint optimization of surveillance and control of the emerald ash borer invasion, which is a novel application for the INFORMS society because, to our knowledge, this specific problem of EAB management has not been published before in any OR/MS journals. We develop a new multi-stage stochastic mixed-integer programming (MSS-MIP) formulation, and we apply our model to surveillance and control of EAB in cities. Our MSS-MIP model aims to help city managers maximize the net benefits of their healthy ash trees by determining the optimal timing and target population for surveying, treating, and removing infested ash trees while taking into account the spatio-temporal stochastic growth of the EAB infestation. We develop a new cutting plane methodology motivated by our problem, which could also be applied to other stochastic MIPs. Our cutting plane approach provides significant computational benefit in solving the problem. Specifically, proposed cutting planes improve the solution time by an average of seven times over solving the original M-SMIP model without cutting planes. We calibrate and validate our model using seven years of ash infestation observations in forests near Toledo, Ohio. We then apply our model to an urban forest in Burnsville, Minnesota, that is threatened by EAB. Our results provide insights into the optimal timing and location of EAB surveillance and control strategies. [ABSTRACT FROM AUTHOR]

The Canadian traveler problem (CTP) is a simple, yet challenging, stochastic optimization problem wherein an agent is given a graph where some edges are blocked with certain probabilities and the status of these edges can be disambiguated dynamically upon reaching an incident vertex. The goal is to devise a traversal policy that results in the shortest expected walk length between a given starting vertex and a termination vertex. CTP has been shown to be intractable in many broad settings. In this paper, we introduce an optimal algorithm for the problem based on a Markov decision process formulation, which is a new improvement on AO* search that takes advantage of the special problem structure in CTP. We call our algorithm CAO*, which stands for AO* with caching. CAO* uses a caching mechanism to avoid re-expansion of previously visited states and makes use of admissible upper bounds at a node level for dynamic state-space pruning. CAO* is not polynomial time, but it can dramatically shorten the execution time needed to find an exact solution for moderately sized instances. We present computational experiments on a realistic variant of the problem involving an actual maritime minefield data set. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Many combinatorial problems require that their solutions achieve a certain balance of given features. For this important aspect of modeling, the spread and deviation constraints have been proposed in Constraint Programming to express balance among a set of variables by constraining their mean and overall deviation from the mean. To our knowledge, the only practical filtering algorithms known for these constraints achieve bounds consistency. In this paper we improve that filtering by presenting an efficient domain consistency algorithm that applies to both constraints. We also extend it to count solutions so that it can be used in counting-based search, a generic and effective family of branching heuristics that free the user from having to write problem-specific search heuristics. We provide a time complexity analysis of our contributions and empirically evaluate them on benchmark problems. [ABSTRACT FROM AUTHOR]

Multistage problems with uncertain parameters and integer decisions variables are among the most difficult applications of robust optimization (RO). The challenge in these problems is to find optimal here-and-now decisions, taking into account that the wait-and-see decisions have to adapt to the revealed values of the uncertain parameters. An existing approach to solve these problems is to construct piecewise constant decision rules by adaptively partitioning the uncertainty set. The partitions of this set are iteratively updated by separating so-called criticial scenarios, and methods for identifying these critical scenarios are available. However, these methods are most suitable for problems with continuous decision variables and many uncertain constraints, providing no mathematically rigorous methodology for partitioning in case of integer decisions. In particular, they are not able to identify sets of critical scenarios for integer problems with uncertainty in the objective function only. In this paper, we address this shortcoming by introducing a general critical scenario detection method. The new method leverages the information embedded in the dual vectors of the LP relaxations at the nodes of the branch-and-bound tree used to solve the corresponding static problem. Numerical experiments on a route planning problem show that our general-purpose method outperforms a problem-specific approach from the literature. [ABSTRACT FROM AUTHOR]

We introduce a simple technique for disjunctive machine scheduling problems and show that this method can match or even outperform state-of-the-art algorithms on a number of problem types. Our approach combines a number of generic search techniques such as restarts, adaptive heuristics, and solution-guided branching on a simple model based on a decomposition of disjunctive constraints and on the reification of these disjuncts. This paper describes the method and its application to variants of the job shop scheduling problem (JSP). We show that our method can easily be adapted to handle additional side constraints and different objective functions, often outperforming the state-of-the-art and closing a number of open problems. Moreover, we perform in-depth analysis of the various factors that make this approach efficient. We show that, while most of the factors give moderate benefits, the variable and value ordering components are key. [ABSTRACT FROM AUTHOR]

In an optical network a signal can only travel a maximum distance dmax before its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. In this paper we introduce the generalized regenerator location problem (GRLP) in which we are given a set S of nodes that corresponds to candidate locations for regenerators, and a set T of nodes that must communicate with each other. If S DT DN, we obtain the regenerator location problem (RLP), which we have studied previously and shown to be NP-complete. Our solution procedure to the RLP is based on its equivalence to the maximum leaf spanning tree problem (MLSTP). Unfortunately, this equivalence does not apply to the GRLP, nor do the procedures developed previously for the RLP. To solve the GRLP, we propose reduction procedures, two construction heuristics, and a local search procedure that we collectively refer to as a heuristic framework. We also establish a correspondence between the (node-weighted) directed Steiner forest problem and the GRLP. Using this fact, we provide several ways to derive natural and extended integer programming (IP) and mixed-integer programming (MIP) models for the GRLP and compare the strength of these models. Using the strongest model derived on the natural node selection variables we develop a branchand- cut approach to solve the problem to optimality. The results indicate that the exact approach can easily solve instances with up to 200 nodes to optimality, whereas the heuristic framework is a high-quality approach for solving large-scale instances. [ABSTRACT FROM AUTHOR]

Viral-marketing strategies are of significant interest in the online economy. Roughly, in these problems, one seeks to identify which individuals to strategically target in a social network so that a given proportion of the network is influenced at minimum cost. Earlier literature has focused primarily on problems where a fixed inducement is provided to those targeted. In contrast, resembling the practical viral-marketing setting, we consider this problem where one is allowed to "partially influence" (by the use of monetary inducements) those selected for targeting. We thus focus on the "least-cost influence problem (LCIP)": an influence-maximization problem where the goal is to find the minimum total amount of inducements (individuals to target and associated tailored incentive) required to influence a given proportion of the population. Motivated by the desire to develop a better understanding of fundamental problems in social-network analytics, we seek to develop (exact) optimization approaches for the LCIP. Our paper makes several contributions, including (i) showing that the problem is NP-complete in general as well as under a wide variety of special conditions; (ii) providing an influence greedy algorithm to solve the problem polynomially on trees, where we require 100% adoption and all neighbors exert equal influence on a node; and (iii) a totally unimodular formulation for this tree case. [ABSTRACT FROM AUTHOR]

We study optimization problems with value-at-risk (VaR) constraints. Because it lacks subadditivity, VaR is not a coherent risk measure and does not necessarily preserve the convexity. Thus, the problems we consider are typically not provably convex. As such, the conditional value-at-risk (CVaR) approximation is often used to handle such problems. Even though the CVaR approximation is known as the best convex conservative approximation, it sometimes leads to solutions with poor performance. In this paper, we investigate the CVaR approximation from a different perspective and demonstrate what is lost in this approximation. We then show that the lost part of this approximation can be remedied using a sequential convex approximation approach, in which each iteration only requires solving a CVaR-like approximation via certain Monte Carlo techniques. We show that the solution found by this approach generally makes the VaR constraints binding and is guaranteed to be better than the solution found by the CVaR approximation and moreover is empirically often globally optimal for the target problem. The numerical experiments show the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

This paper considers a very general class of customer-to-resource assignment problems relevant to a variety of manufacturing contexts. This problem class addresses settings in which subsets of customer types share resource capacities as well as a fixed amount of capacity consumption, independent of production volume. More broadly, our model addresses cross-facility production limits and shared capacity consumption within each customer type. To solve these large-scale optimization problems, we apply a branch-and-price solution approach. This approach relies on an effective solution method for a novel class of nonlinear knapsack pricing problems. As our computational results demonstrate, despite the fact that the resulting master problem is not a simple set-partitioning problem, the problem's relaxation is sufficiently tight to produce an algorithm that significantly outperforms CPLEX for a wide range of problem parameter settings. [ABSTRACT FROM AUTHOR]

One method to obtain high-quality bid prices for network revenue management problems involves using the approximate linear programming approach on the dynamic programming formulation of the problem. This approach ends up with a linear program whose number of constraints increases exponentially with the number of flight legs in the airline network. The linear program is solved using constraint generation, where each constraint can be generated by solving a separate integer program. The necessity to solve integer programs and the slow convergence behavior of constraint generation are generally recognized as drawbacks of this approach. In this paper, we show how to effectively eliminate these drawbacks. In particular, we establish that constraint generation can actually be carried out by solving minimum-cost network flow problems with natural integer solutions. Furthermore, using the structure of minimum-cost network flow problems, we a priori reduce the number of constraints in the linear program from exponential to linear in the number of flight legs. It turns out that the reduced linear program can be solved without using separate problems to generate constraints. The reduced linear program also provides a practically appealing interpretation. Computational experiments indicate that our results can speed up the computation time for the approximate linear programming approach by a factor ranging between 13 and 135. [ABSTRACT FROM AUTHOR]

In this paper we present an exact algorithm for the capacitated location-routing problem (CLRP) based on cut-and-column generation. The CLRP is formulated as a set-partitioning problem that also inherits all of the known valid inequalities for the flow formulations of the CLRP. We introduce five new families of inequalities that are shown to dominate some of the cuts from the two-index formulation. The problem is solved by column generation, where the subproblem consists in finding a shortest path of minimum reduced cost under capacity constraints. We first use the two-index formulation for enumerating all of the possible subsets of depot locations that could lead to an optimal solution of cost less than or equal to a given upper bound. For each of these subsets, the corresponding multiple depot vehicle routing problem is then solved by means of column generation. The results show that we can improve the bounds found in the literature, solve to optimality some previously open instances, and improve the upper bounds on some other instances. [ABSTRACT FROM AUTHOR]

We present a semidefinite programming (SDP) approach for the problem of ordering vertices of a layered graph such that the edges of the graph are drawn as vertical as possible. This multilevel vertical ordering (MLVO) problem is a quadratic ordering problem and conceptually related to the well-studied problem of multilevel crossing minimization (MLCM). In contrast to the latter, it can be formulated such that it does not merely consist of multiple sequentially linked bilevel quadratic ordering problems, but as a genuine multilevel problem with dense cost matrix. This allows us to describe the graphs' structures more compactly and therefore obtain solutions for graphs too large for MLCM in practice. In this paper we give motivation and mathematical models for MLVO. We formulate linear and quadratic programs, including some strengthening constraint classes, and an SDP relaxation for MLVO. We compare all approaches both theoretically and experimentally and show that MLVO's properties render linear and quadratic programming approaches inapplicable, even for small sparse graphs, while the SDP works surprisingly well in practice. This is in stark contrast to other ordering problems like MLCM, where such graphs are typically solved more efficiently with integer linear programs. Finally, we also compare our approach to related MLCM approaches. [ABSTRACT FROM AUTHOR]

This paper studies the classical task assignment problem (TAP) in which M unbreakable tasks are assigned to N agents with the objective to minimize the communication and process costs subject to each agent's capacity constraint. Because a large-size TAP involves many binary variables, most, if not all, traditional methods experience the difficulty in solving the problem within a reasonable time period. Recent works present a logarithmic approach to reduce the number of binary variables in problems with mixed-integer variables. This study proposes a new logarithmic method that significantly reduces the numbers of binary variables and inequality constraints in solving task assignment problems. Our numerical experiments demonstrate that the proposed method is superior to other known methods of this kind for solving large-size TAPs. [ABSTRACT FROM AUTHOR]

In this paper, we study approximation algorithms for two supply chain network design problems, namely, the warehouse-retailer network design problem (WRND) and the stochastic transportation-inventory network design problem (STIND). These two problems generalize the classical uncapacitated facility location problem by incorporating, respectively, the warehouse-retailer echelon inventory cost and the warehouse cycle inventory together with the safety stock costs. The WRND and the STIND were initially studied, respectively, by Teo and Shu (Teo CP, Shu J (2004) Warehouse-retailer network design problem. Oper. Res. 52(3):396-408) and Shu et al. (Shu J, Teo CP, Shen ZJM (2005) Stochastic transportation-inventory network design problem. Oper. Res. 53(1):48-60), where they are formulated as set-covering problems, and column-generation algorithms were used to solve their linear programming relaxations. Both problems can be regarded as special cases of the so-called facility location with submodular facility costs proposed by Svitkina and Tardos (Svitkina Z, Tardos É (2010) Facility location with hierarchical facility costs. ACM Trans. Algorithms 6(2), Article No. 37), for which only a logarithmic-factor approximation algorithm is known. Our main contribution is to obtain efficient constant-factor approximation algorithms for the WRND and the STIND, which are capable of solving large-scale instances of these problems efficiently. [ABSTRACT FROM AUTHOR]

In this paper, we propose a "multistart-type" algorithm for solving the max-k-cut problem. Central to our algorithm is an auxiliary function we propose. We formulate the max-k-cut problem as an explicit mathematical form, which allows us to use an easy implementable local search. The construction of the auxiliary function requires a local maximizer of the max-k-cut problem. If the best local maximizer obtained is used in the construction of the auxiliary function, then the local maximization of the auxiliary function leads to a better maximizer of the max-k-cut problem. This proves to be a good strategy to escape from the current local optima and to search a broader solution space. Indeed, we have shown, both numerically and theoretically, that the maximization of the auxiliary function by the local search method can escape successfully from previously converged discrete local maximizers by taking increasing values of a parameter. Computational results on many test instances with different sizes and densities show that the proposed algorithm is efficient and stable to find approximate global solutions for the max-k-cut problems. Although we have presented results for k = 2, the robustness of our algorithm is shown for k = 2 by comparisons with a number of recent methods. A number of theoretical results are also presented, which justify the design of our algorithm. [ABSTRACT FROM AUTHOR]

This paper describes a generic branch-and-cut algorithm applicable to the solution of multiobjective optimization problems for which a lower bound can be defined as a polynomially solvable multiobjective problem. The algorithm closely follows standard branch and cut except for the definition of the lower and upper bounds and some optional speed-up mechanisms. It is applied to a routing problem called the multilabel traveling salesman problem, a variant of the traveling salesman problem in which labels are attributed to the edges. The goal is to find a Hamiltonian cycle that minimizes the tour length and the number of labels in the tour. Implementations of the generic multiobjective branch-and-cut algorithm and speed-up mechanisms are described. Computational experiments are conducted, and the method is compared to the classical ∈-constraint method. [ABSTRACT FROM AUTHOR]

The traveling salesman problem with time windows (TSPTW) is the problem of finding in a weighted digraph TSPTW a least-cost tour starting from a selected vertex, visiting each vertex of the graph exactly once according to a given time window, and returning to the starting vertex. This-hard problem arises in routing and scheduling applications. This paper introduces a new tour relaxation, called np-tour, to compute a valid lower bound on the TSPTW obtained as the cost of a near-optimal dual solution of a problem that seeks a minimum-weight convex combination of nonnecessarily elementary tours. This problem is solved by column generation. The optimal integer solution is computed with a dynamic programming algorithm that uses bounding functions TSPTW based on different tour relaxations and the dual solution obtained. An extensive computational analysis on basically all instances (involving up to 233 vertices) from the literature is reported. The results show TSPTW that the proposed algorithm solves all but one instance and outperforms all exact methods published in the literature so far. [ABSTRACT FROM AUTHOR]

A phylogeny is an unrooted binary tree that represents the evolutionary relationships of a set of n species. A Phylogenies find applications in several scientific areas ranging from medical research, to drug discovery, to epidemiology, to systematics, and to population dynamics. In such applications, the available information is usually restricted to the leaves of a phylogeny and is represented by molecular data extracted from the analyzed species, such as DNA, RNA, amino acid, or codon fragments. On the contrary, the information about the phylogeny itself is generally missing and is determined by solving an optimization problem, called the phylogeny estimation problem (PEP), whose versions depend on the criterion used to select a phylogeny from among plausible alternatives. In this paper, we investigate a recent version of the PEP, called the balanced minimum evolution problem (BMEP). We present a mixed-integer linear programming model to exactly solve instances of the BMEP and develop branching rules and families of valid inequalities to further strengthen the model. Our results give perspective on the mathematics of the BMEP and suggest new directions on the development of future efficient exact approaches to solutions of the problem. [ABSTRACT FROM AUTHOR]

The many-to-many stable matching problem (MM), defined in the context of a job market, asks for an assignment of workers to firms satisfying the quota of each agent and being stable, pairwise or setwise, with respect to given preference lists or relations. In this paper, we propose a time-optimal algorithm that identifies all stable worker-firm pairs and all stable assignments under pairwise stability, individual preferences, and the max-min criterion. We revisit the poset graph of rotations to obtain an optimal algorithm for enumerating all solutions to the MM and an improved algorithm finding the minimum-weight one. Furthermore, we establish the applicability of all aforementioned algorithms under more complex preference and stability criteria. In a constraint programming context, we introduce a constraint that models the MM and an encoding of the MM as a constraint satisfaction problem. Finally, we provide a series of computational results, including the case where side constraints are imposed. [ABSTRACT FROM AUTHOR]

This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow us to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and it shows better results on a wide range of benchmark instances. [ABSTRACT FROM AUTHOR]

Route planning in large-scale time-dependent road networks is an important practical application of the shortest-path problem that greatly benefits from speedup techniques. In this paper, we extend a two-level hierarchical approach for point-to-point shortest-path computations to the time-dependent case. This method, also known as core routing in the literature for static graphs, consists of the selection of a small subnetwork where most of the computations can be carried out, thus reducing the search space. We combine this approach with bidirectional goal-directed search to obtain an algorithm capable of finding shortest paths in a matter of milliseconds on continental-sized networks. Moreover, we tackle the dynamic scenario where the piecewise linear functions that we use to model time-dependent arc costs are not fixed but can have their coefficients updated requiring only a small computational effort. [ABSTRACT FROM AUTHOR]