Search

Despite the successful applications of decision diagrams (DDs) to solve various classes of integer programs in the literature, the question of which mixed-integer structures admit a DD representation remains open. The present work addresses this question by developing both necessary and sufficient conditions for a mixed-integer program to be DD-representable through identification of certain rectangular formations in the underlying sets. This so-called rectangularization framework is applicable to all bounded mixed-integer linear programs, providing a notable extension of the DD domain to continuous problems. As an application, the paper uses the developed methods to solve stochastic unit commitment problems in energy systems. Computational experiments conducted on benchmark instances show that the DD approach uniformly and significantly outperforms the existing solution methods and modern solvers. The proposed methodology opens new pathways to solving challenging mixed-integer programs in energy systems more efficiently. Over the past decade, decision diagrams (DDs) have been used to model and solve integer programming and combinatorial optimization problems. Despite successful performance of DDs in solving various discrete optimization problems, their extension to model mixed-integer programs (MIPs), such as those appearing in energy applications, is lacking. More broadly, the question of which problem structures admit a DD representation is still open in the DD community. In this paper, we address this question by introducing a geometric decomposition framework based on rectangular formations that provides both necessary and sufficient conditions for a general MIP to be representable by DDs. As a special case, we show that any bounded mixed-integer linear program admits a DD representation through a specialized Benders decomposition technique. The resulting DD encodes both integer and continuous variables and, therefore, is amenable to the addition of feasibility and optimality cuts through refinement procedures. As an application for this framework, we develop a novel solution methodology for the unit commitment problem (UCP) in the wholesale electricity market. Computational experiments conducted on a stochastic variant of the UCP show a significant improvement of the solution time for the proposed method when compared with the outcome of modern solvers. History: This paper has been accepted for the Operations Research Special Issue on Computational Advances in Short-Term Power System Operations. Funding: This work was supported by the Iowa Economic Development Authority [Grant 20IEC005]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2353. [ABSTRACT FROM AUTHOR]

Selecting the optimal policy using simulation is subject to input model risk when input models that mimic real-world randomness in the simulation have estimation error due to finite sample sizes. Instead of trying to find the optimal solution under unknown real-world input distributions by taking a conservative stance or with low statistical guarantee, the input–output uncertainty comparisons (IOU-C) procedure finds a set of solutions that cannot be separated from the best given the resolution decided by the finite sample sizes. The common-input-data (CID) effects measure how differently solutions are affected by the common estimated input models. When CID effects of two systems are positively correlated, the comparison becomes easier than estimating the performance measures of two systems precisely under input model risk; the IOU-C procedure takes advantage of the CID effects to develop a sharp comparison and thereby provides a small subset even in the presence of input model risk. When input distributions to a simulation model are estimated from real-world data, they naturally have estimation error causing input uncertainty in the simulation output. If an optimization via simulation (OvS) method is applied that treats the input distributions as "correct," then there is a risk of making a suboptimal decision for the real world, which we call input model risk. This paper addresses a discrete OvS (DOvS) problem of selecting the real-world optimal from among a finite number of systems when all of them share the same input distributions estimated from common input data. Because input uncertainty cannot be reduced without collecting additional real-world data—which may be expensive or impossible—a DOvS procedure should reflect the limited resolution provided by the simulation model in distinguishing the real-world optimal solution from the others. In light of this, our input–output uncertainty comparisons (IOU-C) procedure focuses on comparisons rather than selection: it provides simultaneous confidence intervals for the difference between each system's real-world mean and the best mean of the rest with any desired probability, while accounting for both stochastic and input uncertainty. To make the resolution as high as possible (intervals as short as possible) we exploit the common input data effect to reduce uncertainty in the estimated differences. Under mild conditions we prove that the IOU-C procedure provides the desired statistical guarantee asymptotically as the real-world sample size and simulation effort increase, but it is designed to be effective in finite samples. The electronic companion of this paper is available at https://doi.org/10.1287/opre.2018.1796. [ABSTRACT FROM AUTHOR]

In many classical combinatorial optimization problems, including critical and shortest paths, maximum flow, and network reliability, the introduction of uncertainty considerably complicates the calculation of system performance. In fact, in these contexts, computing system performance exactly can often be an impossible task. Therefore, obtaining (stochastic) bounds on the system's performance becomes an attractive and useful alternative. This paper studies several stochastic bounds that are applicable to these contexts and to a broader set of problems that can be described by the general combinatorial concepts of clutters and blocking clutters. We begin our discussion by defining these unifying concepts and illustrating their specialization in several problem contexts. [ABSTRACT FROM AUTHOR]

This paper studies a novel decomposition scheme, utilizing decision diagrams for modeling elements of a problem where typical linear relaxations fail to provide sufficiently tight bounds. Given a collection of decision diagrams, each representing a portion of the problem, together with linear inequalities modeling other portions of the problem, how can one efficiently optimize over such a representation? In this paper, we model the problem as a consistent path problem, where a path in each diagram has to be identified, all of which agree on the value assignments to variables. We establish complexity results and propose a branch-and-cut framework for solving the decomposition. Through application to binary cubic optimization and a variant of the market split problem, we show that the decomposition approach provides significant improvement gains over standard linear models. The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to use not one, but a set of diagrams, to model constraints and objective function terms. Optimizing over a collection of decision diagrams, the problem we refer to as the consistent path problem (CPP) can be addressed by associating a network-flow model with each decision diagram, jointly linked through channeling constraints. A direct application of integer programming to the ensuing model has already been shown to result in algorithms that provide orders-of-magnitude performance gains over classical methods. Lacking, however, is a careful study of dedicated solution methods designed to solve the CPP. This paper provides a detailed study of the CPP, including a discussion on complexity results and a complete polyhedral analysis. We propose a cut-generation algorithm, which, under a structured ordering property, finds a cut, if one exists, through an application of the classical maximum flow problem, albeit in an exponentially sized network. We use this procedure to fuel a cutting-plane algorithm that is applied to unconstrained binary cubic optimization and a variant of the market split problem, resulting in an algorithm that compares favorably with CPLEX, using standard integer programming formulations for both problems. [ABSTRACT FROM AUTHOR]

