This paper considers a class of two-stage stochastic mixed-integer optimization problems where, for a given first-stage solution, we can determine the optimal values of recourse variables sequentially. This class of problems arises in a wide variety of applications. In the case of multivariate discrete distributions for uncertain parameters, a standard stochastic programming formulation of these problems involves an exponential number of scenarios, therefore an exponential number of variables and constraints. We propose a new mixed-integer programming modeling approach where the number of variables and constraints is independent of the number of scenarios and scales at most pseudopolynomially with the problem size. The proposed modeling approach relies on state variables that track the system’s state as the uncertainty realizes sequentially. We demonstrate the advantages of the proposed approach in two applications arising in project scheduling and operating room allocation. Summary of Contribution: This paper proposes a new modeling approach for a class of two-stage stochastic optimization problems that is computationally more efficient than the traditional scenario-based stochastic integer programming models. The proposed modeling approach relies on state variables that track the system's state as the uncertainty realizes sequentially. We demonstrated the efficiency of the proposed approach by computational results on two applications in project scheduling and operating room allocation.

Finding a shortest path in a network is a fundamental optimization problem. We focus on settings in which the travel time on an arc in the network depends on the time at which traversal of the arc begins. In such settings, reaching the destination as early as possible is not the only objective of interest. Minimizing the duration of the path, that is, the difference between the arrival time at the destination and the departure from the origin, and minimizing the travel time along the path from origin to destination, are also of interest. We introduce dynamic discretization discovery algorithms to efficiently solve such time-dependent shortest path problems with piecewise linear arc travel time functions. The algorithms operate on partially time-expanded networks in which arc costs represent lower bounds on the arc travel time over the subsequent time interval. A shortest path in this partially time-expanded network yields a lower bound on the value of an optimal path. Upper bounds are easily obtained as by-products of the lower bound calculations. The algorithms iteratively refine the discretization by exploiting breakpoints of the arc travel time functions. In addition to time discretization refinement, the algorithms permit time intervals to be eliminated, improving lower and upper bounds, until, in a finite number of iterations, optimality is proved. Computational experiments show that only a small fraction of breakpoints must be explored and that the fraction decreases as the length of the time horizon and the size of the network increases, making the algorithms highly efficient and scalable. Summary of Contribution: New data collection techniques have increased the availability and fidelity of time-dependent travel time information, making the time-dependent variant of the classic shortest path problem an extremely relevant problem in the field of operations research. This paper provides novel algorithms for the time-dependent shortest path problem with both the minimum duration and minimum travel time objectives, which aims to address the computational challenges faced by existing algorithms. A computational study shows that our new algorithm is indeed significantly more efficient than existing approaches.

Abstract The service network design problem is commonly used to represent the tactical decisions encountered by a consolidation carrier operating a hub‐and‐spoke network: what transportation services to operate between hubs and how to route commodities from their origin to their destination through the network. In most settings, the capacity at hubs is not a limiting factor and can safely be ignored. However, in the context of city logistics networks, where space is limited and expensive, hub capacities typically have to be taken into account. The presence of hub capacity (and time) constraints implies that, contrary to traditional service network design problems, the existence of a feasible solution is no longer guaranteed. We present an exact dynamic discretization discovery algorithm for a variant of the service network design problem in which the number of vehicles that can be loaded and unloaded simultaneously at a hub is restricted. Novel techniques are introduced in the algorithm to handle the hub capacity constraints. A computational study using instances derived from real‐world data shows the potential of dynamic discretization discovery for this class of problems: integer program sizes are reduced by a factor of up to one thousand and small to mid size instances can be (optimally) solved in an acceptable amount of time.

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 We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all IPs provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is integral so that it can be solved as a linear program. However, the number of IPs grows exponentially with the number of terminals in the Steiner tree. As a consequence, we are able to solve the Steiner tree problem by solving a polynomial number of LPs, when the number of terminals is fixed.

We show how recently-defined abstract models of the Branch-and-Bound algorithm can be used to obtain information on how the nodes are distributed in B&B search trees. This can be directly exploited in the form of probabilities in a sampling algorithm given by Knuth that estimates the size of a search tree. This method reduces the offline estimation error by a factor of two on search trees from Mixed-Integer Programming instances.

