# Jacques Desrosiers

Back## Publications

### Cahiers du GERAD

**Jacques Desrosiers**

This paper presents the properties of the minimum mean cycle-canceling algorithm for solving linear programming models. Originally designed by Goldberg ...

BibTeX reference

This paper addresses the solution of the capacitated minimum cost flow problem on a network containing `\(n\)`

nodes and `\(m\)`

arcs. Satisfying necessary ...

In this paper, we propose an integer programming model for obtaining lower bounds for the curriculum-based course timetabling problem, in which weekly assign...

BibTeX reference

This paper describes a vector space decomposition algorithmic framework for linear programming guided by dual feasibility considerations. The resolution pro...

BibTeX reference

This paper introduces a new primal algorithm for solving a linear program *LP*. In this algorithm, a pricing problem, namely a linear fractional program, is ...

This paper describes three recent tools for dealing with primal degeneracy in linear programming.
The first one is the *Improved Primal Simplex* (IPS) algor...

Given a linear program (*LP* ) with *m* constraints and *n* lower and upper bounded variables, any solution `\(x^0\)`

to *LP* can be represented as a nonne...

This paper focuses on the resolution of the capacitated minimum cost flow problem on a network comprising <i>n</i> nodes and <i>m</i> arcs. We present a met...

BibTeX reference

This paper presents the first direct implementation of the positive edge criterion using COIN-OR's CLP, where it has been combined with the Devex pivot rule....

BibTeX reference**Jacques Desrosiers**, Thibaut Vidal, and Bruno Salezze Vieira

Onshore oil fields may contain hundreds of wells that use sophisticated and complex equipments. These equipments need maintenance regularly to keep the...

BibTeX reference

Dantzig-Wolfe reformulation solved by Column Generation is an approach to obtain improved bounds for Mixed Integer Programs. A downside of this approach is t...

BibTeX reference

Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add var...

BibTeX reference

Dynamic constraint aggregation (DCA) and dual variable stabilization (DVS) are two methods that can reduce the negative impact of degeneracy when solvi...

BibTeX reference

In an onshore oil field, the productivity of oil wells decreases when they require maintenance. To restore full productivity at a well, it must be visi...

BibTeX reference**Jacques Desrosiers**

The Job Grouping Problem consists of assigning a set of jobs, each with a specific set of tool requirements, to machines with a limited tool capacity in orde...

BibTeX reference

Column generation for solving linear programs with a huge number of variables alternately solves a (restricted) master problem and a pricing subproblem to ad...

BibTeX referencePositive Edge: A Pricing Criterion for the Identification of Non-Degenerate Simplex Pivots

The <i>positive edge</i> is a new pricing rule for the primal simplex: it identifies, with a probability error less than or equal to 2<sup>-30</sup> in sing...

BibTeX reference**Jacques Desrosiers**

In this paper, we generalize the Asymmetric Representatives Formulation, which was first introduced by Campêlo et al. (2008) for the Node Coloring Problem. ...

BibTeX reference

The vehicle routing problem with time windows VRPTW consists of finding least-cost vehicle routes to service given customers exactly once each while satisfyi...

BibTeX reference**Jacques Desrosiers**

Dans cet article, on raconte l'histoire de l'équipe GENCOL et du logiciel d'optimisation du même nom. C'est avant tout le récit d'une collaboration qui se po...

BibTeX reference

This paper presents a general framework for formulating cutting planes in the context of column generation for integer programs. Valid inequalities can be de...

BibTeX reference**Jacques Desrosiers**

In-house production or outsourcing are important strategic decisions for planning production and capacity in business organizations. Outsourcing to overseas ...

BibTeX reference**Jacques Desrosiers**

This paper presents an overview of the column generation method developed at the GERAD research center in Montr'eal for solving large scale vehicle routing ...

BibTeX reference

We consider a maritime inventory routing problem in the liquefied natural gas (LNG) business. Here, an actor is responsible for the routing of the fleet of s...

BibTeX reference

Column generation algorithms are instrumental in many areas of applied optimization, where linear programs with an enormous number of columns need to be so...