The multiple vehicle routing problem with time windows (VRPTW) is a hard and extensively studied combinatorial optimization problem. This paper considers a dynamic VRPTW with stochastic customers, where the goal is to maximize the number of serviced customers. It presents a multiple scenario approach (MSA) that continuously generates routing plans for scenarios including known and future requests. Decisions during execution use a distinguished plan chosen, at each decision, by a consensus function. The approach was evaluated on vehicle routing problems adapted from the Solomon benchmarks with a degree of dynamism varying between 30% and 80%. They indicate that MSA exhibits dramatic improvements over approaches not exploiting stochastic information, that the use of consensus function improves the quality of the solutions significantly, and that the benefits of MSA increase with the (effective) degree of dynamism. [ABSTRACT FROM AUTHOR]

Accurate yield prediction in integrated circuit manufacturing enables accurate estimation of production cost and early detection of processing problems. It is known that defects tend to be clustered and a chip is likely to be defective if its neighbors are defective. This neighborhood effect is not well captured in traditional yield modeling approaches. We propose a new yield prediction model, called adjacency-clustering which addresses, for the first time, the neighborhood effect, and delivers prediction results that are significantly better than state-of-the-art methods. Adjacency-clustering (AC) model is a form of the Markov random field minimum energy model (MRF) that is primarily known in the context of image segmentation. AC model is a novel use of MRF for identifying defect patterns that enable diagnosis of failure causes in the manufacturing process. In this paper we utilize the defect patterns obtained by the AC model for yield prediction. We compare the performance of the AC model to that of leading yield prediction models including the Poisson, the negative binomial, the Poisson regression, and negative binomial regression models, on real data sets and on simulated data sets. The results demonstrate that the adjacency-clustering model captures the neighborhood effect and delivers superior prediction accuracy. Moreover, the concept and methodology of adjacency-clustering are not limited to integrated circuit manufacturing. Rather, it is applicable in any context where a neighborhood effect is present, such as disease risk mapping and energy consumption prediction. The e-companion is available at https://doi.org/10.1287/opre.2018.1741. [ABSTRACT FROM AUTHOR]

In this paper, we describe an effective exact method for solving both the capacitated vehicle routing problem (CVRP) and the vehicle routing problem with time windows (VRPTW) that improves the method proposed by Baldacci et al. [Baldacci, R., N. Christofides, A. Mingozzi. 2008. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2) 351-385] for the CVRP. The proposed algorithm is based on the set partitioning (SP) formulation of the problem. We introduce a new route relaxation called ng-route, used by different dual ascent heuristics to find near-optimal dual solutions of the LP-relaxation of the SP model. We describe a column-and-cut generation algorithm strengthened by valid inequalities that uses a new strategy for solving the pricing problem. The new ng-route relaxation and the different dual solutions achieved allow us to generate a reduced SP problem containing all routes of any optimal solution that is finally solved by an integer programming solver. The proposed method solves four of the five open Solomon's VRPTW instances and significantly improves the running times of state-of-the-art algorithms for both VRPTW and CVRP. [ABSTRACT FROM AUTHOR]

The pickup and delivery problem with time windows (PDPTW) is a generalization of the vehicle routing problem with time windows. In the PDPTW, a set of identical vehicles located at a central depot must be optimally routed to service a set of transportation requests subject to capacity, time window, pairing, and precedence constraints. In this paper, we present a new exact algorithm for the PDPTW based on a set-partitioning-like integer formulation, and we describe a bounding procedure that finds a near-optimal dual solution of the LP-relaxation of the formulation by combining two dual ascent heuristics and a cut-and-column generation procedure. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between a known upper bound and the lower bound achieved. If the resulting problem has moderate size, it is solved by an integer programming solver; otherwise, a branch-and-cut-and-price algorithm is used to close the integrality gap. Extensive computational results over the main instances from the literature show the effectiveness of the proposed exact method. [ABSTRACT FROM AUTHOR]

This paper presents an exact algorithm for solving strategic and tactical multiperiod vehicle routing problems that can be modeled as period vehicle routing problems (PVRPs). The PVRP is defined on a time horizon of several days and consists of assigning appropriate combinations of delivery to customers and designing a set of delivery routes for every day of the planning period. The objective is to service all customers assigned to each day minimizing the overall routing cost. This paper describes an integer programming formulation of the PVRP that is used to derive different lower bounds and an exact solution method. Computational results on test instances from the literature and on new sets of test instances show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This paper presents a branch-and-cut-and-price algorithm for the vehicle-routing problem with time windows. The standard Dantzig-Wolfe decomposition of the arc flow formulation leads to a set-partitioning problem as the master problem and an elementary shortest-path problem with resource constraints as the pricing problem. We introduce the subset-row inequalities, which are Chvatal-Gomory rank-1 cuts based on a subset of the constraints in the master problem. Applying a subsetrow inequality in the master problem increases the complexity of the label-setting algorithm used to solve the pricing problem because an additional resource is added for each inequality. We propose a modified dominance criterion that makes it possible to dominate more labels by exploiting the step-like structure of the objective function of the pricing problem. Computational experiments have been performed on the Solomon benchmarks where we were able to close several instances. The results show that applying subset-row inequalities in the master problem significantly improves the lower bound and, in many cases, makes it possible to prove optimality in the root node. [ABSTRACT FROM AUTHOR]

