Search

A New Family of Valid-Inequalities for Dantzig-Wolfe Reformulation of Mixed Integer Linear Programs In "Consistency Cuts for Dantzig-Wolfe Reformulation," Jens Vinther Clausen, Richard Lusby, and Stefan Ropke present a new family of valid inequalities to be applied to Dantzig-Wolfe reformulations with binary linking variables. They show that, for Dantzig-Wolfe reformulations of mixed integer linear programs that satisfy certain properties, it is enough to solve the linear programming relaxation of the Dantzig-Wolfe reformulation with all consistency cuts to obtain integer solutions. An example of this is the temporal knapsack problem; the effectiveness of the cuts is tested on a set of 200 instances of this problem, and the results are state-of-the-art solution times. For problems that do not satisfy these conditions, the cuts can still be used in a branch-and-cut-and-price framework. In order to show this, the cuts are applied to a set of generic mixed linear integer programs from the online library MIPLIB. These tests show the applicability of the cuts in general. This paper introduces a family of valid inequalities, which we term consistency cuts, to be applied to a Dantzig-Wolfe reformulation (or decomposition) with linking variables. We prove that these cuts ensure an integer solution to the corresponding Dantzig-Wolfe relaxation when certain criteria to the structure of the decomposition are met. We implement the cuts and use them to solve a commonly used test set of 200 instances of the temporal knapsack problem. We assess the performance with and without the cuts and compare further to CPLEX and other solution methods that have historically been used to solve the test set. By separating consistency cuts, we show that we can obtain optimal integer solutions much faster than the other methods and even solve the remaining unsolved problems in the test set. We also perform a second test on instances from the MIPLIB 2017 online library of mixed-integer programs, showing the potential of the cuts on a wider range of problems. [ABSTRACT FROM AUTHOR]

We study a new parts-procurement planning problem that is motivated by a global auto manufacturer (GAM) that practices mass customization. Because of the astronomically large number of producible configurations, forecasting their demand is impossible. Instead, firms forecast demand for options that constitute a vehicle. Requirements for many parts (up to 60%) are based on the combinations of options in a fully configured vehicle. The options' forecast, however, does not map into a unique configuration-level forecast. As a result, the options' forecast translates into ranges for many parts' requirements. The combined ranges of a set of parts are not always equal to the sum of the component ranges; they may be less. Determining parts ranges is a large-scale NP-hard problem. Large ranges and inaccurate calculation of these ranges can result in excess inventories, shortages in inventories, and suboptimal flexibility levels. We model and analyze the problem of allocating parts to suppliers and accurately computing the ranges to minimize procurement costs arising because of ranges. The range costs are assumed to be convex increasing. We perform extensive numerical analysis using a large set of randomly generated instances as well as eight industrial instances received from GAM to establish the quality of our approximation framework. Our proposed approach significantly reduces the error in range estimates relative to current industry practice. In addition, the proposed approach for allocations of parts to suppliers reduces joint-parts ranges by an average of 29.87% relative to that of current practice. This paper was accepted by Jeannette Song, operations management. [ABSTRACT FROM AUTHOR]

In this paper, we consider a broad class of nonsmooth and nonconvex fractional programs, which encompass many important modern optimization problems arising from diverse areas such as the recently proposed scale-invariant sparse signal reconstruction problem in signal processing. We propose a proximal subgradient algorithm with extrapolations for solving this optimization model and show that the iterated sequence generated by the algorithm is bounded and that any one of its limit points is a stationary point of the model problem. The choice of our extrapolation parameter is flexible and includes the popular extrapolation parameter adopted in the restarted fast iterative shrinking-threshold algorithm (FISTA). By providing a unified analysis framework of descent methods, we establish the convergence of the full sequence under the assumption that a suitable merit function satisfies the Kurdyka–Łojasiewicz property. Our algorithm exhibits linear convergence for the scale-invariant sparse signal reconstruction problem and the Rayleigh quotient problem over spherical constraint. When the denominator is the maximum of finitely many continuously differentiable weakly convex functions, we also propose another extrapolated proximal subgradient algorithm with guaranteed convergence to a stronger notion of stationary points of the model problem. Finally, we illustrate the proposed methods by both analytical and simulated numerical examples. [ABSTRACT FROM AUTHOR]

The minimum sum-of-squares clustering problem (MSSC) consists of partitioning n observations into k clusters in order to minimize the sum of squared distances from the points to the centroid of their cluster. In this paper, we propose an exact algorithm for the MSSC problem based on the branch-and-bound technique. The lower bound is computed by using a cutting-plane procedure in which valid inequalities are iteratively added to the Peng–Wei semidefinite programming (SDP) relaxation. The upper bound is computed with the constrained version of k-means in which the initial centroids are extracted from the solution of the SDP relaxation. In the branch-and-bound procedure, we incorporate instance-level must-link and cannot-link constraints to express knowledge about which data points should or should not be grouped together. We manage to reduce the size of the problem at each level, preserving the structure of the SDP problem itself. To the best of our knowledge, the obtained results show that the approach allows us to successfully solve, for the first time, real-world instances up to 4,000 data points. [ABSTRACT FROM AUTHOR]

We introduce and motivate several variants of the bin packing problem where bins are assigned to time slots, and minimum and maximum lags are required between some pairs of items. We suggest two integer programming formulations for the general problem: a compact one and a stronger formulation with an exponential number of variables and constraints. We propose a branch-cut-and-price approach that exploits the latter formulation. For this purpose, we devise separation algorithms based on a mathematical characterization of feasible assignments for two important special cases of the problem: when the number of possible bins available at each period is infinite and when this number is limited to one and time lags are nonnegative. Computational experiments are reported for instances inspired from a real-case application of chemical treatment planning in vineyards, as well as for literature instances for special cases of the problem. The experimental results show the efficiency of our branch-cut-and-price approach, as it outperforms the compact formulation on newly proposed instances and is able to obtain improved lower and upper bounds for literature instances. Summary of Contribution: The paper considers a new variant of the bin packing problem, which is one of the most important problems in operations research. A motivation for introducing this variant is given, as well as a real-life application. We present a novel and original exact branch-cut-and-price algorithm for the problem. We implement this algorithm, and we present the results of extensive computational experiments. The results show a very good performance of our algorithm. We give several research directions that can be followed by subsequent researchers to extend our contribution to more complex and generic problems. [ABSTRACT FROM AUTHOR]

Strategy-based equilibrium traffic assignment (SETA) problems define travel choice broadly as a strategy rather than a simple path. Travelers navigating through a network based on a strategy end up following a hyperpath. SETA is well suited to represent a rich set of travel choices that take place en route at nodes, such as transit passengers' transfer decisions, truckers' bidding decisions, and taxi drivers' reposition decisions. This paper recognizes and highlights the commonalities among classical and emerging SETA problems and proposes to unify them within the same modeling framework, built on the concept of a hypergraph. A generic hyperbush algorithm (HBA) is developed by decomposing a hypergraph into destination-based hyperbushes. By constructing hyperbushes and limiting traffic assignments to them, HBA promises to obtain more precise solutions to larger instances of SETA problems at a lower computational cost, both in terms of CPU time and memory consumption. To demonstrate its generality and efficiency, we tailor HBA to solve two SETA problems. The results confirm that HBA consistently outperforms the benchmark algorithms in the literature, including two state-of-the-art hyperpath-based algorithms. To obtain high-quality equilibrium solutions for SETA instances of practical size, HBA runs up to five times faster than the best competitor with a fraction of its memory consumption. [ABSTRACT FROM AUTHOR]