BibTeX reference**Jacques Desrosiers**and Lila Rasekh

This paper describes a class of large-scale capacity planning problems under uncertainty. The uncertainty can arise in different dimensions of a production...

BibTeX reference**Jacques Desrosiers**

Real-world routing problems are often represented by large and complex models, and instances of realistic size are very hard to solve. In most cases one ca...

BibTeX referencePath Reduced Costs for Eliminating Arcs

In many branch-and-price algorithms, the column generation pricing problem consists of computing feasible paths in a network. In this paper, we show how, in...

BibTeX reference

Earth observation satellites are platforms equipped with optical instruments that orbit the Earth in order to take photographs of specific areas at the requ...

BibTeX reference

Given the sets of flights and aircraft of an airline carrier, the fleet assignment problem consists of assigning the most profitable aircraft type to each f...

BibTeX referenceStabilized Column Generation for Highly Degenerate Multiple-Depot Vehicle Scheduling Problems

Column generation has proven to be efficient in solving the linear programming relaxation of large scale instances of the Multiple-Depot Vehicle Scheduling ...

BibTeX reference

Given the flight schedule of an airline, the fleet assignment problem consists of determining the aircraft type to assign to each flight leg in order to max...

BibTeX reference

Column generation is one of the most successful approaches for solving large scale linear programming problems. However, degeneracy difficulties and long-ta...

BibTeX reference

Column generation has become a powerful tool in solving large scale integer programs. It is well known that most of the often reported compatibility issues ...

BibTeX reference**Jacques Desrosiers**, and François Soumis

The fractional aircraft market is the fastest growing segment of the business aircraft industry. A fractional aircraft operation is complex - essentially an...

BibTeX referenceStabilization in Column Generation

Column Generation (CG) algorithms are instrumental in many areas of applied optimization, where Linear Programs with an enormous number of columns need to ...

BibTeX reference

We describe an approach that computes an optimal primal basic solution given an optimal vector of dual multipliers. It consists in restricting the dual prob...

BibTeX referenceA Primer in Column Generation

**Jacques Desrosiers**and Marco E. Lübbecke

We give a didactic introduction to the use of the column generation technique in linear and in particular in integer programming. We touch on both, the relev...

BibTeX reference**Jacques Desrosiers**

This paper proposes a generalization of the proximal point algorithm using both penalty and trust region concepts. Finite convergence is established while as...

BibTeX referenceDesign of Balanced MBA Student Teams

**Jacques Desrosiers**, Nenad Mladenović, and Daniel Villeneuve

In some schools and universities, students must sometimes be divided into several teams in such a way that each team provides a good representation of the cl...

BibTeX referenceSelected Topics in Column Generation

**Jacques Desrosiers**

Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large scale integer programming. We outline and relate ...

BibTeX referenceAltitude Manpower Planning. An Integrated System that Addresses the Puzzle of Planning a Crew Force

**Jacques Desrosiers**

A critical aspect of operating an airline is to continuously maintain adequate staffing levels of qualified crewmembers. The airline must be able to plan sev...

BibTeX referenceDe professeur/chercheur à entrepreneur

**Jacques Desrosiers**

Le texte qui suit est l'allocution donnée par le professeur Jacques Desrosiers à la Société Royale du Canada, le jeudi 14 novembre 2002, à l'Université du Qu...

BibTeX reference

Although airlines plan aircraft routes and crew schedules in advance, perturbations occur everyday. As a result, flight schedules may become infeasible and ...

BibTeX reference

Assigning locomotives and cars to a set of scheduled trains is a complex but important problem for passenger railways. This task is normally carried out in ...

BibTeX reference**Jacques Desrosiers**

Cet article de vulgarisation donne un bref aperçu des travaux réalisés en gestion des opérations dans les grands réseaux de transport. On y fait principalem...

BibTeX reference

Given a set of flight legs to be flown by a single type of aircraft, the simultaneous aircraft routing and crew scheduling problem consists of determining a...

BibTeX referenceThe VRP with Pickup and Delivery

