Abstract Scalarization is a common technique to transform a multiobjective optimization problem into a scalar-valued optimization problem. This article deals with the weighted Tchebycheff scalarization applied to multiobjective discrete optimization problems. This scalarization consists of minimizing the weighted maximum distance of the image of a feasible solution to some desirable reference point. By choosing a suitable weight, any Pareto optimal image can be obtained. In this article, we provide a comprehensive theory of this set of eligible weights. In particular, we analyze the polyhedral and combinatorial structure of the set of all weights yielding the same Pareto optimal solution as well as the decomposition of the weight set as a whole. The structural insights are linked to properties of the set of Pareto optimal solutions, thus providing a profound understanding of the weighted Tchebycheff scalarization method and, as a consequence, also of all methods for multiobjective optimization problems using this scalarization as a building block.

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.

Abstract. This note corrects an error in our paper “N. Boland, R. Clement, and H. Waterer. A bucket indexed formulation for nonpreemptive single machine scheduling problems. INFORMS Journal on Computing 28(1):14–30, 2016.”

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.

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.

We consider multistage stochastic programming problems in which the random parameters have finite support, leading to optimization over a finite scenario set. There has been recent interest in dual bounds for such problems, of two types. One, known as expected group subproblem objective (EGSO) bounds, require solution of a group subproblem, which optimizes over a subset of the scenarios, for all subsets of the scenario set that have a given cardinality. Increasing the subset cardinality in the group subproblem improves bound quality, (EGSO bounds form a hierarchy), but the number of group subproblems required to compute the bound increases very rapidly. Another is based on partitions of the scenario set into subsets. Combining the values of the group subproblems for all subsets in a partition yields a partition bound. In this paper, we consider partitions into subsets of (nearly) equal cardinality. We show that the expected value of the partition bound over all such partitions also forms a hierarchy. To make use of these bounds in practice, we propose random sampling of partitions and suggest two enhancements to the approach: sampling partitions that align with the multistage scenario tree structure and use of an auxiliary optimization problem to discover new best bounds based on the values of group subproblems already computed. We establish the effectiveness of these ideas with computational experiments on benchmark problems. Finally, we give a heuristic to save computational effort by ceasing computation of a partition partway through if it appears unpromising.

Despite recent interest in multiobjective integer programming, few algorithms exist for solving biobjective mixed integer programs. We present such an algorithm: the boxed line method. For one of its variants, we prove that the number of single-objective integer programs solved is bounded by a linear function of the number of nondominated line segments in the nondominated frontier. This is the first such complexity result. An extensive computational study demonstrates that the box line method is also efficient in practice and that it outperforms existing algorithms on a diverse set of instances.

We consider the inventory routing problem, in which a supplier has to replenish a set of customers by means of a limited fleet of capacitated vehicles over a discrete time horizon. The goal is to minimize the total cost of the distribution that comprises the inventory cost at the supplier and at the customers and the routing cost. We present a matheuristic that combines a tabu search and mathematical programming formulations. When compared with two exact methods on 640 small instances, the matheuristic finds 192 (48%) optima over the 402 instances with known optima and improves 125 upper bounds. Tested on 240 large instances (with up to 200 customers) for which no optimal solutions are known, it improves the best solution for 220 (92%) of the 240 instances. The online supplement is available at https://doi.org/10.1287/ijoc.2016.0737 .

A new mixed-integer linear programming (MILP) formulation for nonpreemptive single machine scheduling problems is presented. The model is a generalisation of the classical time indexed (TI) model to one in which at most two jobs can be processing in each time period. Like the TI model, the new model, called the bucket indexed (BI) model, partitions the planning horizon into periods of equal length, or buckets. Unlike the TI model, the length of a period is a parameter of the BI model and can be chosen to be as long as the processing time of the shortest job. The two models are equivalent if a period is of unit length, but when longer periods are used in the BI model, it can have significantly fewer variables and nonzeros than the corresponding TI model. A computational study using weighted tardiness instances, and weighted completion time instances with release dates, reveals that the BI model significantly outperforms the TI model on instances where the minimum processing time of the jobs is large. Furthermore, the performance of the BI model is less vulnerable to increases in average processing time when the ratio of the largest processing time to the smallest is held constant.

