Search

The time-dependent traveling salesman problem with time windows (TDTSPTW) is a variant of the well-known traveling salesman problem with time windows, in which travel times are not assumed to be constant. The TDTSPTW accounts for the effects of congestion at the planning level, being particularly suited for distribution problems in large cities. In this paper we develop a labeling-based algorithm for the TDTSPTW that incorporates partial dominance and generalizes several state-of-the-art components from the time-independent related literature. We propose a framework general enough to be applied to the TDTSPTW and its variant without time windows, with the objective of minimizing the duration or the makespan. As part of the framework, we introduce a new state-space relaxation specifically designed for the time-dependent context. Extensive computational experiments show the effectiveness of the overall approach and the impact of the new relaxation, outperforming several recent algorithms proposed for these variants on more than 9,000 benchmark instances. In addition, we frame the minimum tour duration problem within the time-dependent literature and include it as a benchmark for our algorithm, obtaining improved computation times and 31 new optimal solutions. Summary of Contribution: In this paper, we study the time-dependent traveling salesman problem with time windows (TDTSPTW), a difficult single-vehicle routing problem that incorporates more realistic travel time functions than its classic time-independent counterpart. As a result, the TDTSPTW is harder to solve, as it requires more complex models and algorithms. Using state-of-the-art optimization techniques, we propose an efficient solution approach for the TDTSPTW and some related variants that outperforms the previous approaches in the literature. Our paper emphasizes the importance of algorithmic design and efficient implementations to tackle relevant practical combinatorial optimization problems—in particular, for time-dependent problems. Moreover, the resulting algorithm fosters a new research direction regarding exact algorithms for time-dependent problems using dynamic programming and relaxation techniques. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research has been funded by Fondo para la Investigación Científica y Tecnológica (FONCyT) [Grants PICT-2016-2677 and PICT-2018-2961] from the Ministry of Science, Argentina, and by the Google Latin America Research Award (LARA) 2019. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1236. [ABSTRACT FROM AUTHOR]

Over the last two decades, robust optimization has emerged as a popular means to address decision-making problems affected by uncertainty. This includes single-stage and multi-stage problems involving real-valued and/or binary decisions and affected by exogenous (decision-independent) and/or endogenous (decision-dependent) uncertain parameters. Robust optimization techniques rely on duality theory potentially augmented with approximations to transform a (semi-)infinite optimization problem to a finite program, the robust counterpart. Whereas writing down the model for a robust optimization problem is usually a simple task, obtaining the robust counterpart requires expertise. To date, very few solutions are available that can facilitate the modeling and solution of such problems. This has been a major impediment to their being put to practical use. In this paper, we propose ROC++, an open-source C++ based platform for automatic robust optimization, applicable to a wide array of single-stage and multi-stage robust problems with both exogenous and endogenous uncertain parameters, that is easy to both use and extend. It also applies to certain classes of stochastic programs involving continuously distributed uncertain parameters and endogenous uncertainty. Our platform naturally extends existing off-the-shelf deterministic optimization platforms and offers ROPy, a Python interface in the form of a callable library, and the ROB file format for storing and sharing robust problems. We showcase the modeling power of ROC++ on several decision-making problems of practical interest. Our platform can help streamline the modeling and solution of stochastic and robust optimization problems for both researchers and practitioners. It comes with detailed documentation to facilitate its use and expansion. The latest version of ROC++ can be downloaded from https://sites.google.com/usc.edu/robust-opt-cpp/. Summary of Contribution: The paper "ROC++: Robust Optimization in C++" proposes a new open-source C++ based platform for modeling, automatically reformulating, and solving robust optimization problems. ROC++ can address both single-stage and multi-stage problems involving exogenous and/or endogenous uncertain parameters and real- and/or binary-valued adaptive variables. The ROC++ modeling language is similar to the one provided for the deterministic case by state-of-the-art deterministic optimization solvers. ROC++ comes with detailed documentation to facilitate its use and expansion. It also offers ROPy, a Python interface in the form of a callable library. The latest version of ROC++ can be downloaded from https://sites.google.com/usc.edu/robust-opt-cpp/. History: Accepted by Ted Ralphs, Area Editor for Software Tools. Funding: This material is based upon work supported by the National Science Foundation under Grant No. 1763108. This support is gratefully acknowledged. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1209) or is available from the IJOC GitHub software repository (https://github.com/INFORMSJoC) at (https://dx.doi.org/10.5281/zenodo.6360996). [ABSTRACT FROM AUTHOR]

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]