This paper presents a survey on the <i>Vehicle Routing Problem with Pickup and Delivery</i> in which a heterogeneous vehicle fleet based at multiple termina...

BibTeX referenceThe VRP with Time Windows

This paper presents a survey of the research on the Vehicle Routing Problem with Time Windows (VRPTW), an extension of the Capacitated Vehicle Routing Probl...

BibTeX reference

This paper presents an exact approach for solving the simultaneous vehicle and crew scheduling problem in urban mass transit systems. We consider the single...

BibTeX reference

This paper focuses on accelerating strategies used in conjunction with column generation to solve Vehicle Routing and Crew Scheduling problems. We describ...

BibTeX reference

The problem of assigning locomotives and cars to trains is a complex task for most railways. In this paper, we propose a multi-commodity network flow based ...

BibTeX reference

The problem of assigning locomotives to trains consists of selecting the types and number of engines that minimize the fixed and operational locomotive cost...

BibTeX reference

An important aspect of railway planning concerns the distribution of locomotives and cars in the network and their assignment to the scheduled trains. In th...

BibTeX reference

Cet article décrit un problème d'horaires mensuels personnalisés pour les membres d'équipage (pilotes et officiers) en transport aérien. Ce problème consist...

BibTeX reference

One of the many problems faced by rail transportation companies is to optimize the utilization of the available stock of locomotives and cars. In this paper...

BibTeX referenceStabilized Column Generation

Column generation is often used to solve large scale optimization problems, and much research has been devoted to improve the convergence of the solution pr...

BibTeX reference

This paper addresses the problem of generating valid crew pairings in the context of a regional air carrier. The classical column generation solution appro...

BibTeX reference

The locomotive assignment problem is to provide at minimum cost sufficient motive power to pull all the trains of a time tabled schedule. Optimization metho...

BibTeX reference

This article describes a method for solving the crew rostering problem in air transportation. This problem consists of constructing personalized schedules ...

BibTeX reference

This paper describes the Preferential Bidding Problem solved in the airline industry to construct personalized monthly schedules for pilots and officers. T...

BibTeX reference

We propose a common solution approach for different crew scheduling problems arising at the planning and operational levels in the airline industry. Specifi...

BibTeX reference

This paper introduces a strong valid inequality, the 2-path cut, to produce better lower bounds for the Vehicle Routing Problem with Time Windows (VRPTW). ...

BibTeX referenceA Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems

**Jacques Desrosiers**, Irina Ioachim, Marius M. Solomon, François Soumis, and Daniel Villeneuve

The need for an integrating framework for vehicle routing and crew scheduling problems has been apparent for some time. While several attempts have been ma...

BibTeX reference

This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing pr...

BibTeX reference

We consider a weekly locomotive scheduling problem encountered at Swedish State Railways. The objective is to find cyclic locomotive schedules, which minim...

BibTeX reference

This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. This problem consists of modifyin...

BibTeX reference

La méthode de génération de colonnes est couramment utilisée pour résoudre des problèmes d'optimisation de grande taille. En pratique, on observe fréquemmen...

BibTeX reference

The problem of assigning locomotives to train-segments is very important for railway companies, in view of the high cost of operating locomotives. The prob...

BibTeX reference

This paper presents an optimal dynamic programming algorithm, the first such algorithm in the literature to solve the shortest path problem with time window...

BibTeX referenceCrew Pairing at Air France

**Jacques Desrosiers**, Yvan Dumas, S Marc, B Rioux, Marius M. Solomon, and François Soumis

In the airline industry, crew schedules consist of a number of pairings. These are round trips originating and terminating at the same crew home base compo...

BibTeX reference**Jacques Desrosiers**, Marius M. Solomon, and Daniel Villeneuve

The majority of vehicle routing and crew scheduling problems studied up to date in the literature can be formulated by means of a unified model introduced b...

BibTeX reference

In this paper we consider the daily aircraft routing and scheduling problem (DARSP). It consists of determining daily schedules which maximize the anticipat...

BibTeX reference

We present a recent optimization approach that can be applied equally to aircraft routing, crew pairing generation and bidding/rostering problems arising in...