Recent developments in artificial intelligence (AI) have increased interest in combining AI with human intelligence to develop superior systems that augment human and artificial intelligence. In this paper, augmented intelligence informally means computers and humans working together, by design, to enhance one another, such that the intelligence of the resulting system improves. Intelligence augmentation (IA) can pool the joint intelligence of humans and computers to transform individual work, organizations, and society. Notably, applications of IA are beginning to emerge in several domains, such as cybersecurity, privacy, counterterrorism, and healthcare, among others. We provide a brief summary of papers in this special section that represent early attempts to address some of the rapidly emerging research issues. We also present a framework to guide research on IA and advocate for the important implications of IA for the future of work, organizations, and society. We conclude by outlining promising research directions based on this framework for the information systems and related disciplines. [ABSTRACT FROM AUTHOR]

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

In this paper, we study the quadratic assignment problem with a rank-one cost matrix (QAP-R1). Four integer-programming formulations are introduced of which three are assumed to have partial integer data. Unlike the standard quadratic assignment problem, some of our formulations can solve reasonably large instances of QAP-R1 with impressive running times and are faster than some metaheuristics. Pairwise relative strength of the LP relaxations of these formulations are also analyzed from theoretical and experimental points of view. Finally, we present a new metaheuristic algorithm to solve QAP-R1 along with its computational analysis. Our study offers the first systematic experimental analysis of integer-programming models and heuristics for QAP-R1. The benchmark instances with various characteristics generated for our study are made available to the public for future research work. Some new polynomially solvable special cases are also introduced. Summary of Contribution: This paper aims to advance our knowledge and ability in solving an important special case of the quadratic assignment problem. It shows how to exploit inherent properties of an optimization problem to achieve computational advantages, a strategy that was followed by researchers in model building and algorithm developments for decades. Our computational results attest to this time-tested general philosophy. The paper presents the first systematic computational study of the rank one quadratic assignment problem, along with new mathematical programming models and complexity analysis. We believe the theoretical and computational results of this paper will inspire further research on the topic and will be of significant value to practitioners using rank one quadratic assignment models. [ABSTRACT FROM AUTHOR]

This paper presents an exact algorithm for the team formation problem, in which the aim is, given a project and its required skills, to construct a capable team that can communicate and collaborate effectively. This combinatorial optimization problem is modeled as a quadratic set covering problem. The study provides a novel branch-and-bound algorithm where a reformulation of the problem is relaxed so that it decomposes into a series of linear set covering problems, and the relaxed constraints are imposed through branching. The algorithm is able to solve instances that are intractable for commercial solvers. The study illustrates an efficient usage of algorithmic methods and modeling techniques for an operations research problem. It contributes to the field of computational optimization by proposing a new application and a new algorithm to solve a quadratic version of a classical combinatorial optimization problem. The team formation problem (TFP) aims to construct a capable team that can communicate and collaborate effectively. The cost of communication is quantified using the proximity of the potential members in a social network. We study a TFP with two measures for communication effectiveness; namely, we minimize the sum of communication costs, and we impose an upper bound on the largest communication cost. This problem can be formulated as a constrained quadratic set covering problem. Our experiments show that a general-purpose solver is capable of solving small and medium-sized instances to optimality. We propose a branch-and-bound algorithm to solve larger sizes: we reformulate the problem and relax it in such a way that it decomposes into a series of linear set covering problems, and we impose the relaxed constraints through branching. Our computational experiments show that the algorithm is capable of solving large-size instances, which are intractable for the solver. Summary of Contribution: This paper presents an exact algorithm for the Team Formation Problem (TFP), in which the aim is, given a project and its required skills, to construct a capable team that can communicate and collaborate effectively. This combinatorial optimization problem is modeled as a quadratic set covering problem. The study provides a novel branch-and-bound algorithm where a reformulation of the problem is relaxed so that it decomposes into a series of linear set covering problems and the relaxed constraints are imposed through branching. The algorithm is able to solve instances that are intractable for commercial solvers. The study illustrates an efficient usage of algorithmic methods and modelling techniques for an operations research problem. It contributes to the field of computational optimization by proposing a new application as well as a new algorithm to solve a quadratic version of a classical combinatorial optimization problem. [ABSTRACT FROM AUTHOR]

Waiting at the right location at the right time can be critically important in certain variants of time-dependent shortest path problems. We investigate the computational complexity of time-dependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the nodes. We show that some cases are nondeterministic polynomial-time hard, and others can be solved in polynomial time, depending on the choice of the subset of nodes, on whether waiting is penalized or constrained, and on the magnitude of the penalty/waiting limit parameter. Summary of Contributions: This paper addresses simple yet relevant extensions of a fundamental problem in Operations Research: the Shortest Path Problem (SPP). It considers time-dependent variants of SPP, which can account for changing traffic and/or weather conditions. The first variant that is tackled allows for waiting at certain nodes but at a cost. The second variant instead places a limit on the total waiting. Both variants have applications in transportation, e.g., when it is possible to wait at certain locations if the benefits outweigh the costs. The paper investigates these problems using complexity analysis and algorithm design, both tools from the field of computing. Different cases are considered depending on which of the nodes contribute to the waiting cost or waiting limit (all nodes, all nodes except the origin, a subset of nodes...). The computational complexity of all cases is determined, providing complexity proofs for the variants that are NP-Hard and polynomial time algorithms for the variants that are in P. [ABSTRACT FROM AUTHOR]

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

Inference-based optimization via simulation, which substitutes Gaussian process (GP) learning for the structural properties exploited in mathematical programming, is a powerful paradigm that has been shown to be remarkably effective in problems of modest feasible-region size and decision-variable dimension. The limitation to "modest" problems is a result of the computational overhead and numerical challenges encountered in computing the GP conditional (posterior) distribution on each iteration. In this paper, we substantially expand the size of discrete-decision-variable optimization-via-simulation problems that can be attacked in this way by exploiting a particular GP—discrete Gaussian Markov random fields—and carefully tailored computational methods. The result is the rapid Gaussian Markov Improvement Algorithm (rGMIA), an algorithm that delivers both a global convergence guarantee and finite-sample optimality-gap inference for significantly larger problems. Between infrequent evaluations of the global conditional distribution, rGMIA applies the full power of GP learning to rapidly search smaller sets of promising feasible solutions that need not be spatially close. We carefully document the computational savings via complexity analysis and an extensive empirical study. Summary of Contribution: The broad topic of the paper is optimization via simulation, which means optimizing some performance measure of a system that may only be estimated by executing a stochastic, discrete-event simulation. Stochastic simulation is a core topic and method of operations research. The focus of this paper is on significantly speeding-up the computations underlying an existing method that is based on Gaussian process learning, where the underlying Gaussian process is a discrete Gaussian Markov Random Field. This speed-up is accomplished by employing smart computational linear algebra, state-of-the-art algorithms, and a careful divide-and-conquer evaluation strategy. Problems of significantly greater size than any other existing algorithm with similar guarantees can solve are solved as illustrations. [ABSTRACT FROM AUTHOR]