An innovative approach to DNA sequencing by hybridization utilizes isothermic oligonucleotide libraries. In this paper, we demonstrate the utility of a genetic algorithm for the combinatorial portion of this new approach by incorporating characteristics of DNA sequencing by hybridization in addition to isothermic oligonucleotide libraries. Specialized crossover and mutation operators were developed for this purpose. After initial experiments for parameter adjustment, the performance of the genetic algorithm approach was evaluated with respect to previous methods in the literature. The results indicate that the proposed new approach is superior to previous approaches. The proposed new crossover operator that inherits some features of the structured weighted combinations might also be of value for some other combinatorial problems, including the traveling salesman problem. [ABSTRACT FROM AUTHOR]

Combinatorial allocation involves assigning bundles of items to agents when the use of money is not allowed. Course allocation is one common application of combinatorial allocation, in which the bundles are schedules of courses and the assignees are students. Existing mechanisms used in practice have been shown to have serious flaws, which lead to allocations that are inefficient, unfair, or both. A recently developed mechanism is attractive in theory but has several features that limit its feasibility for practice. This paper reports on the design and implementation of a new course allocation mechanism, Course Match, that is suitable in practice. To find allocations, Course Match performs a massive parallel heuristic search that solves billions of mixed-integer programs to output an approximate competitive equilibrium in a fake-money economy for courses. Quantitative summary statistics for two semesters of full-scale use at a large business school (the Wharton School of Business, which has about 1,700 students and up to 350 courses in each semester) demonstrate that Course Match is both fair and efficient, a finding reinforced by student surveys showing large gains in satisfaction and perceived fairness. [ABSTRACT FROM AUTHOR]

Effective route planning for battery electric commercial vehicle (ECV) fleets has to take into account their limited autonomy and the possibility of visiting recharging stations during the course of a route. In this paper, we consider four variants of the electric vehicle-routing problem with time windows: (i) at most a single recharge per route is allowed, and batteries are fully recharged on visit of a recharging station; (ii) multiple recharges per route, full recharges only; (iii) at most a single recharge per route, and partial battery recharges are possible; and (iv) multiple, partial recharges. For each variant, we present exact branch-price-and-cut algorithms that rely on customized monodirectional and bidirectional labeling algorithms for generating feasible vehicle routes. In computational studies, we find that all four variants are solvable for instances with up to 100 customers and 21 recharging stations. This success can be attributed to the tailored resource extension functions (REFs) that enable efficient labeling with constant time feasibility checking and strong dominance rules, even if these REFs are intricate and rather elaborate to derive. The studies also highlight the superiority of the bidirectional labeling algorithms compared to the monodirectional ones. Finally, we find that allowing multiple as well as partial recharges both help to reduce routing costs and the number of employed vehicles in comparison to the variants with single and with full recharges. [ABSTRACT FROM AUTHOR]

Designing optimal--that is, revenue-maximizing--combinatorial auctions (CAs) is an important elusive problem. It is unsolved even for two bidders and two items for sale. Rather than pursuing the manual approach of attempting to characterize the optimal CA, we introduce a family of CAs and then seek a high-revenue auction within that family. The family is based on bidder weighting and allocation boosting; we coin such CAs virtual valuations combinatorial auctions (VVCAs). VVCAs are the Vickrey-Clarke-Groves (VCG) mechanism executed on virtual valuations that are affine transformations of the bidders' valuations. The auction family is parameterized by the coefficients in the transformations. The problem of designing a CA is thereby reduced to search in the parameter space of VVCA--or the more general space of affine maximizer auctions. We first construct VVCAs with logarithmic approximation guarantees in canonical special settings: (1) limited supply with additive valuations and (2) unlimited supply. In the main part of the paper, we develop algorithms that design high-revenue CAs for general valuations using samples from the prior distribution over bidders' valuations. (Priors turn out to be necessary for achieving high revenue.) We prove properties of the problem that guide our design of algorithms. We then introduce a series of algorithms that use economic insights to guide the search and thus reduce the computational complexity. Experiments show that our algorithms create mechanisms that yield significantly higher revenue than the VCG and scale dramatically better than prior automated mechanism design algorithms. The algorithms yielded deterministic mechanisms with the highest known revenues for the settings tested, including the canonical setting with two bidders, two items, and uniform additive valuations. 1 [ABSTRACT FROM AUTHOR]

In several scientific and industrial applications, it is desirable to build compact, interpretable learning models where the output depends on a small number of input features. Recent work has shown that such best-subset selection-type problems can be solved with modern mixed integer optimization solvers. Despite their promise, such solvers often come at a steep computational price when compared with open-source, efficient specialized solvers based on convex optimization and greedy heuristics. In "Fast Best-Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms," Hussein Hazimeh and Rahul Mazumder push the frontiers of computation for best-subset-type problems. Their algorithms deliver near-optimal solutions for problems with up to a million features—in times comparable with the fast convex solvers. Their work suggests that principled optimization methods play a key role in devising tools central to interpretable machine learning, which can help in gaining a deeper understanding of their statistical properties. The L0-regularized least squares problem (a.k.a. best subsets) is central to sparse statistical learning and has attracted significant attention across the wider statistics, machine learning, and optimization communities. Recent work has shown that modern mixed integer optimization (MIO) solvers can be used to address small to moderate instances of this problem. In spite of the usefulness of L0-based estimators and generic MIO solvers, there is a steep computational price to pay when compared with popular sparse learning algorithms (e.g., based on L1 regularization). In this paper, we aim to push the frontiers of computation for a family of L0-regularized problems with additional convex penalties. We propose a new hierarchy of necessary optimality conditions for these problems. We develop fast algorithms, based on coordinate descent and local combinatorial optimization, that are guaranteed to converge to solutions satisfying these optimality conditions. From a statistical viewpoint, an interesting story emerges. When the signal strength is high, our combinatorial optimization algorithms have an edge in challenging statistical settings. When the signal is lower, pure L0 benefits from additional convex regularization. We empirically demonstrate that our family of L0-based estimators can outperform the state-of-the-art sparse learning algorithms in terms of a combination of prediction, estimation, and variable selection metrics under various regimes (e.g., different signal strengths, feature correlations, number of samples and features). Our new open-source sparse learning toolkit L0Learn (available on CRAN and GitHub) reaches up to a threefold speedup (with p up to 106) when compared with competing toolkits such as glmnet and ncvreg. [ABSTRACT FROM AUTHOR]