``Primal heuristics'' are a key contributor to the improved performance of exact branch-and-bound solvers for combinatorial optimization and integer programming. Perhaps the most crucial question concerning primal heuristics is that of at which nodes they should run, to which the typical answer is via hard-coded rules or fixed solver parameters tuned, offline, by trial-and-error. Alternatively, a heuristic should be run when it is most likely to succeed, based on the problem instance's characteristics, the state of the search, etc. In this work, we study the problem of deciding at which node a heuristic should be run, such that the overall (primal) performance of the solver is optimized. To our knowledge, this is the first attempt at formalizing and systematically addressing this problem. Central to our approach is the use of Machine Learning (ML) for predicting whether a heuristic will succeed at a given node. We give a theoretical framework for analyzing this decision-making process in a simplified setting, propose a ML approach for modeling heuristic success likelihood, and design practical rules that leverage the ML models to dynamically decide whether to run a heuristic at each node of the search tree. Experimentally, our approach improves the primal performance of a state-of-the-art Mixed Integer Programming solver by up to 6% on a set of benchmark instances, and by up to 60% on a family of hard Independent Set instances.

The design of strategies for branching in Mixed Integer Programming (MIP) is guided by cycles of parameter tuning and offline experimentation on an extremely heterogeneous testbed, using the average performance. Once devised, these strategies (and their parameter settings) are essentially input-agnostic. To address these issues, we propose a machine learning (ML) framework for variable branching in MIP.Our method observes the decisions made by Strong Branching (SB), a time-consuming strategy that produces small search trees, collecting features that characterize the candidate branching variables at each node of the tree. Based on the collected data, we learn an easy-to-evaluate surrogate function that mimics the SB strategy, by means of solving a learning-to-rank problem, common in ML. The learned ranking function is then used for branching. The learning is instance-specific, and is performed on-the-fly while executing a branch-and-bound search to solve the MIP instance. Experiments on benchmark instances indicate that our method produces significantly smaller search trees than existing heuristics, and is competitive with a state-of-the-art commercial solver.

We present two decomposition algorithms for single product deep-sea maritime inventory routing problems (MIRPs) that possess a core substructure common in many real-world applications. The problem involves routing vessels, each belonging to a particular vessel class, between loading and discharging ports, each belonging to a particular region. Our algorithms iteratively solve a MIRP by zooming out and then zooming in on the problem. Specifically, in the “zoomed out” phase, we solve a first-stage master problem in which aggregate information about regions and vessel classes is used to route vessels between regions, while only implicitly considering inventory and capacity requirements, berth limits, and other side constraints. In the “zoomed in” phase, we solve a series of second-stage subproblems, one for each region, in which individual vessels are routed through each region and load and discharge quantities are determined. Computational experience shows that an integrated approach that combines these two algorithms is vastly superior to solving the problem directly with a commercial mixed-integer programming solver.

We develop an exact algorithm for integer programs that uses restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for generating these problem restrictions and for producing bounds on the value of the optimal solution. The performance of the algorithm is greatly enhanced by using structure, such as arises in network flow type applications, to help define the restrictions that are solved. In addition, local search around the current best solution is incorporated to enhance overall performance. The approach is parallelized and computational experiments on a classical problem in network design demonstrate its efficacy.

Consider a network 𝒩 =(N, A) and associate with each arc e ∈ A a fixed cost ce for using arc e, an interval [le, ue] (le, ue ∈ ℤ) specifying the range of allowable resource consumption quantities along arc e, and a per-unit cost [Formula: see text] for resource consumed along e. Furthermore, for each node n ∈ N, let Un ∈ ℤ be the maximum amount of resource consumption a path can accumulate before visiting node n. Given a source node ns ∈ N and sink node nt ∈ N, the fixed-charge shortest-path problem (FCSPP) seeks to find a minimum-cost-feasible path from ns to nt. When resource consumption is simply additive, the resource-constrained shortest-path problem (RCSPP) is a special case of FCSPP. We develop a new dynamic programming algorithm for FCSPP. The algorithm uses solutions from labeling and dominance techniques for standard RCSPPs on slightly modified problems, and it combines these solutions by exploiting the structure provided by certain classes of knapsack problems to efficiently construct an optimal solution to FCSPP. Computational experiments demonstrate that our algorithm is often several orders of magnitude faster than naive dynamic programming procedures.