Inverse optimization—determining parameters of an optimization problem that render a given solution optimal—has received increasing attention in recent years. Although significant inverse optimization literature exists for convex optimization problems, there have been few advances for discrete problems, despite the ubiquity of applications that fundamentally rely on discrete decision making. In this paper, we present a new set of theoretical insights and algorithms for the general class of inverse mixed integer linear optimization problems. Specifically, a general characterization of optimality conditions is established and leveraged to design new cutting plane solution algorithms. Through an extensive set of computational experiments, we show that our methods provide substantial improvements over existing methods in solving the largest and most difficult instances to date. [ABSTRACT FROM AUTHOR]

We introduce a new optimization model, dubbed the display optimization problem, that captures a common aspect of choice behavior, known as the framing bias. In this setting, the objective is to optimize how distinct items (corresponding to products, web links, ads, etc.) are being displayed to a heterogeneous audience, whose choice preferences are influenced by the relative locations of items. Once items are assigned to vertically differentiated locations, customers consider a subset of the items displayed in the most favorable locations before picking an alternative through multinomial logit choice probabilities. The main contribution of this paper is to derive a polynomial-time approximation scheme for the display optimization problem. Our algorithm is based on an approximate dynamic programming formulation that exploits various structural properties to derive a compact state space representation of provably near-optimal item-to-position assignment decisions. As a byproduct, our results improve on existing constant-factor approximations for closely related models and apply to general distributions over consideration sets. We develop the notion of approximate assortments that may be of independent interest and applicable in additional revenue management settings. Lastly, we conduct extensive numerical studies to validate the proposed modeling approach and algorithm. Experiments on a public hotel booking data set demonstrate the superior predictive accuracy of our choice model vis-à-vis the multinomial logit choice model with location bias, proposed in earlier literature. In synthetic computational experiments, our approximation scheme dominates various benchmarks, including natural heuristics—greedy methods, local search, priority rules—and state-of-the-art algorithms developed for closely related models. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

In 1964, Kenneth Lane proposed an algorithm to optimize the production schedule of a single-metal, single-processor open pit mine. For this, he proposed a policy based on varying, over time, the so-called "cutoff grade"—or grade threshold used to determine if extracted material should be ore (processed material) or waste (thrown away). Lane's algorithm had a profound impact on the mining industry. However, though it has been used in multiple commercial software systems and has traditionally been taught to every aspiring mining engineer, it is widely considered a heuristic, and little is known regarding the quality of the solutions it produces. In this paper, we formally study Lane's problem. We show that Lane's algorithm can be viewed as an approximate dynamic programming scheme and that Lane's optimality conditions can be formally derived in two different ways: by considering a variant of the problem where the future value function is linearly approximated or by deriving the optimality conditions of a continuous-time version of the problem. We further show that Lane's algorithm can naturally be extended to this continuous-time version of the problem and that when this algorithm converges, it converges to an optimal solution. Finally, through a reformulation, we show that Lane's original problem can be solved using convex mixed-integer programming. Though hypothetical counterexamples can be constructed, computational experiments prove that Lane's algorithm can produce the optimal solution in every real-world data set tested, thereby lending solid support for its practical application. This paper was accepted by Chung Piaw Teo, optimization. [ABSTRACT FROM AUTHOR]

A lower bound for a finite-scenario-based chance-constrained program is the quantile value corresponding to the sorted optimal objective values of scenario subproblems. This quantile bound can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. The quality of the bound depends on how the scenarios are grouped. In this paper, we formulate a mixed-integer bilevel program that optimally groups scenarios to tighten the quantile bounds. For general chance-constrained programs, we propose a branch-and-cut algorithm to optimize the bilevel program, and for chance-constrained linear programs, a mixed-integer linear-programming reformulation is derived. We also propose several heuristics for grouping similar or dissimilar scenarios. Our computational results demonstrate that optimal grouping bounds are much tighter than heuristic bounds, resulting in smaller root-node gaps and better performance of scenario decomposition for solving chance-constrained 0-1 programs. Also, the optimal grouping bounds can be greatly strengthened using larger group size. Summary of Contribution: Chance-constrained programs are in general NP-hard but widely used in practice for lowering the risk of undesirable outcomes during decision making under uncertainty. Assuming finite scenarios of uncertain parameter, chance-constrained programs can be reformulated as mixed-integer linear programs with binary variables representing whether or not the constraints are satisfied in corresponding scenarios. A useful quantile bound for solving chance-constrained programs can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. In this paper, we develop algorithms for optimally and heuristically grouping scenarios to tighten the quantile bounds. We aim to improve both the computation and solution quality of a variety of chance-constrained programs formulated for different Operations Research problems. [ABSTRACT FROM AUTHOR]

This paper integrates, from a tactical perspective, berth allocation and quay-crane assignment, two important, closely related decisions in container terminal operations in a single model. To obtain optimal solutions, a branch-and-price algorithm is sought in this paper under the framework of Dantzig–Wolfe decomposition. The algorithm decomposes the original problem to a master problem that links all vessels competing for the shared resources of berths and quay cranes and multiple per-vessel pricing subproblems that can be solved efficiently in polynomial time. Specifically, in the stage of generating promising initial feasible columns, three heuristics are adopted; during the column-updating stage, the subgradient-based Lagrangian relaxation is introduced to tackle the possibly encountered degeneracy phenomenon; the branching strategy is implemented in the pricing subproblem rather than in the master problem as reported in the literature with the benefit of avoiding incurring new dual prices, simplifying the branching process; and both breadth- and depth-first searching policies are tested to select the next node to explore. With real-life data, extensive numerical experiments are conducted to select the best choice for each stage with the strengths and drawbacks of each choice provided. And then the superiority of the branch-and-price algorithm configured with the selected combination of strategies is verified by comparing it with both CPLEX, a general-purpose solver, and a set-partitioning model, a dedicated algorithm reported in the literature. In addition, the decomposition by vessels adopted in this paper is also verified numerically by comparing it with the decomposition by berths reported in the literature, and the performance of the algorithm for other problem settings has also been tested. In conclusion, the numerical experiments show that our method outperforms the commercial solver and state-of-the-art solution methods reported in the literature in terms of both solution quality and computational time. [ABSTRACT FROM AUTHOR]

This paper studies the two-echelon capacitated vehicle routing problem with time windows. The first echelon consists of transferring freight from depots to intermediate facilities (i.e., satellites), whereas the second echelon consists of transferring freight from these facilities to the final customers, within their time windows. We propose two path-based mathematical formulations for our problem: (1) in one formulation, paths are defined over both first- and second-echelon tours, and (2) in the other one, the first- and second-echelon paths are decomposed. Branch-and-price–based algorithms are developed for both formulations. We compare both formulations and solution methods on a comprehensive set of instances and are able to solve instances up to five satellites and 100 customers to optimality. This paper is the first paper in the literature that solves such large instance sizes. The online appendix is available at https://doi.org/10.1287/trsc.2018.0844. [ABSTRACT FROM AUTHOR]

This paper reviews the literature on vehicle routing problems and location routing problems with intermediate stops. We classify publications into different categories from both an application-based perspective and a methodological perspective. In addition, we analyze the papers with respect to the algorithms and benchmark instances they present. Furthermore, we provide an overview of trends in the literature and identify promising areas for further research. [ABSTRACT FROM AUTHOR]

