Integer (linear) programs are a standard way of formalizing a vast array of optimization problems in industry, services, management, science, and technology....

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

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

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

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

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

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

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

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

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

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

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

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

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^-30 in sing...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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