We present a relaxation-based dynamic programming algorithm for solving resource-constrained shortest-path problems (RCSPPs) in the context of column generation for the dial-a-flight problem. The resulting network formulation and pricing problem require solving RCSPPs on extremely large time-expanded networks having a huge number of local resource constraints, i.e., constraints that apply to small subnetworks. The relaxation-based dynamic programming algorithm alternates between a forward and a backward search. Each search employs bounds derived in the previous search to prune the search space. Between consecutive searches, the relaxation is tightened using a set of critical resources and a set of critical arcs over which these resources are consumed. As a result, a relatively small state space is maintained, and many paths can be pruned while guaranteeing that an optimal path is ultimately found.

We describe families of inequalities for 0–1 mixed-integer programming problems that are obtained by lifting cover and packing inequalities. We show that these inequalities can be separated from single rows of the simplex tableaux of their linear programming relaxations. We present the results of a computational study comparing their performance with that of Gomory mixed-integer cuts on a collection of MIPLIB and randomly generated 0–1 mixed-integer programs. The computational study shows that these cuts yield better results than Gomory mixed-integer cuts.

The use of simple auction mechanisms like the GSP in online advertising can lead to significant loss of efficiency and revenue when advertisers have rich preferences — even simple forms of expressiveness like budget constraints can lead to suboptimal outcomes. While the optimal allocation of inventory can provide greater efficiency and revenue, natural formulations of the underlying optimization problems grow exponentially in the number of features of interest, presenting a key practical challenge. To address this problem, we propose a means for automatically partitioning inventory into abstract channels so that the least relevant features are ignored. Our approach, based on LP/MIP column and constraint generation, dramatically reduces the size of the problem, thus rendering optimization computationally feasible at practical scales. Our algorithms allow for principled tradeoffs between tractability and solution quality. Numerical experiments demonstrate the computational practicality of our approach as well as the quality of the resulting abstractions.

We develop a solution approach for the fixed-charge network flow (FCNF) problem that produces provably high-quality solutions quickly. The solution approach combines mathematical programming algorithms with heuristic search techniques. To obtain high-quality solutions, it relies on neighborhood search with neighborhoods that involve solving carefully chosen integer programs derived from the arc-based formulation of FCNF. To obtain lower bounds, the linear programming relaxation of the path-based formulation of FCNF is used and strengthened with cuts discovered during the neighborhood search. The solution approach incorporates randomization to diversify the search and learning to intensify the search. Computational experiments demonstrate the efficacy of the proposed approach.

This paper studies two mixed-integer linear programming (MILP) formulations for piecewise linear functions considered in Li et al. [Li, H.-L., H.-C. Lu, C.-H. Huang, N.-Z. Hu. 2009. A superior representation method for piecewise linear functions. INFORMS J. Comput. 21(2) 314–321]. Although the ideas used to construct one of these formulations are theoretically interesting and could eventually provide a computational advantage, we show that their use in modeling piecewise linear functions yields a poor MILP formulation. We specifically show that neither of the formulations in this paper has a favorable strength property shared by all standard MILP formulations for piecewise linear functions. We also show that both formulations in Li et al. (2009) are significantly outperformed computationally by standard MILP formulations.

This paper develops a linear-programming-based branch-and-bound algorithm for mixed-integer conic quadratic programs. The algorithm is based on a known higher-dimensional or lifted polyhedral relaxation of conic quadratic constraints. The algorithm is different from other linear-programming-based branch-and-bound algorithms for mixed-integer nonlinear programs in that it is not based on cuts from gradient inequalities and it sometimes branches on integer feasible solutions. The algorithm is tested on a series of portfolio optimization problems. It is shown that it significantly outperforms commercial and open-source solvers based on both linear and nonlinear relaxations.

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

We investigate several complexity issues related to branch-and-cut algorithms for 0-1 integer programming based on lifted-cover inequalities (LCIs). We show that given a fractional point, determining a violated LCI over all minimal covers is NP-hard. The main result is that there exists a class of 0-1 knapsack instances for which any branch-and-cut algorithm based on LCIs has to evaluate an exponential number of nodes to prove optimality.

We investigate the algorithmic and implementation issues related to the effective and efficient use of lifted cover inequalities and lifted GUB cover inequalities in a branch and cut algorithm for 0-1 integer programming. We have tried various strategies on several test problems and we identify the best ones for use in practice.