Motivated by the needs from an airline crew scheduling application, we introduce structured convolutional kernel networks (Struct-CKN), which combine CKNs from Mairal et al. (2014) in a structured prediction framework that supports constraints on the outputs. CKNs are a particular kind of convolutional neural networks that approximate a kernel feature map on training data, thus combining properties of deep learning with the non-parametric flexibility of kernel methods. Extending CKNs to structured outputs allows us to obtain useful initial solutions on a flight-connection dataset that can be further refined by an airline crew scheduling solver. More specifically, we use a flight-based network modeled as a general conditional random field capable of incorporating local constraints in the learning process. Our experiments demonstrate that this approach yields significant improvements for the large-scale crew pairing problem (50,000 flights per month) over standard approaches, reducing the solution cost by 17% (a gain of millions of dollars) and the cost of global constraints by 97%.

Abstract The primal adjacency‐based algorithm and the multidirectional dynamic programming algorithm are two exact methods that have recently been developed to efficiently solve the shortest path problem with resource constraints (SPPRCs). These methods are primal in the sense that they are able to produce sequences of feasible solutions using iterative exploration of the search space. Since the SPPRCs often appear as a subproblem (SP) in the solution of vehicle and crew scheduling problems (VCSP) using column generation (CG), we propose a new primal column generation framework that embeds these primal methods in a CG scheme. The primal column generation solves at each iteration a sequence of appropriate restricted SP and stops solving the SP when there is no need to continue. This approach introduces a large degree of flexibility, and allows performing good cost improvements in a very limited time. Computational experiments on VCSP instances show that the proposed approach is able to find optimal solutions while reducing the time spent solving the SP by factors of up to seven compared to the standard CG algorithm. This leads to significant improvements in the overall solution times, with an average reduction factor of 3.5.

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.

Since its appearance in 1947, the primal simplex algorithm has been one of the most popular algorithms for solving linear programs. It is often very efficient when there is very little degeneracy, but it often struggles in the presence of high degeneracy, executing many pivots without improving the objective function value. In this paper, we propose an improved primal simplex algorithm that deals with this issue. This algorithm is based on new theoretical results that shed light on how to reduce the negative impact of degeneracy. In particular, we show that, from a nonoptimal basic solution with p positive-valued variables, there exists a sequence of at most m - p + 1 simplex pivots that guarantee the improvement of the objective value, where m is the number of constraints in the linear program. These pivots can be identified by solving an auxiliary linear program. Finally, we briefly summarize computational results that show the effectiveness of the proposed algorithm on degenerate linear programs.

This paper presents an optimal dynamic programming algorithm, the first such algorithm in the literature to solve the shortest path problem with time windows and additional linear costs on the node service start times. To optimally solve this problem, we propose a new dynamic programming algorithm which takes into account the linear node costs. This problem has numerous applications: Two examples are job-shop scheduling and aircraft routing and scheduling. To underline the efficiency of the proposed method, we compare it with an approach based on partial discretization of the time windows. It clearly outperformed the discretization approach on test problems with wide time windows and many nodes with negative costs. © 1998 John Wiley & Sons, Inc. Networks 31: 193–204, 1998

We study the problem of finding a shortest path for a car-like mobile robot with a minimal turning radius constraint. This vehicle can move either forward or backward in an unconstrained environment. By applying necessary conditions on the segment lengths of shortest paths, we partition the configuration space into elements such that a single path type is associated with 150 elements and two path types are associated with the other 11 elements. A shortest path from a fixed initial configuration to any final configuration in an element can always be found among the paths of types associated with that element. We then present an algorithm based on this partition and we give results showing that our algorithm is 15 times faster on average than the Reeds-Shepp algorithm (1990).

Abstract We present a new two‐commodity flow formulation for the traveling salesman problem. Each commodity corresponds to a resource that is either distributed or picked up along the tour of all nodes. This formulation is partcularly well suited to handling time window constraints; the resource used is then the time. This formulation can be extended to the makespan problem. For a n‐node problem, the linear relaxation of the formulation involves only O(n) constraints and O(n2) variables. Implementation issues are discussed and numerical experimentations have been realized for problems of up to 60 nodes. © 1993 by John Wiley & Sons, Inc.

Abstract One important issue being addressed in the design of Distributed Computer Networks is how to increase the availability of time‐changing information even in the event of failures. Recently, a technique called “stashing” was proposed. Stashing a file signifies placing a copy of that file in several nodes of the network. In addition, a “predicate” has been defined as a consistency requirement for a particular file copy with respect to the original. We address the problem of minimizing the propagation cost of stashed copies subject to predicate restrictions imposed by the user. In the version of the problem that we tackle, the user may receive a copy with a predicate better than requested. We call this problem the Dynamic Predicate Stashing Copy Problem (DPSCP) and propose a formulation to solve it. Resolution approaches, numerical results, and properties of the problem are also discussed. © 1993 by John Wiley & Sons, Inc.

A reliability measure that takes into account routing and rerouting policies after failures as well as the capacity of the network to satisfy its demand is proposed. The measure, based on the evaluation of the lost call traffic, needs resolution of a routing model for the states of perfect functioning as well as the most probable failure states. A type of routing model useful for network planning is also proposed. The model is closer to reality and easier to implement than the other classical multicommodity formulations. A convex-simplex implementation with a reoptimization feature explicitly adapted to the proposed model is used.>

Abstract Consider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost, and a time interval within which the trip must begin. The trips may include visits to one or more specific points. Our problem is to determine the number of vehicles required, together with their routes and schedules, so that each trip begins within its given time interval, while the fixed costs related to the number of vehicles, and the travel costs between trips, are minimized. The problem is a generalization of the m‐traveling salesman problem. We use column generation on a set partitioning problem solved by simplex and branch‐and‐bound; columns are generated by a shortest path algorithm with time windows on the nodes. Numerical results for several school bus transportation problems with up to 151 trips are discussed.