The problem of coordinating a fleet of vehicles so that all demand points on a territory are serviced and the workload is most evenly distributed among the vehicles is a hard one. For this reason, it is often an effective strategy to first divide the service region and impose that each vehicle is only responsible for its own subregion. This heuristic also has the practical advantage that over time, drivers become more effective at serving their territory and customers. In this paper, we assume that client locations are unknown at the time of partitioning the territory and that each of them will be drawn identically and independently according to a distribution that is actually also unknown. In practice, it might be impossible to identify precisely the distribution if, for instance, information about the demand is limited to historical data. Our approach suggests partitioning the region with respect to the worst-case distribution that satisfies first- and second-order moments information. As a side product, our analysis constructs for each subregion a closed-form expression for the worst-case density function, thus providing useful insights about what affects the completion time most heavily. The successful implementation of our approach relies on two branch-and-bound algorithms: whereas the first finds a globally optimal partition of a convex polygon into two convex subregions, the second finds a local optimum for the harder n-partitioning problem. Finally, simulations of a parcel delivery problem will demonstrate that our data-driven approach makes better use of historical data as it becomes available. [ABSTRACT FROM AUTHOR]

In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the makespan objective, robust versions of weighted multiobjective optimization problems, and assortment optimization problems with logit choice models. The main idea behind our approximation schemes is the construction of an approximate Pareto-optimal frontier of the functions that constitute the given objective. Using this idea, we give the first fully polynomial-time approximation schemes for the max-min resource allocation problem with a fixed number of agents, combinatorial optimization problems in which the objective function is the sum of a fixed number of ratios of linear functions, or the product of a fixed number of linear functions, and assortment optimization problems with logit choice model. [ABSTRACT FROM AUTHOR]

In the two-echelon capacitated vehicle routing problem (2E-CVRP), the delivery to customers from a depot uses intermediate depots, called satellites. The 2E-CVRP involves two levels of routing problems. The first level requires a design of the routes for a vehicle fleet located at the depot to transport the customer demands to a subset of the satellites. The second level concerns the routing of a vehicle fleet located at the satellites to serve all customers from the satellites supplied from the depot. The objective is to minimize the sum of routing and handling costs. This paper describes a new mathematical formulation of the 2E-CVRP used to derive valid lower bounds and an exact method that decomposes the 2E-CVRP into a limited set of multidepot capacitated vehicle routing problems with side constraints. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods. [ABSTRACT FROM AUTHOR]

We address the exact solution of the famous esc instances of the quadratic assignment problem. These are extremely hard instances that remained unsolved--even allowing for a tremendous computing power--by using all previous techniques from the literature. During this challenging task we found that three ideas were particularly useful and qualified as a breakthrough for our approach. The present paper is about describing these ideas and their impact in solving esc instances. Our method was able to solve, in a matter of seconds or minutes on a single PC, all easy cases (all esc16* plus esc32e and esc32g). The three very hard instances esc32c, esc32d, and esc64a were solved in less than half an hour, in total, on a single PC. We also report the solution, in about five hours, of tai64c. By using a facility-flow splitting procedure, we were also able to solve to proven optimality, for the first time, esc32h (in about two hours) as well as "the big fish" esc128. (To our great surprise, the solution of the latter required just a few seconds on a single PC.) [ABSTRACT FROM AUTHOR]

In this paper, we outline the development of the core optimization technology used within a decision support tool to help providers and caretakers in constructing catch-up schedules for childhood immunization. These schedules ensure that a child continues to receive timely coverage against vaccine-preventable diseases in the likely event that one or more doses have been delayed. This project was undertaken as part of a collaborative effort between the Centers for Disease Control and Prevention (CDC) and Georgia Institute of Technology. Our aim is to develop a decision support tool that removes from the task of constructing catch-up schedules the tedious combinatorial aspects, while maintaining a level of generality that allows easy accommodation for changes in the existing rules and adding new vaccines to the schedule lineup. We show that the catch-up scheduling problem is NP-hard, and we develop a dynamic programming algorithm that exploits the typical size and structure of the problem to construct optimized schedules almost at the click of a button. In using an optimization-based algorithm, our approach is unique not only in methodology but also in the information, strategy, and advice we can offer to the user. The tool is being advocated by both the CDC and the American Academy of Pediatrics (AAP) as a means of encouraging caretakers and providers to take a more proactive role in ensuring timely vaccination coverage for children, as well as ensuring the accuracy and quality of a catch-up regime. [ABSTRACT FROM AUTHOR]

Latin hypercube designs (LHDs) play an important role when approximating computer simulation models. To obtain good space-filling properties, the maximin criterion is frequently used. Unfortunately, constructing maximin LHDs can be quite time consuming when the number of dimensions and design points increase. In these cases, we can use heuristical maximin LHDs. In this paper, we construct bounds for the separation distance of certain classes of maximin LHDs. These bounds are useful for assessing the quality of heuristical maximin LHDs. Until now only upper bounds are known for the separation distance of certain classes of unrestricted maximin designs, i.e., for maximin designs without a Latin hypercube structure. The separation distance of maximin LHDs also satisfies these "unrestricted" bounds. By using some of the special properties of LHDs, we are able to find new and tighter bounds for maximin LHDs. Within the different methods used to determine the upper bounds, a variety of combinatorial optimization techniques are employed. Mixed-integer programming, the traveling salesman problem, and the graph-covering problem are among the formulations used to obtain the bounds. Besides these bounds, also a construction method is described for generating LHDs that meet Baer's bound for l∞ the distance measure for certain values of n. [ABSTRACT FROM AUTHOR]