We present the first criterion space search algorithm, the triangle splitting method, for finding all nondominated points of a biobjective mixed integer program. The algorithm is relatively easy to implement and converges quickly to the complete set of nondominated points. The algorithm maintains, at any point in time, a diverse set of nondominated points, and is thus ideally suited for fast approximation of the nondominated frontier. An extensive computational study demonstrates the efficacy of the triangle splitting method. Data, as supplemental material, are available at http://dx.doi.org/10.1287/ijoc.2015.0646 .

We present a new criterion space search algorithm, the balanced box method, for finding all nondominated points of a biobjective integer program. The method extends the box algorithm, is easy to implement, and converges quickly to the complete set of nondominated points. Because the method maintains, at any point in time, a diverse set of nondominated points, it is ideally suited for fast approximation of the efficient frontier. In addition, we present several enhancements of the well-known ε-constraint, augmented weighted Tchebycheff, and perpendicular search methods. An extensive computational study, using instances from different classes of combinatorial optimization problems, demonstrates the efficacy of the balanced box method.

Abstract We study the problem of scheduling maintenance on arcs of a capacitated network to maximize the total flow from a source node to a sink node over a set of time periods. Maintenance on an arc shuts down the arc for the duration of the period in which its maintenance is scheduled, making its capacity zero for that period. A set of arcs is designated to have maintenance during the planning period, which will require each to be shut down for exactly one time period. In general this problem is known to be NP‐hard. Here we identify a number of characteristics that are relevant for the complexity of instance classes. In particular, we discuss instances with restrictions on the set of arcs that have maintenance to be scheduled; series‐parallel networks; capacities that are balanced, in the sense that the total capacity of arcs entering a (nonterminal) node equals the total capacity of arcs leaving the node; and identical capacities on all arcs. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 196–202 2014

Finding a delivery plan for cancer radiation treatment using multileaf collimators operating in “step-and-shoot” mode can be formulated mathematically as a problem of decomposing an integer matrix into a weighted sum of binary matrices having the consecutive-ones property and sometimes other properties related to the collimator technology. The efficiency of the delivery plan is measured by both the sum of the weights in the decomposition, known as the total beam-on time, and the number of different binary matrices appearing in it, referred to as the cardinality, the latter being closely related to the setup time of the treatment. In practice, the total beam-on time is usually restricted to its minimum possible value (which is easy to find), and a decomposition that minimizes cardinality (subject to this restriction) is sought. This decomposition problem is known to be NP-hard, and the best available exact solution methods cannot solve, in reasonable time, problems with dimensions large enough to be of use in actual medical applications. In this paper, we propose a new heuristic. To ensure that the heuristic is computationally efficient, we make use of exact bounds that apply to the decomposition and prove that these bounds can be computed efficiently. We demonstrate that the heuristic performs very well numerically against the best previously published heuristic (that of Kalinowski), reducing the average gap between the cardinality of the solution found and the optimal value by 37% on the largest problems tested (for which optimal solutions could be found). Importantly, this new heuristic performs well on those instances that are problematical for Kalinowski's heuristic. A “best-of” algorithm, combining heuristics, produces a decomposition with cardinality within one of optimal in about 98.7% of instances tested (for which an optimal solution is available). It reduces the cardinality of solutions produced by about 5% on average. On instances for which optimal solutions can be found, it more than halves the optimality gap and finds an optimal solution in about 28% more cases than Kalinowski's heuristic.