BibTeX reference

There are several routing and scheduling problems faced by airline companies, notably, aircraft scheduling, pairing generation and crew bidding and rosterin...

BibTeX reference**Jacques Desrosiers**

Crew-Opt is a set-covering method that uses column-generation to produce nearly optimal solutions to crew scheduling problems. We presented this method at t...

BibTeX reference

This survey paper describes the significant advances made in time constrained vehicle routing and crew scheduling problems. In terms of solution methodolog...

BibTeX reference**Jacques Desrosiers**, Yvan Dumas, Marius M. Solomon, and Daniel Villeneuve

This paper examines whether there is a substantial additional payoff to be derived from using mathematical optimization techniques to globally define a set ...

BibTeX referenceA New Branching Strategy for Time Constrained Routing Problems with Application to Backhauling

**Jacques Desrosiers**, and Marius M. Solomon

In this paper we explore a new branching strategy for branch-and-bound approaches based on column generation for the vehicle routing problems with time wind...

BibTeX reference

We propose a new branch-and-bound algorithm for the Satisfiability problem (SAT). A relaxation as well as a decomposition scheme are defined by using polyno...

BibTeX reference

This paper presents the development of a new optimal dynamic programming algorithm for the minimization of the total traveling cost for the traveling salesm...

BibTeX reference

We present a new two-commodity flow formulation for the traveling salesman problem. Each commodity corresponds to a resource that is either distributed or p...

BibTeX reference**Jacques Desrosiers**, Yvan Dumas, Martin Desrochers, François Soumis, Brunilde Sansò, and Pierre Trudeau

The Airline Crew Scheduling Problem can be defined as the problem of finding a set of feasible rotations so that the total cost is minimum and all the fligh...

BibTeX reference

In many cities around the world, public transportation services are requested to provide adapted transportation for handicapped persons and people with rest...

BibTeX reference**Jacques Desrosiers**, and Marius M. Solomon

The vehicle routing problem with time windows (VRPTW) is a generalization of the vehicle routing problem where the service of a customer can begin within th...

BibTeX reference**Jacques Desrosiers**, and J Boisvert

Because of the transmission of disease producing parasites to man and animals and the nuisance caused by bites from adult black flies, they are the object o...

BibTeX reference**Jacques Desrosiers**, and Marius M. Solomon

The vehicle routing problem (VRP) involves the design of a set of minimum cost routes, originating and terminating at a central depot, for a fleet of vehicl...

BibTeX reference

The vehicle routing problem (VRP) involves the design of a set of minimum cost routes for a fleet of vehicles which services exactly once a set of customers...

BibTeX reference

The multiple vehicle many-to-many routing problem is presented in the context of a dial-a-ride system. It is solved by mini-clustering first and optimal ro...

BibTeX reference

We present an algorithm that solves the problem of finding the vehicle schedule which minimizes total inconveniences for travel along a fixed path, where se...

BibTeX reference

Several single-commodity, two-commodity and multi-commodity flow formulations have recently been introduced for the travelling salesman problem. The purpose...

BibTeX referenceMinimisation d'une fonction convexe séparable avec contraintes de rapport entre les variables

We present a dual algorithm to minimize a separable convex function under ratio constraints between variables. This minimization problem occurs when the dep...

BibTeX reference

We present an algorithm that solve the problem of finding the best vehicle time schedule (minimizing total inconveniences) for a fixed path, knowing that vis...

BibTeX reference**Jacques Desrosiers**

This paper presents mathematical formulations for some vehicle routing and scheduling problems with time window constraints and the optimal solution approach...

BibTeX reference**Jacques Desrosiers**

Recently we have witnessed the development of a fast growing body of research focused on vehicle routing and scheduling problem structures with time window c...

BibTeX referenceVehicle Routing with Full Loads

This paper considers a vehicle routing problem with full loads and time limit constraints. This problem can be formulated as an asymmetrical travelling sale...

BibTeX reference**Jacques Desrosiers**

This article examines a constrained shortest path problem which occurs in the design by column generation of vehicle routes constructed to satisfy a set of t...