Games with multiplicative payoffs Trade is win-win: The buyer gets a product that the seller can provide more easily. Selling more and buying more benefits both. This mutual benefit can sometimes be represented multiplicatively. But the buyer also pays a price to the seller. This money transfer is win-lose, a zero-sum game. The sum of the two payoff matrices is a matrix of rank one. In "Fast Algorithms for Rank-1 Bimatrix Games," Bharat Adsul, Jugal Garg, Ruta Mehta, Milind Sohoni, and Bernhard von Stengel show new algorithms that analyze such rank-1 games. The computation time for finding one Nash equilibrium is polynomial. Finding all Nash equilibria takes time comparable to finding a single equilibrium of a general bimatrix game. This puts games in computational reach that are economically much more interesting than zero-sum games (which are of rank zero), whereas solving general games is computationally hard. The paper's detailed structural analysis of games based on their rank enhances our understanding of this computational complexity. The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one and shows the following: (1) For a game of rank r, the set of its Nash equilibria is the intersection of a generically one-dimensional set of equilibria of parameterized games of rank r − 1 with a hyperplane. (2) One equilibrium of a rank-1 game can be found in polynomial time. (3) All equilibria of a rank-1 game can be found by following a piecewise linear path. In contrast, such a path-following method finds only one equilibrium of a bimatrix game. (4) The number of equilibria of a rank-1 game may be exponential. (5) There is a homeomorphism between the space of bimatrix games and their equilibrium correspondence that preserves rank. It is a variation of the homeomorphism used for the concept of strategic stability of an equilibrium component. [ABSTRACT FROM AUTHOR]

Apiculture has gained worldwide interest because of its contributions to economic incomes and environmental conservation. In view of these, migratory beekeeping, as a high-yielding technique, is extensively adopted. However, because of the lack of an overall routing plan, beekeepers who follow the experiential migratory routes frequently encounter unexpected detours and suffer losses when faced with problems such as those related to nectar source capacities and the production of bee products. The migratory beekeeping routing problem (MBRP) is proposed based on the practical background of the commercial apiculture industry to optimize the global revenue for beekeepers by comprehensively considering nectar source allocation, migration, production and sales of bee products, and corresponding time decisions. The MBRP is a new variant of the vehicle routing problem but with significantly different production time decisions at the vertices (i.e., nectar sources). That is, only the overlaps between residence durations and flowering periods generate production benefits. Different sales visits cause different gains from the same products; in turn, these lead to different production time decisions at previously visited nectar source locations and even change the visits for production. To overcome the difficulty resulting from the complicated time decisions, we utilize the Dantzig–Wolfe decomposition method and propose a revised labeling algorithm for the pricing subproblems. The tests, performed on instances and a real-world case, demonstrate that the column generation method with the revised labeling algorithm is efficient for solving the MBRP. Compared with traditional routes, a more efficient overall routing schedule for migratory beekeepers is proposed. Summary of Contribution. Based on the practical background of commercial apiculture industry, this paper proposes a new type of routing problem named the migratory beekeeping routing problem (MBRP), which incorporates the selection of productive nodes and sales nodes as well as the production time decision at the productive nodes on a migratory beekeeping network. To overcome the difficulty resulting from the complicated time decisions, we utilize the Dantzig–Wolfe decomposition method and propose a revised labeling algorithm for the pricing subproblems. The tests, performed on instances and a real-world case, demonstrate that the column generation method with the revised labeling algorithm is efficient for solving the MBRP. Compared with traditional routes, a more efficient overall routing schedule for migratory beekeepers is proposed. Therefore, this paper is congruent with, and contributes to, the scope and mission of INFORMS Journal on Computing, especially the area of Network Optimization: Algorithms & Applications. [ABSTRACT FROM AUTHOR]

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

In this paper, we propose an exact branch-price-and-cut (BPC) algorithm for the two-echelon vehicle routing problem with time windows. This problem arises in city logistics when high-capacity and low-capacity vehicles are used to transport items from depots to satellites (first echelon) and from satellites to customers (second echelon), respectively. The aim is to determine a set of least-cost first- and second-echelon routes such that the load on the routes respect the capacity of the vehicles, each second-echelon route is supplied by exactly one first-echelon route, and each customer is visited by exactly one second-echelon route within its time window. We model the problem with a route-based formulation where first-echelon routes are enumerated a priori, and second-echelon routes are generated using column generation. The problem is solved using BPC. To generate second-echelon routes, one pricing problem per satellite is solved using a labeling algorithm which keeps track of the first-echelon route associated with each (partial) second-echelon route considered. Furthermore, to speed up the solution process, we introduce effective deep dual-optimal inequalities and apply known valid inequalities. We perform extensive computational experiments on benchmark instances and show that our method outperforms a state-of-the-art algorithm. We also conduct sensitivity analyses on the different components of our algorithm and derive managerial insights related to the structure of the first-echelon routes. [ABSTRACT FROM AUTHOR]

Existing literature examines control and resistance in the context of service organizations that rely on both managers and customers to control workers during the execution of work. Digital platform companies, however, eschew managers in favor of algorithmically mediated customer control—that is, customers rate workers, and algorithms tally and track these ratings to control workers' future platform-based opportunities. How has this shift in the distribution of control among platforms, customers, and workers affected the relationship between control and resistance? Drawing on workers' experiences from a comparative ethnography of two of the largest platform companies, we find that platform use of algorithmically mediated customer control has expanded the service encounter such that organizational control and workers' resistance extend well beyond the execution of work. We find that workers have the most latitude to deploy resistance early in the labor process but must adjust their resistance tactics because their ability to resist decreases in each subsequent stage of the labor process. Our paper, thus, develops understanding of resistance by examining the relationship between control and resistance before, during, and after a task, providing insight into how control and resistance function in the gig economy. We also demonstrate the limitations of platforms' reliance on algorithmically mediated customer control by illuminating how workers' everyday interactions with customers can influence and manipulate algorithms in ways that platforms cannot always observe. [ABSTRACT FROM AUTHOR]

Stochastic inventory systems with lead times are often challenging to optimize, including single-sourcing lost-sales and dual-sourcing systems. Recent numerical results suggest that capped policies demonstrate superior performance over existing heuristics. However, the superior performance lacks a theoretical foundation. In "1.79-Approximation Algorithms for Continuous Review Single-Sourcing Lost-Sales and Dual-Sourcing Inventory Models," the author provides a theoretical foundation for this phenomenon in two classical inventory models. First, in a continuous review lost-sales model with lead times and Poisson demand, he proves that a capped base-stock policy has a worst-case performance guarantee of 1.79 by conducting an asymptotic analysis under a large penalty cost and lead time. Second, in a more complex continuous review dual-sourcing model with general lead times and Poisson demand, he proves that a similar capped dual-index policy has a worst-case performance guarantee of 1.79 under large lead time and ordering cost differences. The results provide a deeper understanding of the superior numerical performance of capped policies and present a new approach to proving worst-case performance guarantees of simple policies in hard inventory problems. Stochastic inventory systems with lead times are often challenging to optimize, including single-sourcing lost-sales and dual-sourcing inventory systems. Recent numerical results suggest that capped policies demonstrate superior performance over existing heuristics. However, the superior performance lacks a theoretical foundation, and why such policies generally perform so well remains a major open question. In this paper, we provide a theoretical foundation for this phenomenon in two classical inventory models with lead times. First, in a continuous-review lost-sales inventory model with lead times and Poisson demand, we prove that a so-called capped base-stock policy has a worst-case performance guarantee of 1.79 by conducting an asymptotic analysis under a large penalty cost and lead time. Second, we extend the analysis to a more complex continuous-review dual-sourcing inventory model with general lead times and Poisson demand and also prove that a so-called capped dual-index policy has a worst-case performance guarantee of 1.79 under large lead time and ordering cost differences. Our results provide a deeper understanding of the superior numerical performance of capped policies and present a new approach to proving worst-case performance guarantees of simple policies in hard inventory problems. [ABSTRACT FROM AUTHOR]