In many statistical learning problems, it is desired that the optimal solution conform to an a priori known sparsity structure represented by a directed acyclic graph. Inducing such structures by means of convex regularizers requires nonsmooth penalty functions that exploit group overlapping. Our study focuses on evaluating the proximal operator of the latent overlapping group lasso developed by Jacob et al. in 2009. We implemented an alternating direction method of multiplier with a sharing scheme to solve large-scale instances of the underlying optimization problem efficiently. In the absence of strong convexity, global linear convergence of the algorithm is established using the error bound theory. More specifically, the paper contributes to establishing primal and dual error bounds when the nonsmooth component in the objective function does not have a polyhedral epigraph. We also investigate the effect of the graph structure on the speed of convergence of the algorithm. Detailed numerical simulation studies over different graph structures supporting the proposed algorithm and two applications in learning are provided. Summary of Contribution: The paper proposes a computationally efficient optimization algorithm to evaluate the proximal operator of a nonsmooth hierarchical sparsity-inducing regularizer and establishes its convergence properties. The computationally intensive subproblem of the proposed algorithm can be fully parallelized, which allows solving large-scale instances of the underlying problem. Comprehensive numerical simulation studies benchmarking the proposed algorithm against five other methods on the speed of convergence to optimality are provided. Furthermore, performance of the algorithm is demonstrated on two statistical learning applications related to topic modeling and breast cancer classification. The code along with the simulation studies and benchmarks are available on the corresponding author's GitHub website for evaluation and future use. [ABSTRACT FROM AUTHOR]

In this paper, we consider uncertain second-order cone (SOC) and semidefinite programming (SDP) constraints with polyhedral uncertainty, which are in general computationally intractable. We propose to reformulate an uncertain SOC or SDP constraint as a set of adjustable robust linear optimization constraints with an ellipsoidal or semidefinite representable uncertainty set, respectively. The resulting adjustable problem can then (approximately) be solved by using adjustable robust linear optimization techniques. For example, we show that if linear decision rules are used, then the final robust counterpart consists of SOC or SDP constraints, respectively, which have the same computational complexity as the nominal version of the original constraints. We propose an efficient method to obtain good lower bounds. Moreover, we extend our approach to other classes of robust optimization problems, such as nonlinear problems that contain wait-and-see variables, linear problems that contain bilinear uncertainty, and general conic constraints. Numerically, we apply our approach to reformulate the problem on finding the minimum volume circumscribing ellipsoid of a polytope and solve the resulting reformulation with linear and quadratic decision rules as well as Fourier-Motzkin elimination. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it with the state-of-the-art copositive approach. Moreover, we apply the proposed approach to a robust regression problem and a robust sensor network problem and use linear decision rules to solve the resulting adjustable robust linear optimization problems, which solve the problem to (near) optimality. Summary of Contribution: Computing robust solutions for nonlinear optimization problems with uncertain second-order cone and semidefinite programming constraints are of much interest in real-life applications, yet they are in general computationally intractable. This paper proposes a computationally tractable approximation for such problems. Extensive computational experiments on (i) computing the minimum volume circumscribing ellipsoid of a polytope, (ii) robust regressions, and (iii) robust sensor networks are conducted to demonstrate the effectiveness and efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper makes a contribution to the branch and cut approach to the capacitated vehicle-routing problem (CVRP). In the CVRP, the demands of a set of customers have to be met at minimum total travel cost using vehicles of identical capacity based at a single depot. The potential of maximally violated mod-p cutting-planes (Caprara et al. 2000) for the CVRP is investigated via a computational study. The foundation of the assessment is formed by classes of problem-specific constraints taken from the literature. In several separation algorithms for the CVRP, it is advantageous to shrink inclusionwise maximal minimum-weight cuts in support graphs as preprocessing. It is mentioned how a partition of the set of customers into such mincuts can be computed in a fast and elegant way using the mincut algorithm of Hao and Orlin (1994). Interestingly, maximally violated mod-p cuts, which are general-purpose cuts of Chvátal-Gomory type, stand comparison with problem-specific cuts for the CVRP and they are clearly useful on top of such cuts. The first-time proven optimal solution of the CVRP instance B-n68-k9 is reported. The computation used a branching strategy with far lookahead and relied on maximally violated mod-p cuts. This paper on maximally violated cuts belongs to a set of papers originating from Applegate et al. (1995) where a separation of maximally violated combs for the traveling-salesman problem (TSP) is suggested. [ABSTRACT FROM AUTHOR]