Abstract Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP), for example Beasley and Christofides (Beasley and Christofides, Networks 19 (1989), 379–394), calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and edges. However, for each node and edge, a Lagrangean dual problem exists whose solution may differ from the relaxation of the full problem. Thus, using one Lagrange multiplier does not offer the best possible network reduction. Furthermore, eliminating nodes and edges from the network may change the Lagrangean dual solutions in the remaining reduced network, warranting an iterative solution and reduction procedure. We develop a method for solving the related Lagrangean dual problems for each edge simultaneously which is iterated with eliminating nodes and edges. We demonstrate the effectiveness of our method computationally: we test it against several others and show that it both reduces solve time and the number of intractable problems encountered. We use a modified version of Carlyle and Wood's (38th Annual ORSNZ Conference, Hamilton, New Zealand, November, 2003) enumeration algorithm in the gap closing stage. We also make improvements to this algorithm and test them computationally. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract In this paper we introduce a new formulation of the vehicle routing problem with time windows (VRPTW) involving only binary variables. The new formulation is based on the formulation of the asymmetric traveling salesman problem with time windows by Ascheuer et al. (Networks 36 (2000) 69–79) and has the advantage of avoiding additional variables and linking constraints. In the new formulation, time windows are modeled using path inequalities that eliminate time and capacity infeasible paths. We present a new class of strengthened path inequalities based on the polyhedral results obtained by Mak (Ph.D. Thesis, 2001) for a variant of the TSP. We study the VRPTW polytope and determine its dimension. We show that the lifted path inequalities are facet defining under certain assumptions. We also introduce precedence constraints in the context of the VRPTW. Computational experiments are performed with a branch and cut algorithm on the Solomon test problems with wide time windows. Based on results on 25‐node problems, the outcome is promising compared to leading algorithms in the literature. In particular, we report a solution to a previously unsolved 50‐node Solomon test problem R208. The conclusion is therefore that a polyhedral approach to the VRPTW is a viable alternative to the path formulation of Desrochers et al. (Oper Res 40 (1992), 342–354). © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 273–293 2007

Abstract In this article the modulation of intensity matrices arising in cancer radiation therapy using multileaf collimators (MLC) is investigated. It is shown that the problem is equivalent to decomposing a given integer matrix into a positive linear combination of (0, 1) matrices. These matrices, called shape matrices, must have the strict consecutive‐1‐property, together with another property derived from the technological restrictions of the MLC equipment. Various decompositions can be evaluated by their beam‐on time (time during which radiation is applied to the patient) or the treatment time (beam‐on time plus time for setups). We focus on the former, and develop a nonlinear mixed‐integer programming formulation of the problem. This formulation can be decomposed to yield a column generation formulation: a linear program with a large number of variables that can be priced by solving a subproblem. We then develop a network model in which paths in the network correspond to feasible shape matrices. As a consequence, we deduce that the column generation subproblem can be solved as a shortest path problem. Furthermore, we are able to develop two alternative models of the problem as side‐constrained network flow formulations, and so obtain our main theoretical result that the problem is solvable in polynomial time. Finally, a numerical comparison of our exact solutions with those of well‐known heuristic methods shows that the beam‐on time can be reduced by a considerable margin. © 2004 Wiley Periodicals, Inc.

Abstract Much has been written on shortest path problems with weight, or resource, constraints. However, relatively little of it has provided systematic computational comparisons for a representative selection of algorithms. Furthermore, there has been almost no work showing numerical performance of scaling algorithms, although worst‐case complexity guarantees for these are well known, nor has the effectiveness of simple preprocessing techniques been fully demonstrated. Here, we provide a computational comparison of three scaling techniques and a standard label‐setting method. We also describe preprocessing techniques which take full advantage of cost and upper‐bound information that can be obtained from simple shortest path information. We show that integrating information obtained in preprocessing within the label‐setting method can lead to very substantial improvements in both memory required and run time, in some cases, by orders of magnitude. Finally, we show how the performance of the label‐setting method can be further improved by making use of all Lagrange multiplier information collected in a Lagrangean relaxation first step. © 2003 Wiley Periodicals, Inc.

Intelligent backtracking is a technique used in constraint programming for reducing search in solving combinatorial feasibility problems. The technique uses information derived from small sets of infeasible constraints discovered in one part of the search space to avoid searching other, similar, regions. It is often able to reduce the size of the search space significantly. For many problems, however, the computational effort required to achieve this reduction in search space is prohibitive. We introduce an algorithm that uses intelligent backtracking inside a linear-programming based branch-and-bound framework. We show that minimal infeasible sets can immediately be deduced from the dual extreme ray associated with the infeasible linear program. This allows us to obtain the reduction in search space associated with intelligent backtracking, without paying the large computational cost. We show the implementation of our intelligent backtracking approach as a branch-and-cut algorithm, and present computational results.