Parking pressure has been steadily increasing in cities as well as on university and corporate campuses. To relieve this pressure, this paper studies a carpooling platform that would match riders and drivers while guaranteeing a ride back and exploiting spatial and temporal locality. In particular, the paper formalizes the commute trip-sharing problem (CTSP) to find a routing plan that maximizes ride sharing for a set of commute trips. The CTSP is a generalization of the vehicle routing problem with routes that satisfy time-window, capacity, pairing, precedence, ride-duration, and driver constraints. The paper introduces two exact algorithms for the CTSP: a route-enumeration algorithm and a branch-and-price algorithm. Experimental results show that on a high-fidelity real-world data set of commute trips from a midsize city, both algorithms optimally solve small and medium-sized problems and produce high-quality solutions for larger problem instances. The results show that carpooling, if widely adopted, has the potential to reduce vehicle usage by up to 57% and decrease vehicle miles traveled by up to 46% while incurring only a 22% increase in average ride time per commuter for the trips considered. [ABSTRACT FROM AUTHOR]

Experimental design is a classical statistics problem, and its aim is to estimate an unknown vector from linear measurements where a Gaussian noise is introduced in each measurement. For the combinatorial experimental design problem, the goal is to pick a subset of experiments so as to make the most accurate estimate of the unknown parameters. In this paper, we will study one of the most robust measures of error estimation—the D-optimality criterion, which corresponds to minimizing the volume of the confidence ellipsoid for the estimation error. The problem gives rise to two natural variants depending on whether repetitions of experiments are allowed or not. We first propose an approximation algorithm with a 1/e-approximation for the D-optimal design problem with and without repetitions, giving the first constant-factor approximation for the problem. We then analyze another sampling approximation algorithm and prove that it is asymptotically optimal. Finally, for D-optimal design with repetitions, we study a different algorithm proposed by the literature and show that it can improve this asymptotic approximation ratio. All the sampling algorithms studied in this paper are shown to admit polynomial-time deterministic implementations. [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]

Jose L. Walteros and Austin Buchanan This paper focuses on providing a rigorous, worst-case explanation for why the maximum clique problem is apparently so easy in naturally occurring graphs, despite its intractability in the worst case. To this day, there exist unsolved benchmark instances with just 1,000 vertices. In contrast, real-life instances appear to be much easier. Indeed, relatively simple algorithms can solve instances with millions of vertices in just a few seconds. However, these algorithms lack any worst-case guarantees on their running time. Exactly why these real-life instances are so easy has been somewhat of a puzzle. This paper shows that maximum clique can be solved in time polynomial in the size of the graph, but exponential in a graph invariant that we denote by. Typically, is very small for real-life graphs, being 0, 1 or 2 in over half of the instances coming from commonly used testbeds. In these and other cases where can be thought of as a small constant, our algorithm runs in time. To this day, the maximum clique problem remains a computationally challenging problem. Indeed, despite researchers' best efforts, there exist unsolved benchmark instances with 1,000 vertices. However, relatively simple algorithms solve real-life instances with millions of vertices in a few seconds. Why is this the case? Why is the problem apparently so easy in many naturally occurring networks? In this paper, we provide an explanation. First, we observe that the graph's clique number ω is very near to the graph's degeneracy d in most real-life instances. This observation motivates a main contribution of this paper, which is an algorithm for the maximum clique problem that runs in time polynomial in the size of the graph, but exponential in the gap g ≔ (d + 1) − ω between the clique number ω and its degeneracy-based upper bound d+1. When this gap g can be treated as a constant, as is often the case for real-life graphs, the proposed algorithm runs in time O (d m) = O (m 1.5 ) . This provides a rigorous explanation for the apparent easiness of these instances despite the intractability of the problem in the worst case. Further, our implementation of the proposed algorithm is actually practical—competitive with the best approaches from the literature. [ABSTRACT FROM AUTHOR]

In the paper, "Optimistic Monte Carlo Tree Search with Sampled Information Relaxation Dual Bounds," the authors propose an extension to Monte Carlo tree search that uses the idea of "sampling the future" to produce noisy upper bounds on nodes in the decision tree. These upper bounds can help guide the tree expansion process and produce decision trees that are deeper rather than wider, in effect concentrating computation toward more useful parts of the state space. The algorithm's effectiveness is illustrated in a ride-sharing setting, where a driver/vehicle needs to make dynamic decisions regarding trip acceptance and relocations. Monte Carlo tree search (MCTS), most famously used in game-play artificial intelligence (e.g., the game of Go), is a well-known strategy for constructing approximate solutions to sequential decision problems. Its primary innovation is the use of a heuristic, known as a default policy, to obtain Monte Carlo estimates of downstream values for states in a decision tree. This information is used to iteratively expand the tree toward regions of states and actions that an optimal policy might visit. However, to guarantee convergence to the optimal action, MCTS requires the entire tree to be expanded asymptotically. In this paper, we propose a new "optimistic" tree search technique called primal-dual MCTS that uses sampled information relaxation upper bounds on potential actions to make tree expansion decisions, creating the possibility of ignoring parts of the tree that stem from highly suboptimal choices. The core contribution of this paper is to prove that despite converging to a partial decision tree in the limit, the recommended action from primal-dual MCTS is optimal. The new approach shows promise when used to optimize the behavior of a single driver navigating a graph while operating on a ride-sharing platform. Numerical experiments on a real data set of taxi trips in New Jersey suggest that primal-dual MCTS improves on standard MCTS (upper confidence trees) and other policies while exhibiting a reduced sensitivity to the size of the action space. [ABSTRACT FROM AUTHOR]

This paper considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. Just as the multiarmed bandit problem crystallizes the tradeoff between exploration and exploitation, this "pure exploration" variant crystallizes the challenge of rapidly gathering information before committing to a final decision. The paper proposes several simple Bayesian algorithms for allocating measurement effort and, by characterizing fundamental asymptotic limits on the performance of any algorithm, formalizes a sense in which these seemingly naive algorithms are the best possible. This paper considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. This paper proposes three simple and intuitive Bayesian algorithms for adaptively allocating measurement effort and formalizes a sense in which these seemingly naive rules are the best possible. One proposal is top-two probability sampling, which computes the two designs with the highest posterior probability of being optimal and then randomizes to select among these two. One is a variant of top-two sampling that considers not only the probability that a design is optimal, but the expected amount by which its quality exceeds that of other designs. The final algorithm is a modified version of Thompson sampling that is tailored for identifying the best design. We prove that these simple algorithms satisfy a sharp optimality property. In a frequentist setting where the true quality of the designs is fixed, one hopes that the posterior definitively identifies the optimal design, in the sense that that the posterior probability assigned to the event that some other design is optimal converges to zero as measurements are collected. We show that under the proposed algorithms, this convergence occurs at an exponential rate, and the corresponding exponent is the best possible among all allocation rules. It should be highlighted that the proposed algorithms depend on a single tuning parameter, which determines the probability used when randomizing among the top-two designs. Attaining the optimal rate of posterior convergence requires either that this parameter is set optimally or is tuned adaptively toward the optimal value. The paper goes further, characterizing the exponent attained on any problem instance and for any value of the tunable parameter. This exponent is interpreted as being optimal among a constrained class of allocation rules. Finally, considerable robustness to this parameter is established through numerical experiments and theoretical results. When this parameter is set to 1/2, the exponent attained is within a factor of 2 of best possible across all problem instances. [ABSTRACT FROM AUTHOR]