One of the most common approaches for multiobjective optimization is to generate the whole or partial efficient frontier and then decide about the preferred solution in a higher-level decision-making process. In this paper, a new method for generating the efficient frontier for multiobjective problems is developed, called the diversity maximization approach (DMA). This approach is capable of solving mixed-integer and combinatorial problems. The DMA finds Pareto optimal solutions by maximizing a proposed diversity measure and guarantees generating the complete set of efficient points. Given a subset of the efficient frontier, DMA finds the next Pareto optimal solution which, combined with the existing ones, yields the most diversified subset of efficient points. This solution is defined as the most diverse solution. In fact, it aims to maximize the distance between the new efficient point and the closest point in the given subset of the efficient frontier. The proposed approach can be applied to any problem that can be solved for the single-objective case. We can use the DMA by solving directly a modified version of the mixed-integer programming (MIP) formulation of the multiobjective problem. In this case, the Pareto optimal solutions are found sequentially in an iterative way. Consequently, as we terminate the procedure before completion, a partial efficient frontier is available. The diversity measure assures that in every stage of the procedure, the partial efficient frontier is well diversified. This partial efficient frontier can be perceived as a filtered set of the complete efficient frontier and can be used by the decision maker in case the complete efficient frontier contains too many points. An additional way of using DMA is by incorporating it in a problem oriented branch-and-bound algorithm. Detailed examples of both approaches are given. [ABSTRACT FROM AUTHOR]

We consider the problem of finding an optimal schedule for jobs on a single machine when there are penalties for both tardy and early arrivals. We point out that if attention is paid to how these penalties are measured, then a change of scale of measurement might lead to the anomalous situation where a schedule is optimal if these parameters are measured in one way, but not if they are measured in a different way that seems equally acceptable. In particular, we note that if the penalties measure utilities or disutilities, or loss of goodwill or customer satisfaction, then these kinds of anomalies can occur, for instance if we change both unit and zero point in scales measuring these penalties. We investigate situations where problems of these sorts arise for four specific penalty functions under a variety of different assumptions. The results of the paper have implications far beyond the specific scheduling problems we consider, and suggest that considerations of scale of measurement should enter into analysis of conclusions of optimality both in scheduling problems and throughout combinatorial optimization. [ABSTRACT FROM AUTHOR]

In this and two companion papers, we report on an extended empirical study of the simulated annealing approach to combinatorial optimization proposed by S. Kirkpatrick et al. That study investigated how best to adapt simulated annealing to particular problems and compared its performance to that of more traditional algorithms. This paper (Part I) discusses annealing and our parameterized generic implementation of it, describes how we adapted this generic algorithm to the graph partitioning problem, and reports how well it compared to standard algorithms like the Kernighan-Lin algorithm. (For sparse random graphs, it tended to outperform Kernighan-Lin as the number of vertices become large, even when its much greater running time was taken into account. It did not perform nearly so well, however, on graphs generated with a built-in geometric structure.) We also discuss how we went about optimizing our implementation, and describe the effects of changing the various annealing parameters or varying the basic annealing algorithm itself. [ABSTRACT FROM AUTHOR]

In this paper we use Fulkerson's antiblocking theory as a framework in which to explore certain combinatorial properties of network flows. In particular, we derive a surprising round-off result for a class of integer covering problems. When combined with Edmond's characterization of the matching polytope, our results yield an interesting proposition concerning the four-color conjecture. Our goal in presenting this proposition is not so much to propose a new approach to the famous conjecture as it is to present an interesting example of the interrelation of a number of seemingly diverse areas of combinatorics and combinatorial optimization--in particular, antiblocking and minimum coverings, integer network flows, edge matchings in graphs, and graph coloring. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new probabilistic model for minimizing the anticipated regret in combinatorial optimization problems with distributional uncertainty in the objective coefficients. The interval uncertainty representation of data is supplemented with information on the marginal distributions. As a decision criterion, we minimize the worst-case conditional value at risk of regret. The proposed model includes the interval data minmax regret model as a special case. For the class of combinatorial optimization problems with a compact convex hull representation, a polynomial sized mixed-integer linear program is formulated when (a) the range and mean are known, and (b) the range, mean, and mean absolute deviation are known; and a mixed-integer second order cone program is formulated when (c) the range, mean, and standard deviation are known. For the subset selection problem of choosing K elements of maximum total weight out of a set of N elements, the probabilistic regret model is shown to be solvable in polynomial time in the instances (a) and (b) above. This extends the current known polynomial complexity result for minmax regret subset selection with range information only. [ABSTRACT FROM AUTHOR]

This is the second in a series of three papers that empirically examine the competitiveness of simulated annealing in certain well-studied domains of combinatorial optimization. Simulated annealing is a randomized technique proposed by S. Kirkpatrick, C D. Gelatt and M P. Vecchi for improving local optimization algorithms. Here we report on experiments at adapting simulated annealing to graph colortag and number partitioning, two problems for which local optimization had not previously been thought suitable. For graph coloring, we report on three simulated annealing schemes, all of which can dominate traditional techniques for certain types of graphs, at least when large amounts of computing rune are available. For number partitioning, simulated annealing is not competitive with the differencing algorithm of N. Karmarkar and R. M Karp, except on relatively small instances. Moreover, if running time is taken into account, natural annealing schemes cannot even outperform multiple random runs of the local optimization algorithms on which they are based, in sharp contrast to the observed performance of annealing on other problems. [ABSTRACT FROM AUTHOR]