Aircraft conflict resolution is one of the major tasks of computer-aided air traffic management and represents a challenging optimization problem. Many models and methods have been proposed to assist trajectory regulation to avoid conflicts. However, the question of testing the different mathematical optimization approaches against each other is still open. Standard benchmarks include unrealistic scenarios in which all the flights move toward a common point or completely random generated instances. There is a lack of a common set of test instances that allows comparison of the available methods under a variety of heterogeneous and representative scenarios. We present a flight deconfliction benchmark generator that allows the user to choose between (i) different predefined scenario inspired by existing benchmarks in the literature; (ii) pseudo-random traffic meeting certain congestion measurements; (iii) and randomly generated traffic. The proposed setting can account for different levels of difficulty in the deconfliction of the aircraft and allows to explore and compare the real limitations of optimization approaches for aircraft conflict resolution. History: Accepted by Ted Ralphs, area editor for Software Tools. Funding: This work was supported by the H2020 Marie Skłodowska-Curie Actions [Grant 764759 ITN "MINOA"]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1265) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0283) at (http://dx.doi.org/10.5281/zenodo.7377734). [ABSTRACT FROM AUTHOR]

Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, and so on. Often these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization, one develops primal heuristics in order to obtain feasible points of good quality quickly or to enhance the search process of exact global methods. However, there are comparably few heuristics for bilevel problems. In this paper, we develop such a primal heuristic for bilevel problems with a mixed-integer linear or quadratic upper level and a linear or quadratic lower level. The heuristic is based on a penalty alternating direction method, which allows for a theoretical analysis. We derive a convergence theory stating that the method converges to a stationary point of an equivalent single-level reformulation of the bilevel problem and extensively test the method on a test set of more than 2,800 instances—which is one of the largest computational test sets ever used in bilevel programming. The study illustrates the very good performance of the proposed method in terms of both running times and solution quality. This renders the method a suitable subroutine in global bilevel solvers as well as a reasonable standalone approach.Summary of Contribution: Bilevel optimization problems form a very important class of optimization problems in the field of operations research, which is mainly due to their capability of modeling hierarchical decision processes. However, real-world bilevel problems are usually very hard to solve—especially in the case in which additional mixed-integer aspects are included in the modeling. Hence, the development of fast and reliable primal heuristics for this class of problems is very important. This paper presents such a method. [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]

The purpose of this paper is to introduce a new test-problem collection for stochastic linear programming that the authors have recently begun to assemble. While there are existing stochastic programming test-problem collections, our new collection has three features that distinguish it from existing collections. First, our collection is web-based with free public access, and we intend to enrich it as new test problems become available. Indeed, we encourage submissions of new test problems. Second, along with the collection we provide documentation of the problems, so that researchers can quickly find information about each family without reading through the original source. Third, all of the data in our collection are provided in SMPS (Birge et al. 1987, Gassmann and Schweitzer 2001) format. In this paper, we provide an introduction to the stochastic linear program, give a brief description of each problem family currently in the test-problem collection, and describe the documentation that accompanies the collection. [ABSTRACT FROM AUTHOR]

The paper presents an LU factorization that was developed especially for EMNET's working inverse. This working inverse is obtained by partitioning the simplex basis to isolate the network substructure that many problems possess. The update procedure for the LU factorization is a direct extension of the Bartels-Golub update. This LU factorization has been mentioned in some previous papers but the details of the extension of the Bartels-Golub update have not been previously published. Neither has its impact upon EMNET been documented.

Network design, a cornerstone of mathematical optimization, is about defining the main characteristics of a network satisfying requirements on connectivity, capacity, and level-of-service. It finds applications in logistics and transportation, telecommunications, data sharing, energy distribution, and distributed computing. In multicommodity network design, one is required to design a network minimizing the installation cost of its arcs and the operational cost to serve a set of point-to-point connections. The definition of this prototypical problem was recently enriched by additional constraints imposing that each origin-destination of a connection is served by a single path satisfying one or more level-of-service requirements, thus defining the Network Design with Service Requirements. These constraints are crucial, for example, in telecommunications and computer networks to ensure reliable and low-latency communication. In this paper we provide a new formulation for the problem, where variables are associated with paths satisfying the end-to-end service requirements. We present a fast algorithm for enumerating all the exponentially many feasible paths, and when this is not viable, we provide a column generation scheme that is embedded into a branch-and-cut-and-price algorithm. Extensive computational experiments on a large set of instances show that our approach can move a step further in the solution of the network design with service requirements compared with the current state-of-the-art. [ABSTRACT FROM AUTHOR]

The state of numerical computing is currently characterized by a divide between highly efficient yet typically cumbersome low-level languages such as C, CCC, and Fortran and highly expressive yet typically slow high-level languages such as Python and MATLAB. This paper explores how Julia, a modern programming language for numerical computing that claims to bridge this divide by incorporating recent advances in language and compiler design (such as just-in-time compilation), can be used for implementing software and algorithms fundamental to the field of operations research, with a focus on mathematical optimization. In particular, we demonstrate algebraic modeling for linear and nonlinear optimization and a partial implementation of a practical simplex code. Extensive cross-language benchmarks suggest that Julia is capable of obtaining state-of-the-art performance. [ABSTRACT FROM AUTHOR]

Given a bound, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of minimum total weight with a diameter not exceeding the given diameter bound. Depending on the tightness of the bound, optimal solutions have different structures. For loose bounds, optimal solutions are similar to the much easier minimum spanning tree problem, and greedy heuristics perform best. In contrast, these approaches fail for tight diameter bounds. This paper investigates how the structure of good solutions, and in particular their backbones, change depending on the diameter bound. Two new heuristics are then designed to overcome the shortcomings of existing approaches; required parameters are investigated; and the paper presents performance results for Euclidean BDMST instances. [ABSTRACT FROM AUTHOR]

In this paper, I view and present the multiobjective discrete optimisation problem as a particular case of disjunctive programming where one seeks to identify efficient solutions from within a disjunction formed by a set of systems. The proposed approach lends itself to a simple yet effective iterative algorithm that is able to yield the set of all nondominated points, both supported and nonsupported, for a multiobjective discrete optimisation problem. Each iteration of the algorithm is a series of feasibility checks and requires only one formulation to be solved to optimality that has the same number of integer variables as that of the single objective formulation of the problem. The application of the algorithm shows that it is particularly effective when solving constrained multiobjective discrete optimisation problem instances. [ABSTRACT FROM AUTHOR]

We introduce MathOptInterface, an abstract data structure for representing mathematical optimization problems based on combining predefined functions and sets. MathOptInterface is significantly more general than existing data structures in the literature, encompassing, for example, a spectrum of problems classes from integer programming with indicator constraints to bilinear semidefinite programming. We also outline an automated rewriting system between equivalent formulations of a constraint. MathOptInterface has been implemented in practice, forming the foundation of a recent rewrite of JuMP, an open-source algebraic modeling language in the Julia language. The regularity of the MathOptInterface representation leads naturally to a general file format for mathematical optimization we call MathOptFormat. In addition, the automated rewriting system provides modeling power to users while making it easy to connect new solvers to JuMP. Summary of Contribution: This paper describes a new abstract data structure for representing mathematical optimization models with a corresponding file format and automatic transformation system. The advances are useful for algebraic modeling languages, allowing practitioners to model problems more naturally and more generally than before. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of stochastic optimization problems, where although the objective functions may not be convex, they satisfy a generalization of convexity called the sequentially convex property. We focus on a setting where the distribution of the underlying uncertainty is unknown and the manager must make a decision in real time based on historical data. Because sequentially convex functions are not necessarily convex, they pose difficulties in applying standard adaptive methods for convex optimization. We propose a nonparametric algorithm based on a gradient descent method and show that the T -season average expected cost differs from the minimum cost by at most O(1/√T). Our analysis is based on a careful quantification of the bias that is inherent in gradient estimation because of the adaptive nature of the problem. We demonstrate the usefulness of the concept of sequential convexity by applying it to three canonical problems in inventory control, capacity allocation, and the lifetime buy decision, under the assumption that the manager does not know the demand distributions and has access only to historical sales (censored demand) data. [ABSTRACT FROM AUTHOR]

In this article the author reflects on the implication of post-decision states and separable approximations for approximate dynamic programming. He states that separable approximation works well for models of dynamic resource management. He appreciates Warren Powell's 2010 paper "Merging AI and OR to Solve High-Dimensional Stochastic Optimization Problems Using Approximate Dynamic Programming" which discusses the distribution of random variables.

We discuss two possible parallel strategies for randomized restart algorithms. Given a set of available algorithms, one can either choose the best performing algorithm and run its multiple copies in parallel (single algorithm portfolio) or choose some subset of algorithms to run in parallel (mixed algorithm portfolio). It has been previously shown that the latter approach may provide better results computationally. In this paper, we provide theoretical investigation of the extent of such improvement generalizing some of the known results from the literature. In particular, we estimate the computational value of mixing randomized restart algorithms with different properties. Under some mild assumptions, we prove that in the best case the mixed algorithm portfolio may perform approximately up to 1.58 times faster than the best single algorithm portfolio. We also show that the obtained upper bound is sharp. Furthermore, the constructive proof of the main result allows us to characterize algorithms that are likely to form an effective mixed algorithm portfolio. [ABSTRACT FROM AUTHOR]

This paper derives a novel, asymptotic statistical test of the Karush-Kuhn-Tucker first-order necessary optimality conditions in random simulation models with multiple responses. This test combines a simple form of the delta method and a generalized version of Wald's statistic. The test is applied to both a toy problem and an (s, S) inventory-optimization problem with a service-level constraint; its numerical results are encouraging. [ABSTRACT FROM AUTHOR]

This paper presents a biobjective genetic algorithm (GA) to design reliable two-node connected telecommunication networks. Because the exact calculation of the reliability of a network is NP-hard, network designers have been reluctant to use network reliability as a design criterion; however, it is clearly an important aspect. Herein, three methods of reliability assessment are developed: an exact reliability calculation method using factoring, an efficient Monte Carlo estimation procedure using the sequential construction technique and network reductions, and an upper bound for the all-terminal reliability of networks with arbitrary arc reliabilities. These three methods of reliability assessment are used collectively in a biobjective GA with specialized mutation operators that perturb solutions without disturbing two-node connectivity. Computational experiments show that the proposed approach is tractable and significantly improves upon the results found by single-objective heuristics. [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]

In recent years, much attention has been devoted to the development of metaheuristics and local search algorithms for tackling stochastic combinatorial optimization problems. This paper focuses on local search algorithms; their effectiveness is greatly determined by the evaluation procedure that is used to select the best of several solutions in the presence of uncertainty. In this paper, we propose an effective evaluation procedure that makes use of empirical estimation techniques. We illustrate this approach and we assess its performance on the probabilistic traveling salesman problem. Experimental results on a large set of instances show that the proposed approach can lead to a very fast and highly effective local search algorithm. [ABSTRACT FROM AUTHOR]

We present a new computational approach to the problem of placing n identical nonoverlapping disks in the unit square in such a way that their radii are maximized. The problem has been studied in a large number of papers, from both a theoretical and a computational point of view. In this paper, we conjecture that the problem possesses a so-called funneling landscape, a feature that is commonly found in molecular conformation problems. Based on this conjecture, we develop a stochastic search algorithm that displays excellent numerical performance. Thanks to this algorithm, we could improve over previously known putative optima in the range n ≤ 130 in as many as 32 instances, the smallest of which is n=53. [ABSTRACT FROM AUTHOR]

The introduction of edge-finding techniques was a significant development in constraint-based scheduling. Today, edge finders are still the state of the art in the disjunctive case and a technique of interest in cumulative scheduling. This paper reconsiders edge-finding algorithms for cumulative scheduling and shows that Nuijten's edge finder, and its derivatives, are incomplete because they use an invalid dominance rule. We then present a correct cumulative edge finder running in time O(n²k), where n is the number of tasks and k the number of different capacity requirements of the tasks. The new algorithm is organized in two phases and first uses dynamic programming to precompute the innermost maximization in the edge-finder specification. The paper also proposes the first extended edge-finding algorithms that run in time O(n²k), improving the running time of available algorithms. Finally, the paper discusses how to speed up the algorithm in practice and how the first phase can be used to improve algorithms based on energetic reasoning. [ABSTRACT FROM AUTHOR]

Roughly speaking, the no-free-lunch (NFL) theorems state that any blackbox algorithm has the same average performance as random search. These results have largely been ignored by algorithm researchers. This paper looks more closely at the NFL results and focuses on their implications for combinatorial problems typically faced by many researchers and practitioners. We derive necessary conditions for the NFL results to hold based on common problem structures. Often it is simple to verify that these conditions are not present in the class of problems under investigation, thus providing a theoretical basis for ignoring the doleful implications of NFL giving justification for believing there might be a dominant algorithm for the problem class under study. We apply our results to three common classes of problems. We find that only trivial subclasses of these problems fall under the NFL implications. [ABSTRACT FROM AUTHOR]

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

Workflow systems provide the key technology to enable business-process automation. One important function of workflow management is role resolution, i.e., the mechanism of assigning tasks to individual workers at runtime according to the role qualification defined in the workflow model. Role-resolution decisions directly affect the productivity of workers in an organization, and consequently affect corporate profitability. Therefore it is important to develop effective policies governing these decisions. However, there has not been a formal treatment of role-resolution policies in the literature. In this paper, we analyze role-resolution policies used in current workflow practice and propose new optimization-based policies that utilize online batching. Through a computational study, we examine three workflow-performance measures including maximum flow-time, average workload, and workload variation under these policies in different business scenarios. These scenarios vary by overall system load, task-processing-time distribution, and the number of workers. Based on computational results, we obtain the following insights that can help guide the selection of role-resolution policies. (a) As the overall system load increases, the benefit of using batching-based online optimization policies becomes more significant. (b) Processing-time variation has a major impact on workflow performance, and higher variation favors optimization-based policies. (c) Online optimization has the potential to reduce average workload significantly, and to reduce workload variation significantly as well. [ABSTRACT FROM AUTHOR]

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

The pressure from today's economic and energy markets demands further distribution of decision making in large, dynamic networks. To this end, distributed model predictive control (MPC) divides the task of operating a dynamic network into a set of small, localized subtasks, one for each distributed control agent. To guide the decomposition of die overall task, which plays a central role in die quality of the operation fielded by die distributed agents, this paper proposes a model for problem decomposition based on the design of agent communication networks. The model gives rise to the communication-network design problem: A bicriteria optimization problem whose objectives are the maximization of the influence perceived by the agents and the minimization of die communication cost. The benefit of the model is the potential to concentrate the effort of implementing distributed MPC, and measuring its actual performance, on a reduced number of decompositions, namely those that are Pareto efficient for the model. The paper gives an account of related work, including the computational complexity of finding Pareto efficient solutions, an integer programming formulation, and families of valid inequalities. Its main contribution is the demonstration that the model can be effective, meaning that Pareto efficient solutions to the model tend to induce efficient problem decompositions. The experimental evidence was gathered by applying the model to decompose control problems of two representative networks, namely arrays of pendulums and electric power networks, and measuring the quality of the operation delivered by the distributed control agents. [ABSTRACT FROM AUTHOR]

Algorithms for approximating the nondominated set of multiobjective optimization problems are reviewed. The approaches are categorized into general methods that are applicable under mild assumptions and, thus, to a wide range of problems, and into algorithms that are specifically tailored to structured problems. All in all, this survey covers 52 articles published within the last 41 years, that is, between 1979 and 2020. Summary of Contribution: In many problems in operations research, several conflicting objective functions have to be optimized simultaneously, and one is interested in finding Pareto optimal solutions. Because of the high complexity of finding Pareto optimal solutions and their usually very large number, however, the exact solution of such multiobjective problems is often very difficult, which motivates the study of approximation algorithms for multiobjective optimization problems. This research area uses techniques and methods from algorithmics and computing in order to efficiently determine approximate solutions to many well-known multiobjective problems from operations research. Even though approximation algorithms for multiobjective optimization problems have been investigated for more than 40 years and more than 50 research articles have been published on this topic, this paper provides the first survey of this important area at the intersection of computing and operations research. [ABSTRACT FROM AUTHOR]

This paper is about modeling and solving mixed integer programming (MIP) problems. In the last decade, the use of mixed integer programming models has increased dramatically. Fifteen years ago, mainframe computers were required to solve problems with a hundred integer variables. Now it is possible to solve problems with thousands of integer variables on a personal computer and obtain provably good approximate solutions to problems such as set partitioning with millions of binary variables. These advances have been made possible by developments in modeling, algorithms, software, and hardware. This paper focuses on effective modeling, preprocessing, and the methodologies of branch-and-cut and branch-and-price, which are the techniques that make it possible to treat problems with either a very large number of constraints or a very large number of variables. We show how these techniques are useful in important application areas such as network design and crew scheduling. Finally, we discuss the relatively new research areas of parallel integer programming and stochastic integer programming. [ABSTRACT FROM AUTHOR]

The sparse inverse covariance matrix is used to model conditional dependencies between variables in a graphical model to fit a multivariate Gaussian distribution. Estimating the matrix from data are well known to be computationally expensive for large-scale problems. Sparsity is employed to handle noise in the data and to promote interpretability of a learning model. Although the use of a convex ℓ1 regularizer to encourage sparsity is common practice, the combinatorial ℓ0 penalty often has more favorable statistical properties. In this paper, we directly constrain sparsity by specifying a maximally allowable number of nonzeros, in other words, by imposing an ℓ0 constraint. We introduce an efficient approximate Newton algorithm using warm starts for solving the nonconvex ℓ0-constrained inverse covariance learning problem. Numerical experiments on standard data sets show that the performance of the proposed algorithm is competitive with state-of-the-art methods. Summary of Contribution: The inverse covariance estimation problem underpins many domains, including statistics, operations research, and machine learning. We propose a scalable optimization algorithm for solving the nonconvex ℓ0-constrained problem. [ABSTRACT FROM AUTHOR]

Coherent risk measures have become a popular tool for incorporating risk aversion into stochastic optimization models. For dynamic models in which uncertainty is resolved at more than one stage, however, using coherent risk measures within a standard single-level optimization framework becomes problematic. To avoid severe time-consistency difficulties, the current state of the art is to employ risk measures of a specific nested form, which unfortunately have some undesirable and somewhat counterintuitive modeling properties. This paper summarizes the potential drawbacks of nested-form risk measure issues and then presents an alternative multilevel optimization modeling approach that enforces a form of time consistency through constraints rather than by restricting the modeler's choice of objective function. This technique leads to models that are time consistent even while using time-inconsistent risk measures and can easily be formulated to be law invariant with respect to the final wealth if so desired. We argue that this approach should be the starting point for all multistage optimization modeling. When used with time-consistent objective functions, we show its multilevel optimization constraints become redundant, and the associated models thus simplify to a more familiar single-objective form. Unfortunately, we also show that our proposed approach leads to NP-hard models, even in the simplest imaginable setting in which it would be needed: three-stage linear problems on a finite probability space, using the standard average value-at-risk and first-order mean-semideviation risk measures. Finally, we show that for a simple but reasonably realistic test application, the kind of models we propose, although drawn from an NP-hard family and certainly more time consuming to solve than those obtained from the nested-objective approach, are readily solvable to global optimality using a standard commercial mixed-integer linear programming solver. Therefore, there seems some promise of our proposed modeling approach being useful despite its computational complexity properties. [ABSTRACT FROM AUTHOR]

In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible schedule that minimizes the total cost of reducing the processing times. We reformulate the problem in terms of maximizing a linear function over a submodular polyhedron intersected with a box. For the latter problem of submodular optimization, we develop a recursive decomposition algorithm and apply it to solving the single machine scheduling problem to achieve the best possible running time. [ABSTRACT FROM AUTHOR]

We analyze the effect of tumor repopulation on optimal dose delivery in radiation therapy. We are primarily motivated by accelerated tumor repopulation toward the end of radiation treatment, which is believed to play a role in treatment failure for some tumor sites. A dynamic programming framework is developed to determine an optimal fractionation scheme based on a model of cell kill from radiation and tumor growth in between treatment days. We find that faster tumor growth suggests shorter overall treatment duration. In addition, the presence of accelerated repopulation suggests larger dose fractions later in the treatment to compensate for the increased tumor proliferation. We prove that the optimal dose fractions are increasing over time. Numerical simulations indicate a potential for improvement in treatment effectiveness. [ABSTRACT FROM AUTHOR]

Product assortment and availability are important determinants of sales success for firms of industrial commodity products. Well-known pricing and promotion strategies for differentiated products do not translate well to such products where price is closely tied to the cost of the products. Consequently, firms with multiple stores of commodity products are faced with the problem of product assortment that incorporates varying geographic and demographic conditions of locations they serve. The paper presents a model for assortment planning and optimization for multiple stores of a company. The novelty of our approach is twofold: first, it deploys data mining techniques to identify sales pattern information across multiple stores through existing sales data across segments and across stores; second, it identifies the optimal product assortment for each store and permits analyses of assortment efficiency evaluation among all existing stores. Our model first finds frequent itemsets based on association rule analysis and prunes them using a novel conflict resolution method. It then incorporates the identified product combinations into the development of the optimization formulation. Our methodology offers solutions that have important implications on product assortment, including complements versus substitutes and product bundling, and sheds lights on product planning and assortment strategies in general. A data set from an industry leading plastics manufacturer and retailer in the United States is used to demonstrate our model. [ABSTRACT FROM AUTHOR]

In this paper, we consider the so-called worst-case linear optimization (WCLO) with uncertainties on the right-hand side of the constraints. Such a problem often arises in applications such as in systemic risk estimation in finance and stochastic optimization. We first show that the WCLO problem with the uncertainty set corresponding to the l p-norm ((WCLOp)) is NP-hard for p ɛ (1,∞). Second, we combine several simple optimization techniques, such as the successive convex optimization method, quadratic convex relaxation, initialization, and branch-and-bound (B&B), to develop an algorithm for (WCLO2) that can find a globally optimal solution to (WCLO2) within a prespecified ε-tolerance. We establish the global convergence of the algorithm and estimate its complexity. We also develop a finite B&B algorithm for (WCLO∞) to identify a global optimal solution to the underlying problem, and establish the finite convergence of the algorithm. Numerical experiments are reported to illustrate the effectiveness of our proposed algorithms in finding globally optimal solutions to medium and large-scale WCLO instances. [ABSTRACT FROM AUTHOR]

With the increasing penetration of intermittent renewable energy and fluctuating electricity loads, power system operators are facing significant challenges in maintaining system load balance and reliability. In addition to traditional energy markets that are designed to balance power generation and load, ancillary service markets have been recently introduced to help manage the considerable uncertainty by reserving certain generation capacities against unexpected events. In this paper, we develop a multistage stochastic optimization model for system operators to efficiently schedule power-generation assets to co-optimize power generation and regulation reserve service (a critical ancillary service product) under uncertainty. In addition, to improve the computational efficiency of the proposed multistage stochastic integer program, we explore its polyhedral structure by investigating physical characteristics of individual generators, the system-wide requirements that couple all of the generators, and the scenario tree structure for our proposed multistage model. We start with the single-generator polytope and provide convex hull descriptions for the two-period case under different parameter settings. We then provide several families of multiperiod strong valid inequalities linking different scenarios and covering decision variables that represent both power generation and regulation reserve amounts. We further extend our study by exploring the multigenerator polytope and derive strong valid inequalities linking different generators and covering multiple periods. To enhance computational performance, polynomial-time separation algorithms are developed for the exponential number of inequalities. Finally, we verify the effectiveness of our proposed strong valid inequalities by applying them as user cuts under the branch-and-cut scheme to solve multistage stochastic network-constrained power generation scheduling problems. [ABSTRACT FROM AUTHOR]

Statistical database auditing is the process of checking aggregate queries that are submitted in a continuous manner, to prevent inference disclosure. Compared to other data protection mechanisms, auditing has the features of flexibility and maximum information. Auditing is typically accomplished by examining responses to past queries to determine whether a new query can be answered. It has been recognized that query denials release information and can cause data disclosure. This paper proposes an auditing mechanism that is free of query denial threat and applicable to mixed types of aggregate queries, including sum, max, min, deviation, etc. The core ideas are (i) deriving the complete information leakage from each query denial and (ii) carrying the complete leaked information derived from past answered and denied queries to audit each new query. The information leakage deriving problem can be formulated as a set of parametric optimization programs, and the whole auditing process can be modeled as a series of convex optimization problems. [ABSTRACT FROM AUTHOR]

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. [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]

In 2007, W. H. Cunningham and J. Geelen describe an algorithm for solving max{cT x: Ax = b, ≧ 0, x ∈ ℤn} where A ∈ ℤmxn≧0, b ∈ ℤm and c ∈ ℤn which utilizes a branch-decomposition of the matrix A and techniques from dynamic programming. In this paper, we report on the first implementation of the CG algorithm and compare our results with the commercial integer programming software Gurobi. Using branch-decomposition trees produced by heuristics and optimal trees produced by algorithms developed in our previous studies, we test both a memory-intensive and low-memory version of the CG algorithm on problem instances such as graph 3-coloring, set partition, market split, and knapsack. We isolate a class of set partition instances where the CG algorithm runs twice as fast as Gurobi, and demonstrate that certain infeasible market split and knapsack instances with width ≦6 range from running twice as fast as Gurobi, to running in a matter of minutes versus a matter of hours. [ABSTRACT FROM AUTHOR]

This paper presents a binary search heuristic algorithm for the rectangular strip-packing problem. The problem is to pack a number of rectangles into a sheet of given width and infinite height so as to minimize the required height. We first transform this optimization problem into a decision problem. A least-waste-first strategy and a minimal-inflexion-first strategy are proposed to solve the related decision problem. Lastly, we develop a binary search heuristic algorithm based on randomized local search to solve the original optimization problem. The computational results on six classes of benchmark problems have shown that the presented algorithm can find better solutions within a reasonable time than the published best heuristic algorithms for most zero-waste instances. In particular, the presented algorithm is proved to be the dominant algorithm for large zero-waste instances. [ABSTRACT FROM AUTHOR]

Some existing simulation optimization algorithms (e.g., adaptive random search) become pure random search methods and thus are ineffective for the zero-one optimization via simulation problem. In this paper, we present highly efficient rapid screening procedures for solving the zero-one optimization via simulation problem. Three approaches adopting different sampling rules and providing different statistical guarantees are described. We also propose efficient neighborhood search methods and a simple algorithm for generation of initial solutions, all of which can be incorporated into our rapid screening procedures. The proposed procedures are more adaptive than ordinary ranking and selection procedures because in each iteration they can eliminate inferior solutions and intelligently sample promising solutions from the neighborhood of the survivors. Empirical studies are performed to compare the efficiency of the proposed procedures with other existing ones. [ABSTRACT FROM AUTHOR]

This paper presents a simple branch-and-bound method based on Lagrangean relaxation and subgradient optimization for solving large instances of the capacitated facility location problem (CFLP) to optimality. To guess a primal solution to the Lagrangean dual, we average solutions to the Lagrangean subproblem. Branching decisions are then based on this estimated (fractional) primal solution. Extensive numerical results reveal that the method is much faster and more robust than other state-of-the-art methods for solving the CFLP exactly. [ABSTRACT FROM AUTHOR]

The explosive growth in the variety and size of social networks has focused attention on searching these networks for useful structures. Like the Internet or the telephone network, the ability to efficiently search large social networks will play an important role in the extent of their use by individuals and organizations alike. However, unlike these domains, search on social networks is likely to involve measures that require a set of individuals to collectively satisfy some skill requirement or be tightly related to each other via some underlying social property of interest. The aim of this paper is to highlight--and demonstrate via specific examples--the need for algorithmic results for some fundamental set-based notions on which search in social networks is expected to be prevalent. To this end, we argue that the concepts of an influential set and a central set that highlight, respectively, the specific role and the specific location of a set are likely to be useful in practice. We formulate two specific search problems: the elite group problem (EGP) and the portal problem (PP), that represent these two concepts and provide a variety of algorithmic results. We first demonstrate the relevance of EGP and PP across a variety of social networks reported in the literature. For simple networks (e.g., structured trees and bipartite graphs, cycles, paths), we show that an optimal solution to both EGP and PP is easy to obtain. Next, we show that EGP is polynomially solvable on a general graph, whereas PP is strongly NP-hard. Motivated by practical considerations, we also discuss (i) a size-constrained variant of EGP together with its penalty-based relaxation and (ii) the solution of PP on balanced and full d-trees and general trees. [ABSTRACT FROM AUTHOR]