Distributed generation and remotely controlled switches have emerged as important technologies to improve the resiliency of distribution grids against extreme weather-related disturbances. Therefore it becomes important to study how best to place them on the grid in order to meet a resiliency criteria, while minimizing costs and capturing their dependencies on the associated communication systems that sustain their distributed operations. This paper introduces the Optimal Resilient Design Problem for Distribution and Communication Systems (ORDPDC) to address this need. The ORDPDC is formulated as a two-stage stochastic mixed-integer program that captures the physical laws of distribution systems, the communication connectivity of the smart grid components, and a set of scenarios that specifies which components are affected by potential disasters. The paper proposes an exact branch-and-price algorithm for the ORDPDC that features a strong lower bound and a variety of acceleration schemes to address degeneracy. The ORDPDC model and branch-and-price algorithm were evaluated on a variety of test cases with varying disaster intensities and network topologies. The results demonstrate the significant impact of the network topologies on the expansion plans and costs, as well as the computational benefits of the proposed approach. [ABSTRACT FROM AUTHOR]

We develop a model of many-to-one matching markets in which agents with multiunit demand aim to maximize a cardinal linear objective subject to multidimensional knapsack constraints. The choice functions of agents with multiunit demand are therefore not substitutable. As a result, pairwise stable matchings may not exist and even when they do, may be highly inefficient. We provide an algorithm that finds a group-stable matching that approximately satisfies all the multidimensional knapsack constraints. The novel ingredient in our algorithm is a combination of matching with contracts and Scarf's Lemma. We show that the degree of the constraint violation under our algorithm is proportional to the sparsity of the constraint matrix. The algorithm, therefore, provides practical constraint violation bounds for applications in contexts, such as refugee resettlement, day care allocation, and college admissions with diversity requirements. Simulations using refugee resettlement data show that our approach produces outcomes that are not only more stable, but also more efficient than the outcomes of the Deferred Acceptance algorithm. Moreover, simulations suggest that in practice, constraint violations under our algorithm would be even smaller than the theoretical bounds. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. [ABSTRACT FROM AUTHOR]

Online reputation has become a key marketing-mix variable in the digital economy. Our study helps managers decide on the effort they should use to manage online reputation. We consider an online reputation race in which it is important not just to manage the absolute reputation, but also the relative rating. That is, to stay ahead, a firm should try to have ratings that are better than those of its competitors. Our findings are particularly significant for platform owners (such as Expedia or Yelp) to strategically grow their base of participating firms: growing the middle of the market (firms with average ratings) is the best option considering the goals of the platform and the other stakeholders, namely incumbents and consumers. For firms, we find that they should increase their effort when the mean market rating increases. Another key insight for firms is that, sometimes, adversity can come disguised as an opportunity. When an adverse event strikes the industry (such as a reduction in sales margin or an increase in the cost of effort), a firm's profit can increase if it can manage this event better than its competitors. Online reputation (as reflected in customer ratings) has become a key marketing-mix variable in the digital economy. This paper models how firms compete by managing their online reputations. We consider a market consisting of competing firms that participate in a platform such as Expedia or Yelp. Each firm exerts effort to improve its rating but, in doing so, also influences the mean market rating. The sales of a firm are influenced by its own rating and the mean rating of the firms in the market. We formulate each firm's decision as a stochastic control problem in which the objective is to maximize the discounted profit over a planning horizon. These control problems are connected through a common market belief that represents the mean rating of the firms in the market. The joint actions of the firms generate a mean market rating in equilibrium. We prove that such an equilibrium exists and is unique, and we use a simple algorithm to compute its value. An equilibrium analysis of the mean market rating reveals several insights. A more heterogeneous market (one in which the parameters of the firms are very different) leads to a lower mean market rating and higher total profit of the firms in the market. Our results can inform platforms to target certain firms to join: growing the middle of the market (firms with average ratings) is the best option considering the goals of the platform (increase the total profit of the firms) and other stakeholders, namely the incumbents and the consumers. For firms, we find that a firm's profit can increase from an adverse event (such as a reduction in sales margin or an increase in the cost of control) depending on how other firms in the market are affected by the event. Our findings are particularly significant for platform owners to employ a strategic growth model for the platform. [ABSTRACT FROM AUTHOR]

The crew-pairing problem (CPP) is solved in the first step of the crew-scheduling process. It consists of creating a set of pairings (sequence of flights, connections, and rests forming one or multiple days of work for an anonymous crew member) that covers a given set of flights at minimum cost. Those pairings are assigned to crew members in a subsequent crew-rostering step. In this paper, we propose a new integral column-generation algorithm for the CPP, called improved integral column generation with prediction ( I 2 C G p ), which leaps from one integer solution to another until a near-optimal solution is found. Our algorithm improves on previous integral column-generation algorithms by introducing a set of reduced subproblems. Those subproblems only contain flight connections that have a high probability of being selected in a near-optimal solution and are, therefore, solved faster. We predict flight-connection probabilities using a deep neural network trained in a supervised framework. We test I 2 C G p on several real-life instances and show that it outperforms a state-of-the-art integral column-generation algorithm as well as a branch-and-price heuristic commonly used in commercial airline planning software, in terms of both solution costs and computing times. We highlight the contributions of the neural network to I 2 C G p . [ABSTRACT FROM AUTHOR]

A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width 1 because they are just additive, but it is already nontrivial even when the width is restricted to 2. We show two types of tight bounds on the polynomial-time approximability for this problem. First, in general, the approximation bound is between O(n) and Ω (n / l o g n ) , and exactly θ (n / l o g n ) if randomization is allowed, where n is the ground set size. Second, when the width of the input XOS functions is bounded by a constant k ≥ 2, the approximation bound is between k − 1 and k − 1 − ɛ for any ɛ > 0. In particular, we give a linear-time algorithm to find an exact maximizer of a given XOS function of width 2, whereas we show that any exact algorithm requires an exponential number of value oracle calls even when the width is restricted to 3. [ABSTRACT FROM AUTHOR]

Many applications in machine learning or signal processing involve nonsmooth optimization problems. This nonsmoothness brings a low-dimensional structure to the optimal solutions. In this paper, we propose a randomized proximal gradient method harnessing this underlying structure. We introduce two key components: (i) a random subspace proximal gradient algorithm; and (ii) an identification-based sampling of the subspaces. Their interplay brings a significant performance improvement on typical learning problems in terms of dimensions explored. [ABSTRACT FROM AUTHOR]