Consider a complete graph G = (K, E) in which each node is present with probability p,. We are interested in solving combinatorial optimization problems on subsets of nodes which are present with a certain probability. We introduce the idea of a priori optimization as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problem is solved optimally for every instance. We consider four problems: the traveling salesman problem (TSP), the minimum spanning tree, vehicle routing, and traveling salesman facility location. We discuss the applicability of a priori optimization strategies in several areas and show that if the nodes are randomly distributed in the plane the a priori and reoptimization strategies are very close in terms of performance. We characterize the complexity of a priori optimization and address the question of approximating the optimal a priori solutions with polynomial time heuristics with provable worst-case guarantees. Finally, we use the TSP as an example to find practical solutions based on ideas of local optimality. [ABSTRACT FROM AUTHOR]

The placement of text on a map to maximize map legibility, while avoiding graphic overplotting, is a problem in combinatorial optimization. This particular optimization problem can be formulated as a multiple choice integer programming problem, and the integer programming problem has a structure that can be exploited, using a Lagrangian heuristic, to obtain a cost effective solution, even when tens of thousands of variables and thousands of constraints are involved. This paper presents the mathematical formulation of the map label placement problem and describes a computer program implemented to solve it. [ABSTRACT FROM AUTHOR]

Many interesting combinatorial problems can be optimized efficiently using recursive computations often termed discrete dynamic programming. In this paper, we develop a paradigm for a general class of such optimizations that yields a polyhedral description for each model in the class. The elementary concept of dynamic programs as shortest path problems in acyclic graphs is generalized to one seeking a least cost solution in a directed hypergraph. Sufficient conditions are then provided for binary integrality of the associated hyperflow problem. Given a polynomially solvable dynamic program, the result is a linear program, in polynomially many variables and constraints, having the solution vectors of the dynamic program as its extreme-point optima. That is, the linear program provides a succinct characterization of the solutions to the underlying optimization problem expressed through an appropriate change of variables. We also discuss projecting this formulation to recover constraints on the original variables and illustrate how some important dynamic programming solvable models fit easily into our paradigm. A classic multiechelon lot sizing problem in production and a host of optimization problems on recursively defined classes of graphs are included. [ABSTRACT FROM AUTHOR]

We know that the effectiveness of the branch-and-bound algorithms proposed for the solution of combinatorial optimization problems greatly depends on the tightness of the available bounds. In this paper, we consider optimization problems with a linear objective function. We propose an additive approach for computing lower bounds that yields an increasing sequence of values. An application to the traveling salesman problem with precedence constraints is presented to exemplify the technique. [ABSTRACT FROM AUTHOR]

A nonstationary Markov chain is weakly ergodic if the dependence of the state distribution on the starting state vanishes as time tends to infinity. A chain is strongly ergodic if it is weakly ergodic and converges in distribution. In this paper we show that the two ergodicity concepts are equivalent for finite chains under rather general (and widely verifiable) conditions. We discuss applications to probabilistic analyses of general search methods for combinatorial optimization problems (simulated annealing). [ABSTRACT FROM AUTHOR]

The linear ordering problem is an NP-hard combinatorial optimization problem with a large number of applications (including triangulation of input-output matrices, archaeological senation, minimizing total weighted completion time in one-machine scheduling, and aggregation of individual preferences). In a former paper, we have investigated the facet structure of the 0/1-polytope associated with the linear ordering problem. Here we report on a new algorithm that is based on these theoretical results. The main part of the algorithm is a cutting plane procedure using facet defining inequalities. This procedure is combined with various heuristics and branch and bound techniques. Our computational results compare favorably with the results of existing codes. In particular, we could triangulate all input-output matrices, of size up to 60 x 60, available to us within acceptable time bounds. [ABSTRACT FROM AUTHOR]

Consumers generally do not know about, much less evaluate, the hundreds or thousands of product variations available to them in a category. In many situations, including online shopping, they use product features to sequentially screen the set of available alternatives. In "Randomized algorithms for lexicographic inference," R. Kohli, K. Boughanmi, and V. Kohli describe a method for inferring lexicographic rules from ranking, choice, or paired comparison data. They show that the inference problem is computationally hard (it generalizes the linear ordering problem) and propose a randomized algorithm that explicitly uses statistical distributions, the parameters of which are obtained by maximizing a likelihood function. The expected value of the solution obtained by the randomized algorithm is a function of the likelihood value and has a nontrivial lower bound. In an empirical test, the algorithm found screening rules that predicted consumer preferences substantially better than several competing methods. The inference of a lexicographic rule from paired comparisons, ranking, or choice data is a discrete optimization problem that generalizes the linear ordering problem. We develop an approach to its solution using randomized algorithms. First, we show that maximizing the expected value of a randomized solution is equivalent to solving the lexicographic inference problem. As a result, the discrete problem is transformed into a continuous and unconstrained nonlinear program that can be solved, possibly only to a local optimum, using nonlinear optimization methods. Second, we show that a maximum likelihood procedure, which runs in polynomial time, can be used to implement the randomized algorithm. The maximum likelihood value determines a lower bound on the performance ratio of the randomized algorithm. We employ the proposed approach to infer lexicographic rules for individuals using data from a choice experiment for electronic tablets. These rules obtain substantially better fit and predictions than a previously described greedy algorithm, a local search algorithm, and a multinomial logit model. [ABSTRACT FROM AUTHOR]