BibTeX reference

The single-vehicle dial-a-ride problem with time window constraints for both pick-up and delivery locations, and precedence and capacity constraints, is solv...

BibTeX reference**Jacques Desrosiers**

Cet article traite d'un problème de plus court chemin sous contraintes. Il s'agit du chemin d'un véhicule complétant un sous-ensemble de demandes de transpo...

BibTeX reference

This paper presents some preliminary results from an ongoing study of the impact of various operating scenarios on the construction and quality of reoutes in...

BibTeX reference**Jacques Desrosiers**

L'objectif de l'étude est d'évaluer l'impact sur les choix résidentiels de certains changements structurels tels les modifications dans la composition de la ...

BibTeX reference

In this article, we examine the use of Lagrangian relaxation to obtain a lower bound on the minimum fleet size for the m-TSP with time window constraints on ...

BibTeX reference

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 tr...

BibTeX reference

Bus fleet route planning is often carried out in the following two sequential stages:<br> 1) Based on the demand, determine the trips to be carried out.<br>...

BibTeX reference**Jacques Desrosiers**

In this article, two Lagrangean relaxations for the vehicle routing problem with time windeow constraints are examined. In the first case, the scheduling co...

BibTeX reference**Jacques Desrosiers**and Alain Lapointe

Les modèles développés jusqu'à maintenant dans le domaine urbain, que ce soient les modèles économétriques ou encore les modèles déterministes de simulation,...

BibTeX reference

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 tr...

BibTeX reference

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 tr...

BibTeX reference

Le problème considère un ensemble de parcours ayant chacun un lieu de début, un lieu de fin, une durée, un coût et un intervalle de temps pendant lequel ils ...

BibTeX reference**Jacques Desrosiers**and François Soumis

Le service de transport des handicapés vise à procurer un transport à toute personne handicapée incapable d'utiliser le service de transport urbain régulier....

BibTeX reference**Jacques Desrosiers**and Paul Pelletier

Le problème classique de l'industrie du papier consiste à générer un programme de coupe de façon à satisfaire les demandes des clients, tout en minimisant le...

BibTeX reference### Articles

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**, and Marco E. Lübbecke

**Jacques Desrosiers**, and Jean-Bertrand Gauthier

**Jacques Desrosiers**, and Marco E. Lübbecke

**Jacques Desrosiers**, and Marco E. Lübbecke

**Jacques Desrosiers**, and Marco E. Lübbecke

**Jacques Desrosiers**, Thibaut Vidal, and Bruno Salezze Vieira

**Jacques Desrosiers**, and Marco E. Lübbecke

**Jacques Desrosiers**, and François Soumis

**Jacques Desrosiers**, Jean-Bertrand Gauthier, and Marco E. Lübbecke

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**, and Simon Spoorendonk

**Jacques Desrosiers**and Lila Rasekh

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**, and Ahmed Hadjar

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**, Gilbert Laporte, and Vincent Raymond

**Jacques Desrosiers**, and Hatem Ben Amor

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**, and José Manuel Valério de Carvalho

**Jacques Desrosiers**, and François Soumis

**Jacques Desrosiers**

**Jacques Desrosiers**, Nenad Mladenović, and Daniel Villeneuve

**Jacques Desrosiers**, and June Lavigne

**Jacques Desrosiers**

**Jacques Desrosiers**, Marco E. Lübbecke, and François Soumis

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**, Yvan Dumas, S Marc, B Rioux, Marius M. Solomon, and François Soumis

**Jacques Desrosiers**, and Marius M. Solomon

**Jacques Desrosiers**, Pierre Girard, and Marius M. Solomon

**Jacques Desrosiers**, and Marius M. Solomon

**Jacques Desrosiers**, and François Soumis

### Books

**Jacques Desrosiers**, and Marius M. Solomon

### Book chapters

**Jacques Desrosiers**and Marco E. Lübbecke

**Jacques Desrosiers**, and Simon Spoorendonk

**Jacques Desrosiers**

**Jacques Desrosiers**

**Jacques Desrosiers**and Marco E. Lübbecke