Motivated by applications in online advertising, we consider a class of maximization problems where the objective is a function of the sequence of actions and the running duration of each action. For these problems, we introduce the concepts of sequence-submodularity and sequence-monotonicity, which extend the notions of submodularity and monotonicity from functions defined over sets to functions defined over sequences. We establish that if the objective function is sequence-submodular and sequence-nondecreasing, then there exists a greedy algorithm that achieves 1 − 1 / e of the optimal solution. We apply our algorithm and analysis to two applications in online advertising: online ad allocation and query rewriting. We first show that both problems can be formulated as maximizing nondecreasing sequence-submodular functions. We then apply our framework to these two problems, leading to simple greedy approaches with guaranteed performances. In particular, for the online ad allocation problem, the performance of our algorithm is 1 − 1 / e , which matches the best known existing performance, and for the query rewriting problem, the performance of our algorithm is 1 − 1 / e 1 − 1 / e , which improves on the best known existing performance in the literature. This paper was accepted by Chung Piaw Teo, optimization. [ABSTRACT FROM AUTHOR]

We consider a single product dynamic pricing with demand learning. The candidate prices belong to a wide range of a price interval; the modeling of the demand functions is nonparametric in nature, imposing only smoothness regularity conditions. One important aspect of our model is the possibility of the expected reward function to be nonconcave and indeed multimodal, which leads to many conceptual and technical challenges. Our proposed algorithm is inspired by both the Upper-Confidence-Bound algorithm for multiarmed bandit and the Optimism-in-the-Face-of-Uncertainty principle arising from linear contextual bandits. The multiarmed bandit formulation arises from local-bin approximation of an unknown continuous demand function, and the linear contextual bandit formulation is then applied to obtain more accurate local polynomial approximators within each bin. Through rigorous regret analysis, we demonstrate that our proposed algorithm achieves optimal worst-case regret over a wide range of smooth function classes. More specifically, for k-times smooth functions and T selling periods, the regret of our proposed algorithm is O ˜ (T (K + 1) / (2 K + 1) ) , which is shown to be optimal via the development of information theoretical lower bounds. We also show that in special cases, such as strongly concave or infinitely smooth reward functions, our algorithm achieves an O (T) regret, matching optimal regret established in previous works. Finally, we present computational results that verify the effectiveness of our method in numerical simulations. This paper was accepted by J. George Shanthikumar, big data analytics. [ABSTRACT FROM AUTHOR]

We explore the benefits of multivariable branching schemes for linear-programming-based branch-and-bound algorithms for the 0-1 knapsack problem—that is, the benefits of branching on sets of variables rather than on a single variable (the current default in integer-programming solvers). We present examples where multivariable branching has advantages over single-variable branching and partially characterize situations in which this happens. Chvátal shows that for a specific class of 0-1 knapsack instances, a linear-programming-based branch-and-bound algorithm (employing a single-variable branching scheme) must explore exponentially many nodes. We show that for this class of 0-1 knapsack instances, a linear-programming-based branch-and-bound algorithm employing an appropriately chosen multivariable branching scheme explores either three or seven nodes. Finally, we investigate the performance of various multivariable branching schemes for 0-1 knapsack instances computationally and demonstrate their potential; the multivariable branching schemes explored result in smaller search trees (some in search trees that are an order of magnitude smaller), and some also result in shorter solution times. Summary of Contribution: As a powerful modeling tool, mixed-integer programming (MIP) is ubiquitous in Operations Research and is usually solved via the branch-and-bound framework. However, solving MIPs is computationally challenging in general, where branching affects the performance of solvers dramatically. In this paper, we explore the benefits of branching on multiple variables, which can be viewed as a generalization of the standard single-variable branching. We analyze its theoretical behavior on a special instance introduced by Chvátal, which is proved to be hard for single-variable branching. We also partially characterize situations in which branching on multiple variables is superior to its single-variable counterpart. Lastly, we demonstrate its potential in reducing the overall computational time and possible memory usage for storing unexplored nodes through numerical experiments on 0-1 knapsack problems. [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]

In a minimum load spanning tree (MLST) problem, we are given an undirected graph and nondecreasing load functions for nodes defined on nodes' degrees in a spanning tree, and the objective is to find a spanning tree that minimizes the maximum load among all nodes. We propose the first O ∗ (2 n) time exact algorithm for the MLST problem, where n is the number of nodes and O ∗ ignores polynomial factor. The algorithm is obtained by repeatedly querying whether a candidate objective value is feasible, where each query can be formulated as a bounded degree spanning tree problem (BDST). We propose a novel solution to BDST by extending an inclusion-exclusion based algorithm. To further enhance the time efficiency of the previous algorithm, we then propose a faster algorithm by generalizing the concept of branching walks. In addition, for the purpose of comparison, we give the first mixed integer linear programming formulation for MLST. In numerical analysis, we consider various load functions on a randomly generated network. The results verify the effectiveness of the proposed algorithms. Summary of Contribution: Minimum load spanning tree (MLST) plays an important role in various applications such as wireless sensor networks (WSNs). In many applications of WSNs, we often need to collect data from all sensors to some specified sink. In this paper, we propose the first exact algorithms for the MLST problem. Besides having theoretical guarantees, our algorithms have extraordinarily good performance in practice. We believe that our results make significant contributions to the field of graph theory, internet of things, and WSNs. [ABSTRACT FROM AUTHOR]

In the paper "Robust Dual Dynamic Programming," Angelos Georghiou, Angelos Tsoukalas, and Wolfram Wiesemann propose a novel solution scheme for addressing planning problems with long horizons. Such problems can be formulated as multistage robust optimization problems. The proposed method takes advantage of the decomposable nature of these problems by bounding the costs arising in the future stages through lower and upper cost-to-go functions. The proposed scheme does not require a relatively complete recourse, and it offers deterministic upper and lower bounds throughout the execution of the algorithm. The promising performance of the algorithm is shown in a stylized inventory-management problem in which the proposed algorithm achieved the optimal solution in problem instances with 100 time stages in a few minutes. Multistage robust optimization problems, where the decision maker can dynamically react to consecutively observed realizations of the uncertain problem parameters, pose formidable theoretical and computational challenges. As a result, the existing solution approaches for this problem class typically determine suboptimal solutions under restrictive assumptions. In this paper, we propose a robust dual dynamic programming (RDDP) scheme for multistage robust optimization problems. The RDDP scheme takes advantage of the decomposable nature of these problems by bounding the costs arising in the future stages through lower and upper cost-to-go functions. For problems with uncertain technology matrices and/or constraint right-hand sides, our RDDP scheme determines an optimal solution in finite time. Also, if the objective function and/or the recourse matrices are uncertain, our method converges asymptotically (but deterministically) to an optimal solution. Our RDDP scheme does not require a relatively complete recourse, and it offers deterministic upper and lower bounds throughout the execution of the algorithm. We show the promising performance of our algorithm in a stylized inventory management problem. Supplemental material is available at https://doi.org/10.1287/opre.2018.1835. [ABSTRACT FROM AUTHOR]