In metamodeling, the choice of sampling points is crucial for the quality of the model. In this context, the maximin Latin hypercube designs (LHD), with their spacefilling and noncollapsing properties, are particularly efficient. To this day, there is no polynomial time algorithm that produces optimal maximin LHDs, i.e., in which the minimum distance between two points (the separation distance) is maximal.We are interested in LHDs with a separation distance as large as possible. The algorithm we propose, IES, gives an approximate solution to the LHD problem regardless of its dimension and size with a theoretical performance guarantee. We introduce two upper bounds for the separation distance to find its approximation ratio. Its performance is compared with the best metaheuristic algorithm known for this problem, an appropriate simulated annealing scheme. Our algorithm defeats the metaheuristic algorithm for large instances of the problem while having a very short running time. [ABSTRACT FROM AUTHOR]

Given a polytope X, a monotone concave univariate function g, and two vectors c and d, we study the discrete optimization problem of finding a vertex of X that maximizes the utility function c' x + g( d' x). This problem has numerous applications in combinatorial optimization with a probabilistic objective, including estimation of project duration with stochastic times, in reliability models, in multinomial logit models and in robust optimization. We show that the problem is 풩풫-hard for any strictly concave function g even for simple polytopes, such as the uniform matroid, assignment and path polytopes; and propose a 1/2-approximation algorithm for it. We discuss improvements for special cases where g is the square root, log utility, negative exponential utility and multinomial logit probability function. In particular, for the square root function, the approximation ratio is 4/5. We also propose a 1.25-approximation algorithm for a class of minimization problems in which the maximization of the utility function appears as a subproblem. Although the worst-case bounds are tight, computational experiments indicate that the suggested approach finds solutions within 1%-2% optimality gap for most of the instances, and can be considerably faster than the existing alternatives. [ABSTRACT FROM AUTHOR]

We identify a rich class of finite-horizon Markov decision problems (MDPs) for which the variance of the optimal total reward can be bounded by a simple linear function of its expected value. The class is characterized by three natural properties: reward nonnegativity and boundedness, existence of a do-nothing action, and optimal action monotonicity. These properties are commonly present and typically easy to check. Implications of the class properties and of the variance bound are illustrated by examples of MDPs from operations research, operations management, financial engineering, and combinatorial optimization. [ABSTRACT FROM AUTHOR]

This study presents new exact algorithms for the clustered vehicle routing problem (CluVRP). The CluVRP is a generalization of the capacitated vehicle routing problem (CVRP), in which the customers are grouped into clusters. As in the CVRP, all the customers must be visited exactly once, but a vehicle visiting one customer in a cluster must visit all the remaining customers therein before leaving it. Based on an exponential time preprocessing scheme, an integer programming formulation for the CluVRP is presented. The formulation is enhanced by a polynomial time graph reduction scheme. Two exact algorithms for the CluVRP, a branch and cut as well as a branch and cut and price, are presented. The computational performances of the algorithms are tested on benchmark instances adapted from the vehicle routing problem literature as well as real-world instances from a solid waste collection application. [ABSTRACT FROM AUTHOR]

We consider cooperative traveling salesman games with nonnegative asymmetric costs satisfying the triangle inequality. We construct a stable cost allocation with budget balance guarantee equal to the Held-Karp integrality gap for the asymmetric traveling salesman problem, using the parsimonious property and a previously unknown connection to linear production games. We also show that our techniques extend to larger classes of network design games. We then provide a simple example showing that our cost allocation does not necessarily achieve the best possible budget balance guarantee, even among cost allocations stable for the game defined by the Held-Karp relaxation, and discuss its implications on future work on traveling salesman games. [ABSTRACT FROM AUTHOR]

The robust capacitated vehicle routing problem (CVRP) under demand uncertainty is studied to address the minimum cost delivery of a product to geographically dispersed customers using capacity-constrained vehicles. Contrary to the deterministic CVRP, which postulates that the customer demands for the product are deterministic and known, the robust CVRP models the customer demands as random variables, and it determines a minimum cost delivery plan that is feasible for all anticipated demand realizations. Robust optimization counterparts of several deterministic CVRP formulations are derived and compared numerically. Robust rounded capacity inequalities are developed, and it is shown how they can be separated efficiently for two broad classes of demand supports. Finally, it is analyzed how the robust CVRP relates to the chance-constrained CVRP, which allows a controlled degree of supply shortfall to decrease delivery costs. [ABSTRACT FROM AUTHOR]

We develop a novel framework, the implicit hitting set approach, for solving a class of combinatorial optimization problems. The explicit hitting set problem is as follows: given a set U and a family S of subsets of U, find a minimum-cardinality set that intersects (hits) every set in S. In the implicit hitting set problem (IHSP), the family of subsets S is not explicitly listed (its size is, generally, exponential in terms of the size of U); instead, it is given via a polynomial-time oracle that verifies if a given set H is a hitting set or returns a set in S that is not hit by H. Many NP-hard problems can be straightforwardly formulated as implicit hitting set problems. We show that the implicit hitting set approach is valuable in developing exact and heuristic algorithms for solving this class of combinatorial optimization problems. Specifically, we provide a generic algorithmic strategy, which combines efficient heuristics and exact methods, to solve any IHSP. Given an instance of an IHSP, the proposed algorithmic strategy gives a sequence of feasible solutions and lower bounds on the optimal solution value and ultimately yields an optimal solution. We specialize this algorithmic strategy to solve the multigenome alignment problem and present computational results that illustrate the effectiveness of the implicit hitting set approach. [ABSTRACT FROM AUTHOR]

We develop a family of rollout policies based on fixed routes to obtain dynamic solutions to the vehicle routing problem with stochastic demand and duration limits (VRPSDL). In addition to a traditional one-step rollout policy, we leverage the notions of the pre- and post-decision state to distinguish two additional rollout variants. We tailor our rollout policies by developing a dynamic decomposition scheme that achieves high quality solutions to large problem instances with reasonable computational effort. Computational experiments demonstrate that our rollout policies improve upon the performance of a rolling horizon procedure and commonly employed fixed-route policies, with improvement over the latter being more substantial. [ABSTRACT FROM AUTHOR]

