Jacques Desrosiers
RetourPublications
Cahiers du GERAD
Branch-and-Price
Integer (linear) programs are a standard way of formalizing a vast array of optimization problems in industry, services, management, science, and technology....
référence BibTeX
Cet article présente les propriétés de l'algorithme MMCC (minimum mean cycle-canceling) pour la résolution de programmes linéaires. Initialement conçu ...
référence BibTeX
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...
référence BibTeX
This paper describes a vector space decomposition algorithmic framework for linear programming guided by dual feasibility considerations. The resolution pro...
référence BibTeX
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 ...
référence BibTeX
This paper describes three recent tools for dealing with primal degeneracy in linear programming. The first one is the Improved Primal Simplex (IPS) algor...
référence BibTeX
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...
référence BibTeX
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....
référence BibTeX
Onshore oil fields may contain hundreds of wells that use sophisticated and complex equipments. These equipments need maintenance regularly to keep the...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
Dynamic constraint aggregation (DCA) and dual variable stabilization (DVS) are two methods that can reduce the negative impact of degeneracy when solvi...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
Column generation for solving linear programs with a huge number of variables alternately solves a (restricted) master problem and a pricing subproblem to ad...
référence BibTeXPositive 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...
référence BibTeX
In this paper, we generalize the Asymmetric Representatives Formulation, which was first introduced by Campêlo et al. (2008) for the Node Coloring Problem. ...
référence BibTeX
The vehicle routing problem with time windows VRPTW consists of finding least-cost vehicle routes to service given customers exactly once each while satisfyi...
référence BibTeX
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...
référence BibTeX
This paper presents a general framework for formulating cutting planes in the context of column generation for integer programs. Valid inequalities can be de...
référence BibTeX
In-house production or outsourcing are important strategic decisions for planning production and capacity in business organizations. Outsourcing to overseas ...
référence BibTeX
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 ...
référence BibTeX
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...
référence BibTeX
Column generation algorithms are instrumental in many areas of applied optimization, where linear programs with an enormous number of columns need to be so...
référence BibTeX
This paper describes a class of large-scale capacity planning problems under uncertainty. The uncertainty can arise in different dimensions of a production...
référence BibTeX
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...
référence BibTeXPath 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...
référence BibTeX
Earth observation satellites are platforms equipped with optical instruments that orbit the Earth in order to take photographs of specific areas at the requ...
référence BibTeX
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...
référence BibTeXStabilized 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 ...
référence BibTeX
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...
référence BibTeX
Column generation is one of the most successful approaches for solving large scale linear programming problems. However, degeneracy difficulties and long-ta...
référence BibTeX
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 ...
référence BibTeX
The fractional aircraft market is the fastest growing segment of the business aircraft industry. A fractional aircraft operation is complex - essentially an...
référence BibTeXStabilization 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 ...
référence BibTeX
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...
référence BibTeXA Primer in Column Generation
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...
référence BibTeX
This paper proposes a generalization of the proximal point algorithm using both penalty and trust region concepts. Finite convergence is established while as...
référence BibTeXDesign of Balanced MBA Student Teams
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...
référence BibTeXSelected Topics in Column Generation
Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large scale integer programming. We outline and relate ...
référence BibTeXAltitude Manpower Planning. An Integrated System that Addresses the Puzzle of Planning a Crew Force
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...
référence BibTeXDe professeur/chercheur à entrepreneur
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...
référence BibTeX
Although airlines plan aircraft routes and crew schedules in advance, perturbations occur everyday. As a result, flight schedules may become infeasible and ...
référence BibTeX
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 ...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeXThe 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...
référence BibTeXThe 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...
référence BibTeX
This paper presents an exact approach for solving the simultaneous vehicle and crew scheduling problem in urban mass transit systems. We consider the single...
référence BibTeX
This paper focuses on accelerating strategies used in conjunction with column generation to solve Vehicle Routing and Crew Scheduling problems. We describ...
référence BibTeX
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 ...
référence BibTeX
The problem of assigning locomotives to trains consists of selecting the types and number of engines that minimize the fixed and operational locomotive cost...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeXStabilized 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...
référence BibTeX
This paper addresses the problem of generating valid crew pairings in the context of a regional air carrier. The classical column generation solution appro...
référence BibTeX
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...
référence BibTeX
This article describes a method for solving the crew rostering problem in air transportation. This problem consists of constructing personalized schedules ...
référence BibTeX
This paper describes the Preferential Bidding Problem solved in the airline industry to construct personalized monthly schedules for pilots and officers. T...
référence BibTeX
We propose a common solution approach for different crew scheduling problems arising at the planning and operational levels in the airline industry. Specifi...
référence BibTeX
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). ...
référence BibTeXA Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems
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...
référence BibTeX
This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing pr...
référence BibTeX
We consider a weekly locomotive scheduling problem encountered at Swedish State Railways. The objective is to find cyclic locomotive schedules, which minim...
référence BibTeX
This paper describes the operational airline crew scheduling problem and represents a first published attempt to solve it. This problem consists of modifyin...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
This paper presents an optimal dynamic programming algorithm, the first such algorithm in the literature to solve the shortest path problem with time window...
référence BibTeXCrew Pairing at Air France
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...
référence BibTeX
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...
référence BibTeX
In this paper we consider the daily aircraft routing and scheduling problem (DARSP). It consists of determining daily schedules which maximize the anticipat...
référence BibTeX
We present a recent optimization approach that can be applied equally to aircraft routing, crew pairing generation and bidding/rostering problems arising in...
référence BibTeX
There are several routing and scheduling problems faced by airline companies, notably, aircraft scheduling, pairing generation and crew bidding and rosterin...
référence BibTeX
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...
référence BibTeX
This survey paper describes the significant advances made in time constrained vehicle routing and crew scheduling problems. In terms of solution methodolog...
référence BibTeX
This paper examines whether there is a substantial additional payoff to be derived from using mathematical optimization techniques to globally define a set ...
référence BibTeXA New Branching Strategy for Time Constrained Routing Problems with Application to Backhauling
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...
référence BibTeX
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...
référence BibTeX
This paper presents the development of a new optimal dynamic programming algorithm for the minimization of the total traveling cost for the traveling salesm...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
In many cities around the world, public transportation services are requested to provide adapted transportation for handicapped persons and people with rest...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
Several single-commodity, two-commodity and multi-commodity flow formulations have recently been introduced for the travelling salesman problem. The purpose...
référence BibTeXMinimisation 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...
référence BibTeX
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...
référence BibTeX
This paper presents mathematical formulations for some vehicle routing and scheduling problems with time window constraints and the optimal solution approach...
référence BibTeX
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...
référence BibTeXVehicle 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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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 ...
référence BibTeX
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 ...
référence BibTeX
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...
référence BibTeX
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>...
référence BibTeX
In this article, two Lagrangean relaxations for the vehicle routing problem with time windeow constraints are examined. In the first case, the scheduling co...
référence BibTeX
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,...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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 ...
référence BibTeX
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....
référence BibTeX
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...
référence BibTeX