In this paper, we describe a branch-and-price algorithm for the personalized nurse scheduling problem. The variants that appear in the literature involve a large number of constraints that can be hard or soft, meaning that they can be violated at the price of a penalty. We capture the diversity of the constraints on individual schedules by seven generic constraints characterized by lower and upper bounds on a given quantity. The core of the column generation procedure is in the identification of individual schedules with minimum reduced cost. For this, we solve a shortest path problem with resource constraints (SPPRC) where several generic constraints are modeled as resource constraints. We then describe dominance rules adapted to the presence of both upper and lower bounds on the resources and leverage soft constraints to improve the dominance. We also describe several acceleration techniques for the solution of the SPPRC, and branching rules that fit the specificities of the problem. Our numerical experiments are based on the instances of three benchmarks of the literature including those of the two international nurse rostering competitions (INRC-I and INRC-II). Their objective is threefold: assess the dominance rules and the acceleration techniques, investigate the capacity of the algorithm to find provable optimal solutions of instances that are still open, and conduct a comparison with best published results. The most noticeable conclusion is that the improved solution of the SPPRC allows to solve optimally all the INRC-II instances where a four-week planning horizon is considered and 40% of the eight-week instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0019 .

Many discrete optimization problems amount to selecting a feasible set of edges of least weight. We consider in this paper the context of spatial graphs where the positions of the vertices are uncertain and belong to known uncertainty sets. The objective is to minimize the sum of the distances of the chosen set of edges for the worst positions of the vertices in their uncertainty sets. We first prove that these problems are [Formula: see text]-hard even when the feasible sets consist either of all spanning trees or of all s – t paths. Given this hardness, we propose an exact solution algorithm combining integer programming formulations with a cutting plane algorithm, identifying the cases where the separation problem can be solved efficiently. We also propose a conservative approximation and show its equivalence to the affine decision rule approximation in the context of Euclidean distances. We compare our algorithms to three deterministic reformulations on instances inspired by the scientific literature for the Steiner tree problem and a facility location problem. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.1276 .

Abstract We consider a time‐dependent shortest path problem with possible waiting at some nodes of the graph and a global bound W on the total waiting time. The goal is to minimize the time traveled along the edges of the path, not including the waiting time. We prove that the problem can be solved in polynomial time when the travel time functions are piecewise linear and continuous. The algorithm relies on a recurrence relation characterized by a bound ω on the total waiting time, where 0 ≤ ω ≤ W. We show that only a small number of values ω1, ω2, …, ωK need to be considered, where K depends on the total number of breakpoints of all travel time functions.

Abstract We study a variant of the shortest path problem in a congested environment. In this setting, the travel time of each arc is represented by a piecewise continuous affine function of departure time. Besides, the driver is allowed to wait at nodes to avoid wasting time in traffic. While waiting, the driver is able to perform useful tasks for her job or herself, so the objective is to minimize only driving time. Although optimal solutions may contain cycles and pseudo‐polynomially many arcs, we provide a representation of the solutions that is polynomial in the absolute value of the inverse of the slopes as well as in the dimensions of the graph. We further prove that the problem is ‐Hard when the slopes are integer. We introduce a restriction of the problem where waits must be integer and propose pseudo‐polynomial algorithms for the latter. We also provide a pseudo‐FPTAS, polynomial in the ratio between the bound on the total waiting time and the minimum travel time. Finally, we discuss harder variants of the problem and show their inapproximability.

In this article, we propose a general framework for an algorithm derived from the primal simplex that guarantees a strict improvement in the objective after each iteration. Our approach relies on the identification of compatible variables that ensure a nondegenerate iteration if pivoted into the basis. The problem of finding a strict improvement in the objective function is proved to be equivalent to two smaller problems, respectively, focusing on compatible and incompatible variables. We then show that the improved primal simplex (IPS) is a particular implementation of this generic theoretical framework. The resulting new description of IPS naturally emphasizes what should be considered as necessary adaptations of the framework versus specific implementation choices. This provides original insight into IPS that allows for the identification of weaknesses and potential alternative choices that would extend the efficiency of the method to a wider set of problems. We perform experimental tests on an extended collection of data sets including instances of Mittelmann’s benchmark for linear programming. The results confirm the excellent potential of IPS and highlight some of its limits while showing a path toward an improved implementation of the generic algorithm.

Any significant increase in current levels of air traffic will need the support of efficient decision-aid tools. One of the tasks of air traffic management is to modify trajectories when necessary to maintain a sufficient separation between pairs of aircraft. Several algorithms have been developed to solve this problem, but the diversity in the underlying assumptions makes it difficult to compare their performance. In this paper, separation is maintained through changes of heading and velocity while minimizing a combination of fuel consumption and delay. For realistic trajectories, the speed is continuous with respect to time, the acceleration and turning rate are bounded, and the planned trajectories are recovered after the maneuvers. After describing the major modifications to existing models that are necessary to satisfy this definition of the problem, we compare three mixed-integer linear programs. The first model is based on a discretization of the airspace and the second relies on a discretization of the time horizon. The third model implements a time decomposition of the problem; it allows only one initial maneuver and is periodically solved with a receding horizon to build a complete trajectory. The computational tests are conducted on a benchmark of artificial instances specifically built to include complex situations. Our analysis of the results highlights the strengths and limits of each model. The time decomposition proves to be an excellent compromise.

The approach presented in this paper aims at finding a solution to the problem of conflict-free motion planning for multiple aircraft on the same flight level with trajectory recovery. One contribution of this work is to develop three consistent models, i.e., from a continuous-time representation to a discrete-time linear approximation. Each of these models guarantees separation at all times and trajectory recovery, but they are not equally difficult to solve. A new hybrid algorithm is thus developed to use the optimal solution of a mixed-integer linear program as a starting point when solving a nonlinear formulation of the problem. The significance of this process is that it always finds a solution when the linear model is feasible while still taking into account the nonlinear nature of the problem. A test bed containing numerous data sets is then generated from three virtual scenarios. A comparative analysis with three different initializations of nonlinear optimization validates the efficiency of the hybrid method.