We propose an algorithmic framework that successfully addresses three vehicle routing problems: the multidepot VRP, the periodic VRP, and the multidepot periodic VRP with capacitated vehicles and constrained route duration. The metaheuristic combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and advanced population-diversity management schemes. Extensive computational experiments show that the method performs impressively in terms of computational efficiency and solution quality, identifying either the best known solutions, including the optimal ones, or new best solutions for all currently available benchmark instances for the three problem classes. The proposed method also proves extremely competitive for the capacitated VRP. [ABSTRACT FROM AUTHOR]

We consider the vehicle routing problem with stochastic demands (VRPSD). We give randomized approximation algorithms achieving approximation guarantees of 1 + α for split-delivery VRPSD, and 2 + α for unsplit-delivery VRPSD; here is the best approximation guarantee for the traveling salesman problem. These bounds match the best known for even the respective deterministic problems [Altinkemer, K., B. Gavish. 1987. Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper . Res. Lett. 6(4) 149-158; Altinkemer, K., B. Gavish. 1990. Heuristics for delivery problems with constant error guarantees. Transportation Res. 24(4) 294-297]. We also show that the "cyclic heuristic" for split-delivery VRPSD achieves a constant approximation ratio, as conjectured in Bertsimas [Bertsimas, D. J. 1992. A vehicle routing problem with stochastic demand. [ABSTRACT FROM AUTHOR]

We consider the problem of evaluating the quality of solution sets generated by heuristics for multiple-objective combinatorial optimization problems. We extend previous research on the integrated preference functional (IPF), which assigns a scalar value to a given discrete set of nondominated points so that the weighted Tchebycheff function can be used as the underlying implicit value function. This extension is useful because modeling the decision maker's value function with the weighted Tchebycheff function reflects the impact of unsupported points when evaluating sets of nondominated points. We present an exact calculation method for the IPF measure in this case for an arbitrary number of criteria. We show that every nondominated point has its optimal weight interval for the weighted Tchebycheff function. Accordingly, all nondominated points, and not only the supported points in a set, contribute to the value of the IPF measure when using the weighted Tchebycheff function. Two- and three-criteria numerical examples illustrate the desirable properties of the weighted Tchebycheff function, providing a richer measure than the original IPF based on a convex combination of objectives. [ABSTRACT FROM AUTHOR]

We address a toll pricing problem in which the objective is to minimize the number of required toll facilities in a transportation network while inducing drivers to make the most efficient collective use of the network. We formulate the problem as a mixed-integer programming model and propose a solution method using combinatorial Benders cuts. Computational study of real networks as well as randomly generated networks indicates that our proposed method is efficient in obtaining provably optimal solutions for networks with small to medium sizes. [ABSTRACT FROM AUTHOR]

The ordered open-end bin-packing problem is a variant of the bin-packing problem in which the items to be packed are sorted in a given order and the capacity of each bin can be exceeded by the last item packed into the bin. We present a branch-and-price algorithm for its exact optimization. The pricing subproblem is a special variant of the binary knapsack problem, in which the items are ordered and the last one does not consume capacity. We present a specialized optimization algorithm for this subproblem. The speed of the column generation algorithm is improved by subgradient optimization steps, allowing for multiple pricing and variable fixing. Computational results are presented on instances of different sizes and items with different correlations between their size and their position in the given order. [ABSTRACT FROM AUTHOR]

We consider the problem of dynamically cross-selling products (e.g., books) or services (e.g., travel reservations) in the e-commerce setting. In particular, we look at a company that faces a stream of stochastic customer arrivals and may offer each customer a choice between the requested product and a package containing the requested product as well as another product, what we call a "packaging complement." Given consumer preferences and product inventories, we analyze two issues: (1) how to select packaging complements, and (2) how to price product packages to maximize profits. We formulate the cross-selling problem as a stochastic dynamic program blended with combinatorial optimization. We demonstrate the state-dependent and dynamic nature of the optimal package selection problem and derive the structural properties of the dynamic pricing problem. In particular, we focus on two practical business settings: with (the Emergency Replenishment Model) and without (the Lost-Sales Model) the possibility of inventory replenishment in the case of a product stockout. For the Emergency Replenishment Model, we establish that the problem is separable in the initial inventory of all products, and hence the dimensionality of the dynamic program can be significantly reduced. For both models, we suggest several packaging/pricing heuristics and test their effectiveness numerically. [ABSTRACT FROM AUTHOR]

We develop a method for computing efficient patient-specific drug protocols. Using this method, we identify two general categories of anticancer drug protocols, depending on the temporal cycle parameters of the host and cancer cells: a one-time intensive treatment, or a series of nonintensive treatments. Our method is based on a theoretical and experimental work showing that treatment efficacy can be improved by determining the dosing frequency on the drug-susceptible target and host cell-cycle parameters. Simulating the patient's pharmaco-dynamics in a simple model for cell population growth, we calculate the number of drug susceptible cells at every moment of therapy. Local search heuristics are then used to conduct a search for the desired solution, as defined by our criteria. These criteria include the patient's state at the end of a predetermined time period, the number of cancer and host cells at the end of treatment, and the time to the patient's cure. The process suggested here does not depend on the exact biological assumptions of the model, thus enabling its use in a more complex description of the system. We test three solution methods. Simulated annealing is compared to threshold acceptance and old bachelor acceptance, which are less known variants to this method. The conclusions concerning the three approximation methods are that good results can be achieved by choosing the proper parameters for each of the methods, but the computational effort required for achieving good results is much greater in simulated annealing than in the other methods. Also, a large number of iterations does not guarantee better solution quality, and resources would be better used in several short searches with different parameter values than in one long search. [ABSTRACT FROM AUTHOR]