This paper addresses a travel time reliable signal control problem. Travel time distributional estimates are obtained from a stochastic microscopic traffic simulator. The estimates are embedded within a simulation-based optimization algorithm. Analytical approximations of the simulated metrics are combined with the simulated data in order to enhance the computational efficiency of the algorithm. The signal control problems are formulated based on the expectation and the standard deviation of travel time metrics. The proposed approach goes beyond the traditional use of first-order simulated information, it addresses a problem that embeds higher-order distributional information. It is used to solve a large-scale signal control problem. The approach addresses these challenging simulation-based optimization problems in a computationally efficient manner. Its performance is compared to that of a traditional simulation-based optimization approach. The proposed method systematically outperforms the traditional approach. Such an approach can be used to inform the design and operations of transportation systems by, for instance, addressing reliable and/or robust formulations of traditional transportation problems. The online appendix is available at https://doi.org/10.1287/trsc.2017.0812. [ABSTRACT FROM AUTHOR]

Managing perishable inventory systems with positive lead times and finite ordering capacities is important but notoriously difficult in both theory and computation. The optimal control policy is extremely complicated, and no effective heuristic policy has been proposed in the literature. In this paper, we develop an easy-to-compute approximation algorithm for this class of problems and prove that it admits a theoretical worst-case performance guarantee under independent and many commonly used positively correlated demand processes. Our worst-case analysis departs significantly from those in the previous studies, requiring several novel ideas. In particular, we introduce a transient unit-matching rule to dynamically match the supply and demand units, and the notion of associated demand processes that provides the right future demand information to establish the desired results. Our numerical study demonstrates the effectiveness of the proposed algorithm. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

This paper investigates a decomposition approach for binary optimization problems with nonlinear objectives and linear constraints. Our methodology relies on the partition of the objective function into separate low-dimensional dynamic programming (DP) models, each of which can be equivalently represented as a shortest-path problem in an underlying state-transition graph. We show that the associated transition graphs can be related by a mixed-integer linear program (MILP) so as to produce exact solutions to the original nonlinear problem. To address DPs with large state spaces, we present a general relaxation mechanism that dynamically aggregates states during the construction of the transition graphs. The resulting MILP provides both lower and upper bounds to the nonlinear function, and it may be embedded in branch-and-bound procedures to find provably optimal solutions. We describe how to specialize our technique for structured objectives (e.g., submodular functions) and consider three problems arising in revenue management, portfolio optimization, and healthcare. Numerical studies indicate that the proposed technique often outperforms state-of-the-art approaches by orders of magnitude in these applications. Data and the online appendix are available at https://doi.org/10.1287/mnsc.2017.2849. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

In many sequential decision-making settings where there is uncertainty about the reward of each action, frequent selection of specific actions may reduce expected reward while choosing less frequently selected actions could lead to an increase. These effects are commonly observed in settings ranging from personalized healthcare interventions and targeted online advertising. To address this problem, the authors propose a new class of models called ROGUE (reducing or gaining unknown efficacy) multiarmed bandits. In the paper, the authors present a maximum likelihood approach to estimate the parameters of these models, and we show that these estimates can be used to construct upper confidence bound algorithms and epsilon-greedy algorithms for optimizing these models with strong theoretical guarantees. The authors conclude with a simulation study to show that these algorithms perform better than current nonstationary bandit algorithms in terms of both cumulative regret and average reward. Many settings involve sequential decision making where a set of actions can be chosen at each time step, each action provides a stochastic reward, and the distribution for the reward provided by each action is initially unknown. However, frequent selection of a specific action may reduce the expected reward for that action, whereas abstaining from choosing an action may cause its expected reward to increase. Such nonstationary phenomena are observed in many real-world settings such as personalized healthcare adherence–improving interventions and targeted online advertising. Though finding an optimal policy for general models with nonstationarity is PSPACE-complete, we propose and analyze a new class of models called reducing or gaining unknown efficacy (ROGUE) bandits, which we show in this paper can capture these phenomena and are amenable to the design of policies with provable properties. We first present a consistent maximum likelihood approach to estimate the parameters of these models and conduct a statistical analysis to construct finite sample concentration bounds. Using this analysis, we develop and analyze two different algorithms for optimizing ROGUE models: an upper confidence bound algorithm (ROGUE-UCB) and an ɛ-greedy algorithm (ɛ-ROGUE). Our theoretical analysis shows that under proper conditions, the ROGUE-UCB and ɛ-ROGUE algorithms can achieve logarithmic in time regret, unlike existing algorithms, which result in linear regret. We conclude with a numerical experiment using real-world data from a personalized healthcare adherence–improving intervention to increase physical activity. In this intervention, the goal is to optimize the selection of messages (e.g., confidence increasing versus knowledge increasing) to send to each individual each day to increase adherence and physical activity. Our results show that ROGUE-UCB and ɛ-ROGUE perform better in terms of aggregated regret and average reward when compared with state-of-the-art algorithms, and in the context of this intervention, the use of ROGUE-UCB increases daily step counts by roughly 1,000 steps a day (about a half-mile more of walking) compared with other algorithms in a simulation experiment. [ABSTRACT FROM AUTHOR]

Mixture models are versatile tools that are used extensively in many fields, including operations, marketing, and econometrics. The main challenge in estimating mixture models is that the mixing distribution is often unknown, and imposing a priori parametric assumptions can lead to model misspecification issues. In this paper, we propose a new methodology for nonparametric estimation of the mixing distribution of a mixture of logit models. We formulate the likelihood-based estimation problem as a constrained convex program and apply the conditional gradient (also known as Frank–Wolfe) algorithm to solve this convex program. We show that our method iteratively generates the support of the mixing distribution and the mixing proportions. Theoretically, we establish the sublinear convergence rate of our estimator and characterize the structure of the recovered mixing distribution. Empirically, we test our approach on real-world datasets. We show that it outperforms the standard expectation-maximization (EM) benchmark on speed (16 times faster), in-sample fit (up to 24% reduction in the log-likelihood loss), and predictive (average 28% reduction in standard error metrics) and decision accuracies (extracts around 23% more revenue). On synthetic data, we show that our estimator is robust to different ground-truth mixing distributions and can also account for endogeneity. This paper was accepted by Serguei Netessine, operations management. [ABSTRACT FROM AUTHOR]

We study the nonuniform capacitated multi-item lot-sizing problem. In this problem, there is a set of demands over a planning horizon of T discrete time periods, and all demands must be satisfied on time. We can place an order at the beginning of each period s, incurring an ordering cost Ks. In this order, we can order up to Cs units of products. On the other hand, carrying inventory from time to time incurs an inventory holding cost. The goal of the problem is to find a feasible solution that minimizes the sum of ordering and holding costs. Levi et al. [Levi R, Lodi A, Sviridenko M (2008) Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities. Math. Oper. Res. 33(2):461–474.] gave a two-approximation for the problem when the capacities Cs are the same. Extending the result to the case of nonuniform capacities requires new techniques as pointed out in the discussion section of their paper. In this paper, we solve the problem by giving a 10-approximation algorithm for the capacitated multi-item lot-sizing problem with general capacities. The constant approximation is achieved by adding an exponential number of new covering inequalities to the natural facility location–type linear programming (LP) relaxation for the problem. Along the way of our algorithm, we reduce the lot-sizing problem to two generalizations of the classic knapsack-covering problem. We give LP-based constant approximation algorithms for both generalizations via the iterative rounding technique. [ABSTRACT FROM AUTHOR]