Constraint Programming Based Column Generation for Crew Assignment

Abstract

Airline crew assignment problems are large-scale optimization problems which can be adequately solved by column generation. The subproblem is typically a so-called constrained shortest path problem and solved by dynamic programming. However, complex airline regulations arising frequently in European airlines cannot be expressed entirely in this framework and limit the use of pure column generation. In this paper, we formulate the subproblem as a constraint satisfaction problem, thus gaining high expressiveness. Each airline regulation is encoded by one or several constraints. An additional constraint which encapsulates a shortest path algorithm for generating columns with negative reduced costs is introduced. This constraint reduces the search space of the subproblem significantly. Resulting domain reductions are propagated to the other constraints which additionally reduces the search space. Numerical results based on data of a large European airline are presented and demonstrate the potential of our approach. [PUBLICATION ABSTRACT]

*u*n*s*t*u*r*t*u*r*e**t*e*x*t*

Journal of Heuristics, 8: 59-81, 2002 c\Theta 2002 Kluwer Academic Publishers. Manufactured in The Netherlands.

Constraint Programming Based Column Generationfor Crew Assignment* TORSTEN FAHLE University of Paderborn, Department of Mathematics and Computer Science, F"urstenallee 11, D-33102 Paderborn, Germany email: [email protected]

ULRICH JUNKER ILOG S.A., 1681, route des Dolines, F-06560 Valbonne, France email: [email protected]

STEFAN E. KARISCH Carmen Systems Ltd., 1800 McGill College Avenue, Suite 2800 Montreal, Quebec H3A 3J6, Canada email: [email protected]

NIKLAS KOHL Carmen Consulting, Fruebjergvej 3, 2100 Copenhagen O/, Denmark email: [email protected]

MEINOLF SELLMANN University of Paderborn, Department of Mathematics and Computer Science, F"urstenallee 11, D-33102 Paderborn, Germany email: [email protected]

BO VAABEN Carmen Consulting, Fruebjergvej 3, 2100 Copenhagen O/, Denmark email: [email protected]

Abstract Airline crew assignment problems are large-scale optimization problems which can be adequately solved by column generation. The subproblem is typically a so-called constrained shortest path problem and solved by dynamic programming. However, complex airline regulations arising frequently in European airlines cannot be expressed entirely in this framework and limit the use of pure column generation. In this paper, we formulate the subproblem as a constraint satisfaction problem, thus gaining high expressiveness. Each airline regulation is encoded by one or several constraints. An additional constraint which encapsulates a shortest path algorithm for generating columns with negative reduced costs is introduced. This constraint reduces the search space of the subproblem significantly. Resulting domain reductions are propagated to the other constraints which additionally

*The production of this paper was supported by the PARROT project, partially funded by the ESPRIT programme of the Commission of the European Union as project number 24 960. The partners in the project are ILOG (F), Lufthansa Systems (D), Carmen Systems (S), Olympic Airways (GR), University of Paderborn (D), and University of Athens (GR). This paper reflects the opinions of the authors and not necessarily those of the consortium.

60 FAHLE ET AL. reduces the search space. Numerical results based on data of a large European airline are presented and demonstrate the potential of our approach.

Key Words: airline crew assignment, constraint satisfaction, column generation, shortest path constraint, hybrid OR/CP methods

1. Introduction 1.1. The crew assignment problem Routing and scheduling of crews and equipment in large public transportation networks such as airlines, railways, and bus companies has been a major field for optimization for a long time. Different planning problems such as fleet assignment, aircraft routing, and crew scheduling have been addressed by numerous research papers. A recent book of Yu (1998) and the article of Rushmeier, Hoffmann, and Padberg (1995) give examples of problems and solution approaches in the airline industry.

In the airline crew scheduling problem a set of basic activities or tasks1--typically, to fly an aircraft from A to B--has to be assigned to a set of crew members such that all basic activities are covered. Additionally, complex rules and regulations coming from legislation and contractual agreements have to be met by the solutions. Different objectives like minimizing overall costs and maximizing crew satisfaction are of interest. The latter objective is chosen in so-called preferential bidding systems where crew members are allowed to express their likes and dislikes for certain activities (see, e.g., Gamache et al., 1998).

In larger airlines the crew scheduling problem is decomposed into a crew pairing and a crew assignment (or rostering) problem. In the crew pairing problem the basic activities, flight legs (flight without stopover), are grouped into so-called pairings. A pairing is a sequence of flight legs usually starting and ending at the same home base and is considered one single "piece" of work. A pairing corresponds to one or more days of work and will be assigned as a whole to one or more named individuals. However, in the crew pairing problem the pairings remain anonymous. Pairings have to respect certain rules, e.g., connection time between flight legs and rest time between duty days. The crew pairing problem has been studied by several authors (see, e.g., Andersson et al., 1998; Barnhart and Shenoi, 1998; Chu, Gelman, and Johnson, 1997; Desaulniers et al., 1997).

The topic of this paper is the crew assignment problem (CAP). In the CAP the pairings together with other activities such as ground duties, reserve duties, and off-duty blocks must be assigned to named individuals. The outcome of this is a so-called roster for each crew member. Rosters must respect rules and regulations additionally to those considered in the pairing problem. These rules can be classified into single crew member rules and multiple crew member rules. The rules of the first class only influence the legality of a single roster, whereas those of the second class express regulations on combinations of rosters or crew members. Crew assignment is considered to be a large scale optimization problem, as in practice several thousand pairings and other activities have to be assigned to hundreds or possibly even thousands of crew members. The number of rules and regulations which must be respected can be up to one hundred and the number of possible rosters is gigantic.

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 61 1.2. Current solution methods To our knowledge, all published work on the airline CAP follows the idea of generate-andoptimize or column generation, see Gamache et al. (1998), Day and Ryan (1997), and Ryan (1992) for examples. The problem is divided into a subproblem where a subset of all legal rosters is generated, and a master problem where some of these rosters, one for each crew member, are selected. The master problem is a linear integer program whereas the structure of the subproblem is dependent on the rules, regulations, and objectives of the underlying CAP. Usually, one iterates between the master problem and the subproblem, thus gradually improving the solution quality.

The generation of legal rosters in the subproblem is either done by partial enumeration based on propagation and pruning techniques (Kohl and Karisch, 1999) or by solving a resource constrained shortest path problem where the constraints ensure that only legal rosters are generated. The objective function measures the reduced costs of the roster with respect to the solution of the continuous relaxation of the master problem defined on the previously generated rosters (Gamache et al., 1998). The latter approach is known as resource constrained shortest path column generation. In this approach, the subproblem can be solved optimally and one can prove that it is possible to obtain the optimal solution to the entire (relaxed) problem without explicit enumeration of all possible rosters.

Resource constrained shortest path column generation is a very powerful technique but it is only useful if rules, regulations and objectives satisfy certain properties (see Desrosiers et al., 1995, for an overview), whereas propagation and pruning techniques do not depend on particular assumptions on the problem.

Several alternative approaches have been proposed for solving the railway CAP, which differs slightly from the airline crew assignment, but also has to model rules and regulations. Caprara et al. (1998b) gave an algorithm that uses information from a Lagrangean lower bound based on the solution of an assignment problem to guide a heuristic. Their algorithm won the first prize in a competition organized by the Italian Railway Company. For the Lisbon Underground, Cavique, Rego, and Themido (1999) used a tabu search procedure working on the entire solution. The contractual and operational rules in this case consist mainly of time limits for minimum/maximum work time and for meal breaks.

For the approach presented here, the work of Caprara et al. (1998a) is of certain interest. Their approach is mainly based on the constraint logic programming (CLP) paradigm enhanced with a lower bounding procedure taken from the operations research field. This is the natural choice since good and fast bounding procedures were available from (Caprara et al., 1998a). The efficiency of the approach is supposed to be due to the existence of these bounding procedures for the case considered. Thus, a generalization to the generic airline CAP considered in this paper is not straightforward.

1.3. Integration of CP and OR techniques The integration of techniques from Constraint Programming (CP) and Operations Research (OR) has become an important field of research in recent years, see Hooker (1999) for an overview. The integration of OR and CP techniques applied to airline CAP is investigated

62 FAHLE ET AL. in the ESPRIT project PARROT (Parallel Crew Rostering) (1997) where this work has been carried out. In principle there are two main ways of integrating CP and OR:

* Embed OR algorithms in a CP framework. Beringer and De Backer (1995), Bockmayr and

Kasper (1998) and Rodosek, Wallace, and Haijan (1999) did this for a linear solver. The purpose of the OR algorithm is usually to provide bounds and possibly other information to guide the search. In certain cases, OR algorithms can also be exploited for domain reduction. A famous example are global resource constraints in scheduling that use the edge-finder (Nuijten and Aarts, 1996).* Embed CP algorithms in an OR framework. This is done in the context of a column generation algorithm. The master (OR) problem is a linear integer program and the difficult constraints are "hidden" in the column generating subproblem which is solved by CP.

This paper elaborates the latter approach. In our column generating subproblem we take advantage of the powerful modeling and solving abilities of CP for rules and regulations arising from a possibly non-linear world. For the master problem we use OR techniques.

An important result from the column generation (OR) theory says that new columns can improve the current solution to the continuous relaxation of the master problem, only if their reduced cost with respect to the current continuous solution is strictly negative. The major theoretical novelty of our work is to show how this result can be exploited efficiently by the CP algorithm applied to the subproblem. We do this by introducing a shortest path constraint and a negative reduced cost constraint allowing us to dynamically reduce domains in the subproblem using dual information from the master problem.

Compared to traditional approaches of generating columns, the CP framework combines a high expressiveness with the domain reduction capabilities of CP algorithms. In particular, the CP framework allows to encapsulate traditional generation techniques (e.g. sophisticated constrained shortest-path algorithms) inside a constraint and to exploit them for domain reduction. Constraints that cannot be treated by the shortest-path algorithm can now interact with it via domain reduction. We can also say that the additional constraints will cut illegal choices of the shortest-path algorithm as early as possible when searching for best columns. Thus, constraint programming based column generation can be seen as a way of enhancing or extending traditional approaches to column generation.

1.4. The airline test case For our experiments, we use data for several 4 week planning periods of Spring and Summer 1998 from a major European airline. The problem instances consider cockpit crew at one crew base and consist of around 400 crew members and around 1000 activities which have to be assigned.

For the crew assignment, the airline is interested in fair rosters which minimize overall costs. The costs are represented by a linear objective function on the rosters and the unassigned activities. The main costs of each roster depend on the total flight time (or block time) and costs on extra days off.

In the production system of that airline, around 90 single crew member rules are implemented. Representative subsets of rules and regulations have been chosen for our

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 63 experiments. However, certain issues such as individual rule relaxations or restrictions are not considered.

The following lists seven rules which have been implemented for the test case presented in this paper. The formulations of some rules use the term airline day which is a 24 hours period not corresponding to a calendar day. It starts at time \Theta on one day and ends one minute before \Theta on the next day.

(R1) Minimum Rest at Home Base: A crew member gets at least an \Lambda 1-hour rest period at

his/her home base between two activities. (R2) Minimum Rest for One Day Off: If a crew member has one complete airline day off,

i.e., the rest between two activities contains one airline day, the rest period must be at least \Lambda 2 hours. (R3) Minimum Rest for Two Days Off: If a crew member has two complete airline days

off, i.e., the rest between two activities contains two airline days, the rest period must be at least \Lambda 3 hours. (R4) Minimum Rest for Three Days Off: If a crew member has three complete airline days

off, i.e., the rest between two activities contains three airline days, the rest period must be at least \Lambda 4 hours. (R5) Latest Check-out for Two Days Off: If an activity is followed by a rest period containing

two airline days, the activity is not allowed to end in a night period, i.e., the period defined by an interval [\Theta 1, \Theta 2]. (R6) No Early Briefing After Five/Two: After a 5-day working period followed by two

airline days off, a crew member cannot be assigned an activity starting before time \Theta 3. (R7) No two trips on the same day: Except for preassignments, it is not allowed to have

two flight trips on the same day.

Additionally, crew members are required to have special activities like simulator training, medical checks, etc. during the planing period under consideration. These activities usually require interaction with resources that are not necessarily known in the planning system (e.g., slots for the simulator, medical personal, etc.). Therefore, in the present work they are not handled as special rules but simply by assigning these activities to a crew member in advance. We refer to these activities as preassignments.

Note, that due to the generic approach based on CP, the rule set can easily be extended and modified without significantly changing the algorithms described in the following sections.

1.5. Outline The paper is organized as follows. The next two sections present the column generation approach for the CAP. In Section 2 we concentrate on the subproblem, especially we describe the new shortest path and the negative reduced cost constraint. The remaining components of the approach are introduced in Section 3. In Section 4 the new approach is applied to some airline crew assignment problems coming from a major European airline and numerical results are presented. Finally, we conclude in Section 5.

64 FAHLE ET AL. 2. A CP based column generation approach 2.1. Column generation Column generation (also called Dantzig-Wolfe decomposition) is a well-known technique for handling linear programs (LPs) with a huge amount of variables:

min cx, s.t. Ax = b (1) Its origins date back to the works of Dantzig and Wolfe (1961) and Gilmore and Gomory (1961). The latter paper applies column generation to the classical cutting stock problem where the subproblem is a knapsack problem. More recent applications include specially structured integer programs such as the generalized assignment problem and time constrained vehicle routing, crew pairing, crew assignment and related problems. We refer to Desrosiers et al. (1995) for a survey.

Due to its size it is often impossible to solve the large system (1) directly. Column generation provides a way for obtaining the solution of this system indirectly. Therefore, a much smaller system A\Sigma x = b is considered where A\Sigma contains only few columns of A. An optimal basic solution of the restricted master problem A\Sigma x = b provides dual values \Sigma i of each constraint i of the linear system.

Now we pose the question: Which columns have to be added to A\Sigma yielding a linear system with the same solution value as the original problem (1)? Linear programming duality theory tells us that only columns with negative reduced cost can be candidates for entering the basis. This is the way the simplex algorithm chooses columns for its basis internally. But it can also be applied for the external generation of columns. Similar to the simplex algorithm, column generation can be stopped as soon as no further columns with negative reduced costs exist. Therefore, in the subproblem of column generation it is sufficient to search only for a column \Upsilon := (\Upsilon 1, . . . , \Upsilon z)T that obeys the negative reduced cost inequality

c\Upsilon -

z\Theta

i=1

\Sigma i * \Upsilon i < 0 (2)

where c\Upsilon denotes the cost coefficient for column \Upsilon . \Upsilon then is added to A\Sigma .

Theoretically, it may still be necessary to generate all possible columns before terminating the generation phase but in practice this rarely happens. Typically, only a small subset of all possible columns will be needed. Algorithm 1 describes this idea. There, we assume that function solveSubproblem() returns new columns {\Upsilon (1), . . . , \Upsilon (k)} which are valid solutions for the subproblem, or an empty set, if no more solutions respecting Eq. (2) exist. An initial matrix A\Sigma is returned by getInitialColumns(). solveLP() solves the LP given by

A\Sigma x = b and returns the corresponding dual values \Sigma . Function addColumnsToMatrix() extends A\Sigma by the columns generated.

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 65 Algorithm 1 Outline of the Column Generation

A\Sigma :=getInitialColumns() repeat

\Sigma := solveLP(A\Sigma )//get new duals{

\Upsilon (1), . . . , \Upsilon (k)} := solveSubproblem(\Sigma )//solve subproblem, respecting Eq. (2) addColumnsToMatrix(A\Sigma , \Upsilon (1), . . . , \Upsilon (k) ) until ({\Upsilon (1), . . . , \Upsilon (k)} = ff)

For linear integer programs (IP) like the one presented in this work, however, column generation may not find the optimal solution as linear programming duality theory is not valid for IPs. In this case, two general approaches are possible.

The first approach is to ignore that fact: One solves the continuous relaxation of the problem first, and then applies branch-and-bound to obtain an integer solution. For a range of IP problems it is known that the remaining gap between LP and IP solution value is small enough to be neglected. We use a variant of this approach which will be described in Section 3.3.

Another possibility is to use branch-and-price where columns are generated in the nodes of a branch-and-bound tree and optimality can be proven. We refer to Barnhart et al. (1998) for further information on this topic.

For the column generation approach used in this work, we decompose the CAP into a subproblem, where legal rosters that obey Eq. (2) are generated, and a set partitioning master problem ensuring that all activities are assigned exactly once.

2.2. The subproblem In this section, we present the subproblem of our column generation approach.

For each crew member we generate a set of rosters. A roster for crew member c is a set of activities Y that contains the chosen and possibly preassigned activities P of the crew member and that satisfies all single crew member rules. Each generated roster leads to the introduction of a new column in the master problem. For this purpose, we need the cost coefficient cY that is defined by this roster, as well as the coefficients ai,Y for each constraint of the master problem. These coefficients are uniquely defined by a roster and will be calculated when generating the roster. They also allow to check Eq. (2) and to generate only rosters with negative reduced costs.

The subproblem for each crew member consists of generating a set of rosters. For each roster we have to find a set Y of activities, a cost coefficient cY , and the coefficient ai,Y for the master constraint such that the following conditions are satisfied:

1. P fi Y fi T , where T is the set of all tasks that have to be assigned, 2. Y satisfies the single crew member rules, and 3. cY - \Lambda i \Sigma i * ai,Y < 0.

66 FAHLE ET AL.

In the following, we introduce a constraint programming approach in Section 2.3 and show how costs and reduced costs can be determined by finding a path in a graph (Section 2.4). We introduce and show how to encode the reduced cost constraint in this approach (Section 2.5). In order to obtain a powerful propagation, we additionally exploit the path-finding algorithm and encapsulate it in a path constraint (Section 2.6). Section 2.7 shows how the propagations of this constraint can be computed efficiently in linear time. Since the path finding approach alone does not take into account all airline rules, we introduce these additional constraints into the constraint model in Section 2.8. Finally, Section 2.9 presents some search heuristics for solving the subproblem.

2.3. Formulation as a CSP In this section, we formulate the subproblem as a constraint satisfaction problem (CSP) (see Mackworth, 1977; Montanari, 1974) allowing us to express complex airline rules and regulations.

A CSP is specified by a set of variables and a set of constraints. Each variable x has an initial domain D(x). This domain can be, for example, an interval of integers. A constraint consists of a tuple of variables (x1, . . . , xn) and an n-ary relation R which is a subset of

D(x1) * * * * * D(xn). A solution of a CSP is an assignment of a value v(x) ffi D(x) to each variable x of the CSP such that all the constraints of the CSP are satisfied. A constraint with variables (x1, . . . , xn) and relation R is satisfied by a solution iff the tuple (v(x1), . . . , v(xn)) is in R.

When defining a specific constraint with variables (x1, . . . , xn) we define the relation of this constraint as the set of all tuples ( _x1, . . . , _xn) satisfying a given condition C( _x1, . . . , _xn). Thus, _x is used to denote the value of x in the considered tuple.

CSPs are usually solved by applying domain reduction techniques. Each variable has a current domain dom(x) that is initialized by D(x). If x is an integer variable, we denote the smallest element of dom(x) by min(x) and the largest element by max(x). We also call them the lower and upper bounds for x.

Each constraint has an associated domain reduction algorithm that tries to remove inconsistent values from the domains of its variables. An overall propagation algorithm propagates these domain changes among the constraints and iterates until no further constraint can reduce the domains (Van Hentenryck, Deville, and Teng, 1992). In order to find a solution, domain reduction alone is not sufficient and a search mechanism is used additionally. Search decisions cause additional domain reductions by invoking the propagation algorithm. The alternative search decisions lead to a search tree that is usually explored by chronological backtracking.2

Dead-ends (failures) in the search are obtained, if the current domain of a variable becomes empty, whereas a solution is found, if all variables are instantiated, i.e., they have exactly one element in their current domain.

For the problem of roster generation, we do not only use integer variables but also set variables. The value of a set variable is a set of integers selected from an initially given domain. The current domain of a set variable is defined by a lower and an upper bound, which are also called required set req(Y ) and possible set pos(Y ). The value of the set

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 67 variable has to be a superset of req(Y ) and a subset of pos(Y ). Set variables replace an array of boolean variables. They lead to more compact constraint models and more efficient and powerful propagation algorithms.

For the roster generation problem of crew member c, we introduce a single set variable Y denoting the (unknown) set of tasks of c. The value of Y has to be a subset of the set of tasks T . Initially, the possible set pos(Y ) contains all tasks and the required set req(Y ) contains all preassigned tasks of the crew member. During roster generation, the required set contains all tasks that have already been assigned to the considered crew member, whereas the possible set contains activities that are still candidates to be assigned. Constraint propagation and search decisions will then remove tasks from the possible set or assign new tasks by adding them to the required set. If the required set is equal to the possible set, the set variable is bound and a solution has been found.

Most rules and regulations require the introduction of further constrained variables. For example, for ensuring a minimal rest time after a given number of days off we introduce a constrained integer variable di for each task ti that represents the number of days off directly after this task.

We now give a small example illustrating effects of domain reduction during roster generation. Consider the set variable Y of a crew member c and suppose that its possible set pos(Y ) initially contains the four tasks t1, t2, t3, t4 satisfying following properties:

0 <= start(t2) - end(t1) < \Lambda 1 1 day <= start(t3) - end(t1) < \Lambda 2

\Lambda 2 <= start(t4) - end(t1)

(3)

If crew member c has no preassigned tasks then the required set req(Y ) is empty initially. Now we start the roster generation procedure which explores different search decisions. For example, it assigns task t1 to crew member c by adding it to req(Y ). This search decision leads to following domain reductions, which are all executed before another search decision is made.

1. Since t1 is in req(Y ) and the rest between t1 and t2 is smaller than the minimal rest time

\Lambda 1, the minimal rest time rule removes t2 from pos(Y ). 2. The earliest task that can follow t1 is now t3. Since the rest time between these tasks is

greater than 1 day the lower bound min(d1) of the variable d1 representing the number of days off after t1 is set to 1. 3. Since the rest time between t1 and t3 is smaller than the minimal rest time \Lambda 2 after 1 day

off, the minimal rest time rule for 1 day off removes t3 from pos(Y ).

Table 1 summarizes these domain reductions.

Table 1. Domain reductions after an assignment.

Initial domain Add t1 to Y Reduced domains req(Y ) ff {t1} {t1}

pos(Y ) {t1, t2, t3, t4} {t1, t2, t3, t4} {t1, t4}

68 FAHLE ET AL. 2.4. Shortest path problems So far, we have not discussed how to calculate the coefficients cY and ai,Y (as introduced in Section 2.2). In CAPs, the cost cY of a roster is often determined by an additive cost function, and in cases where the cost is not completely additive, an additive function will usually be a good approximation. Furthermore, the dominating terms in Eq. (2) tend to be those associated with the \Sigma coefficients, as there is a strong feasibility component in the problem. These terms are always additive. For each task t selected in Y , we obtain a cost ct and the resulting cost of the roster is the sum of the ct 's of all selected tasks. The cost ct does not only depend on task t, but also on the next task t\Sigma . For example, ct can depend on the rest time after t which depends on the arrival time of t and the departure time of t\Sigma . In the following, we assume that roster costs are in fact defined by a sum of task costs ct which depend on the selected tasks t and their successors t\Sigma (but not on any other tasks).

Due to this assumption, we can model the problem of finding a cheapest set of tasks by the problem of finding a shortest path in a weighted graph G = (V, E). The nodes of the graph are the tasks plus an additional source s and an additional sink s\Sigma .

V = T j {s, s\Sigma } (4) If task t\Sigma has a start time start(t\Sigma ) that is greater than the end time end(t) of task t we introduce an edge (t, t\Sigma ). Furthermore, we introduce an edge from the source s to any task t and an edge from any task t to the sink s\Sigma :

E = {(t, t\Sigma ) ffi T * T | end(t) <= start(t\Sigma )} j {(s, t), (t, s\Sigma ) | t ffi T } (5) Hence, the graph G is a directed acyclic graph and if we order the tasks in T by increasing start time we obtain a topological order s, t1, . . . , tn, s\Sigma on the nodes.

Each legal roster corresponds to a path from source to sink. The roster costs are obtained as the path costs if the edge weights are given as follows:

1. An edge from source s to node t is labeled with costs fis,t := 0. 2. An edge from node t to node t\Sigma is labeled with the costs fit,t\Sigma that present the costs for

executing t\Sigma directly after t. 3. An edge from node t to the sink node s\Sigma is labeled with the costs that t will have if it is

the last task in the roster.

We can also represent the reduced costs of a roster in this way. We distinguish two kinds of constraints in the master problem. The first kind of constraint ensures that exactly one roster is selected for each crew member. We know a-priori that the coefficient ai is 1, if constraint i concerns the considered crew member c and 0 otherwise. The second kind of constraint ensures that each task is covered by the required number of crew members. The coefficient ai of the latter constraint will be 1, if the constraint concerns task t and if task t belongs to the selected path. Otherwise it will be 0. We can therefore simplify Eq. (2) as

-\Sigma c - \Theta

tffiY

(fit,t\Sigma - \Sigma t ) < 0 (6)

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 69 where \Sigma t is the dual value of master constraint for task t and \Sigma c is the dual value of master constraint for crew member c. Edge weights are then adapted correspondingly.

1. For edges from the source s to any task t we only add the negative dual of the crew

member, i.e.,

c\Sigma s,t = -\Sigma c. (7)

2. Edges from node t to node t\Sigma (or to sink s\Sigma ) are labeled with the difference of the initial

costs fit,t\Sigma and the dual value of task t:

c\Sigma t,t\Sigma = fit,t\Sigma - \Sigma t (8) These new costs c\Sigma t,t\Sigma reflect the reduced costs for performing activity t\Sigma after t. We call them also reduced costs of activity t and we distinguish them from the initial costs ct,t\Sigma of task t. Each roster with negative reduced costs then corresponds to a path from source to sink with negative costs in the graph with weights c\Sigma t,t\Sigma . However, not every path from source to sink is a legal roster. We can already reduce a large number of illegal paths in a preprocessing step by removing edges. If task t\Sigma cannot follow task t since this violates some rule (e.g., on minimal rest time) we suppress the edge (t, t\Sigma ) in the graph. Rules that depend on more than two tasks cannot be treated in this way. For example rule (R6) requiring a day off after 5 days of work depends on more than two successive tasks. In the next sections, we show how constraint satisfaction techniques can be exploited to obtain dynamic reductions of the graph.

2.5. A negative reduced cost constraint We show how to encode the negative reduced cost condition in the CSP-framework. The first idea is to use the Eq. (6) and to directly encode it by a sum-over-set constraint. For the sake of readability we do not specify the relation of the constraints, but just give the condition that the constraint is imposing on the value of Y .

-\Sigma c - \Theta

tffi _Y _

c\Sigma t < 0 where _c\Sigma t = _ct - \Sigma t (9)

The initial costs ct of task t and its `reduced costs' c\Sigma t are represented by constrained variables. The variable ct can have a more complex definition involving next-in-set constraints (which will be explained in Section 2.8).

Although this is a straightforward way to express the negative reduced cost constraint, we have to analyze how effective it is. The negative reduced cost constraint is a very tight constraint. If it does not reduce the domains sufficiently early during the search, much search effort will be spent in subtrees of the search space which will not contain any roster of negative reduced cost.

We only have an upper bound on the reduced costs of a roster, namely 0. The sum-over-set constraint uses this upper bound as follows. First, it determines a necessary lower bound lb by summing up the lower bounds min(c\Sigma t ) of the tasks. If lb is strictly greater than 0

an inconsistent search state is reached and backtracking occurs. Otherwise, if the bound lb is smaller than 0 the constraint checks for each element t in pos(Y )\req(Y ) whether its

70 FAHLE ET AL. selection would make the lower bound greater than 0. If so, the task t will be removed from the possible set.

This method is only efficient, if a good lower bound is computed. The lower bound is defined as follows:

lb := -\Sigma c - \Theta

tffi req(Y),min(c\Sigma t)>=0

min(c\Sigma t ) + \Theta

tffipos(Y),min(c\Sigma t)<0

min(c\Sigma t ) (10)

Suppose that almost all tasks could have negative reduced costs c\Sigma t . The sum-over-set constraint does not know any incompatibilities between tasks and assumes that all tasks in

pos(Y ) could be selected. In this case, we obtain a very small negative lower bound, which probably will not lead to any domain reductions. Domain reductions will only occur deep in the search tree when the size of the possible set comes close to the size of the required set.

The graph introduced in Section 2.4 avoids a large number of incompatible tasks. If task t\Sigma cannot follow task t there is no edge from t to t\Sigma . A path of the graph never contains two successive tasks that are incompatible. As a consequence, a shortest path in the graph leads to a much tighter lower bound and to better propagation.

In the next section, we introduce a path constraint that implements this approach and that provides a significant improvement over the sum-over-set constraint. We nevertheless keep the sum-over-set constraint in order to be able to measure the improvements. In our experiments we use a simplified implementation of this sum-over-set constraint that avoids all calculations for propagations which will probably not be effective anyway. It just provides the basic pruning rule that compares the calculated lower bound lb with the given upper bound 0. Hence, no domain reduction is caused by this constraint. It thus provides an interesting basis for comparisons, because it is fast and does not lead to any computational overhead.

2.6. An efficient path constraint In this section, we introduce a path constraint for acyclic graphs that provides a powerful propagation for the negative reduced cost condition.

The path constraint is defined for a directed acyclic graph G = (V, E), the edge costs ci, j , a set variable Y , and a variable z. The graph G has the same form as in Section 2.4 except that we use numbers for representing the nodes. If the tasks are ordered by increasing start time as follows t1, . . . , tn we replace ti by i, s by 0, and s\Sigma by n + 1. Since there is no edge from i to j if j < i, the node numbers represent a topological order.

To simplify the notation we define t0 := s and tn + 1 := s\Sigma . The path constraint then has the variables Y and z and is defined by two conditions:

1. Y represents a path in the graph from source s to sink s\Sigma , i.e., _Y fi T and

{(i, j) | ti ffi _Y j {s}, t j = next(ti , Y )} fi E (11)

2. z is the sum of the edge costs

_z = \Theta

tiffi _Yj{s}, tj=next(ti,Y)

ci, j (12)

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 71

where next (t, Y ) denotes the successor of t on the path Y . Since we have a topological order on G, this successor is uniquely defined as

next (t, Y ) = min{t\Sigma ffi _Y j {s\Sigma } | t\Sigma > t} where t j > ti iff j > i. (13)

In the following, we introduce propagations of the path constraint that are important for roster generation. In this case, we just have the upper bound 0 on the path costs z. The propagations require the calculations of paths from source to sink that contain all required tasks and only possible tasks (i.e., the set of nodes Y of such a path has to satisfy req(Y ) fi Y fi pos(Y )). We call such a path admissible. The propagation rules are:

1. If the bound min(z) is smaller than the costs lb of the shortest admissible path (or +_

if there is no admissible path) we replace it by lb. If the new bound is strictly greater than the upper bound max(z), a failure is obtained as a consequence. 2. If the costs of the shortest admissible path through node i for i ffi pos(Y ) are strictly

greater than the upper bound max(z) we can remove i from pos(Y ).

In the next section, we show how shortest admissible paths can be computed efficiently. Furthermore, we discuss how to maintain these paths when incremental updates occur.

2.7. Implementation To compute a lower bound on the reduced costs, we just have to solve the single source shortest path problem (SSSP) starting with node s. We denote the single source shortest path distance from s to s\Sigma by yss\Sigma and call it the SSSP-distance. The SSSP-distance is the desired lower bound on the reduced costs of all legal rosters, as each of them can be identified with a (s, s\Sigma )-path.

To solve the SSSP, we apply an algorithm that makes use of the acyclic structure of the graph. It visits nodes in topological order and thus runs in linear time O(|V | + |E|). Furthermore, it does not require that edge costs are positive (see Cormen, Leierson, and Riverste, 1990, for details).

However, we have to ensure that the algorithm determines only nodes which are subsets of pos(Y ) and supersets of req(Y ). For this purpose, we consider only nodes in pos(Y ) and we ignore all edges (i, j) that go around a node of req(Y ). That means, if there is a k ffi req(Y ) s.t. i < k < j we do not consider (i, j). This can be done efficiently by determining the smallest element k ffi req(Y ) that is strictly greater than i and ignoring all edges (i, j), * j > k.

During the search for a legal roster, the domain of Y changes frequently, which means that many and often similar SSSPs have to be solved. We therefore developed an incremental version of the algorithm that computes the differences in the domains of the current and the last iteration. The required set may have grown and the possible set may have shrinked. If a new node became required, we need to restart the SSSP-algorithm with this node and can stop when we first run over an already formerly required node; its difference in distance then applies to all following nodes as well. The algorithm follows the support idea in the style of AC-6 (Bessi`ere, 1994). If a node i\Sigma left the possible set, we check if any adjacent node i is affected by that change. We call i\Sigma the support node for i.

72 FAHLE ET AL.

If the node i is affected, its support may be replaceable by another node without a change in the distance ysi to the start node s. If this is not the case, we need to do the distance update and mark the successors of node i for a continuing update on all affected nodes. Notice, that the updates for all nodes can be done in one pass.

Of course, if the lower bound becomes greater than zero, the search for a legal roster with negative reduced costs fails and we backtrack. If not, we can use the distance information just computed to reduce the domain of Y further.

To eliminate activities from pos(Y ), we must determine the cost of a shortest admissible path going through node i ffi pos(Y ). For directed acyclic graphs, this cost is simply the sum of the costs ysi of the shortest path from the source s to node i and the costs ys\Sigma i of the shortest path from i to the sink s\Sigma . The latter can be computed with the same algorithm by just inverting all the edges and by applying it to the sink s\Sigma . If ysi + ys\Sigma i is non-negative, we remove i from the possible set. These ideas are summarized in Algorithm 2. To have a compact representation we omit the technical details of the incremental variant.

Algorithm 2 (Non-Incremental) Shortest Path Constraint

for all i ffi T do

ysi := _; ys\Sigma i := _; yss := 0; ys\Sigma s\Sigma := 0 // Init source and sink k := 0; // determining shortest path from source s to all nodes for all i ffi V taken in increasing topological order do

if k <= i then

k := min{l ffi req(Y ) | l > i}; //get next required node in the top. ordering for all j ffi pos(Y ) s.t. (i, j) ffi E and j <= k do

if ysj > ysi + ci, j then

ysj := ysi + ci, j //determining reverse shortest path from sink s\Sigma to all nodes k := 0; for all i ffi V taken in decreasing topological order do

if k >= i then

k := max{l ffi req(Y ) | l < i}; //get next required node in the top. ordering for all j ffi pos(Y ) s.t. ( j, i) ffi E and j >= k do

if ys\Sigma j > ys\Sigma i + c j,i then

ys\Sigma j := ys\Sigma i + c j,i if yss\Sigma > min(z) then

min(z) := yss\Sigma // propagate new lower bound on costs for all i ffi pos(Y ) do

if ysi + ys\Sigma i > max(z) then

pos(Y ) := pos(Y )\Xi {i} //exclude nodes that are too expensive

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 73 2.8. Single crew member rules The rules and regulations coming from legislation and contractual agreements are formulated by constraints over set variables, such as cardinality constraints, sum-over-set constraints, next- and previous-in-set constraints, or set-of constraints. Most of them are provided by the constraint library ILOG SOLVER, others have been implemented as extensions of SOLVER. Given the flight time ft (block hours) of each task t and a maximal flight time

F, we can express a maximal flight time rule by a sum-over-set constraint

\Theta

tffi _Y

ft <= F. (14)

In order to express a minimal rest time rule between two successive tasks, we need the arrival time end(t) of a task t and the departure time start(t\Sigma ) of the next task t\Sigma . Given a minimal rest time \Lambda between two tasks, the minimal rest time rule can then be expressed by the next-in-set constraint (13) as follows:

start(next(t, Y )) - end(t) >= \Lambda (15) where next (t, Y ) is defined as in Eq. (13).

Regulations on days off, maximal duration of working periods, and so on, can be expressed as well, but usually lead to more complex constraint models. In order to facilitate this modeling task, a specific ROSTER LIBRARY has been developed in the scope of the PARROT project (1997). Complex crew regulations that have been formulated by expressions of the ROSTER LIBRARY are automatically translated into compact constraint models of SOLVER.

In real world CAPs the rules and regulations will vary from crew member to crew member. Quite often individuals only differ with respect to parameters (e.g. reduced flying time). This doesn't affect the number of rules or the structure of these. It may also be, that there has to be some kind of compatibility between attributes (e.g. qualifications) of the crew member and attributes (requirements) of the tasks. This is also modeled with generic rules, where the results clearly depend on the crew member in question. A common rule requires that the aircraft type flown must be in the set of aircraft types, for which the crew member is qualified. We may have cases where different crew members work under completely different agreements. This increase the number of rules, but not necessarily the number of constraints, as all rules will not apply to all crew members.

Since the resulting models become quite complex, we illustrate the possible propagations just for two rules, namely (R1) and (R2). For (R1) (Minimum Rest at Home Base) we get a constraint model that excludes all those activities from the possible set of Y that cannot follow legally any already required activity. Rule (R2) (Minimum Rest for One Day Off) is modeled such that any possible activity that follows a required one with one airline day in between is excluded from further search, if the rest time is less than \Lambda 2. The corresponding propagation rules are given in Algorithm 3.

74 FAHLE ET AL. Algorithm 3 Propagation Algorithm for Rules (R1) and (R2)

for all t ffi req(Y ) do

for all t\Sigma ffi pos(Y )\req(Y ) do

if (start(t\Sigma ) - end(t) < \Lambda 1) then

pos(Y ) := pos(Y )\{t\Sigma } // Rule R1

for all t ffi req(Y ) do

for all t\Sigma ffi pos(Y )\req(Y ) do

if (one airline day(t, t\Sigma ) AND (start(t\Sigma ) - end(t) < \Lambda 2)) then

pos(Y ) := pos(Y )\{t\Sigma } // Rule R2

2.9. Search heuristics The shortest path constraint and the negative reduced cost constraint help to reduce the search effort in pruning parts of the search tree without using the special structure of the underlying problem. However, for moderate to large size real-world problems this pruning alone is not sufficient for finding promising rosters. Heuristics designed for the special structure of the CAP are needed to prune further and/or guide the search to promising regions of the search space. The search space is explored by Algorithm 4.

Algorithm 4 A Non-Deterministic Algorithm Describing the Search Tree

while (pos(Y ) ,= req(Y )) do

1: select a task t ffi pos(Y )\req(Y ) s.t. t is on a shortest admissible path 2: chose (req(Y ) := req(Y ) j {t}) OR (pos(Y ) := pos(Y )\{t}) 3: apply constraint propagation algorithm

The task selection (Step 1 in Algorithm 4) should take care of first selecting the best activity from the possible set. It is often possible to sort activities during preprocessing (static ordering). In case the order of activities depends on the search history, the ordering can also be carried out during the search (dynamic ordering).

As static ordering method one can choose the first possible successor of the last activity that is already required. This first activity first approach is believed to be good at generating productive rosters with only little idle time between activities. In general, these rosters have a low cost, due to the fact that airlines typically prefer such rosters to those with much unproductive time between two activities. This static ordering is also used by Ryan (1992).

We get a dynamic ordering when using the shortest path constraint and choosing the pairing on the path that contributes the lowest value to the path costs. The Lowest Reduced First (LRF) method selects a task with the lowest reduced cost and proves to be superior in our experiments. The advantage of LRF is that the costs contributed by the pairing to the resulting costs of the roster are also taken into account.

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 75

For the branching order (Step 2 in Algorithm 4) we try to add the selected task to the required set of Y in the first branch and to remove it from the possible set of Y on the second branch.

3. The entire approach 3.1. The master problem To combine the rosters generated by solving the subproblem to one entire work plan, the master problem has to be solved. It consists of minimizing the total cost (the sum of all chosen rosters) by choosing exactly one line of work for each crew member, such that all pairings are assigned exactly once. This problem can be stated as binary IP problem, or--to be more precise--as a set partitioning problem (SPP). However, we are also interested in the set covering problem (SCP) as we use it as a relaxation of the SPP. These two problems are defined as

SPP: min cx, s.t. Ax = 1, x binary (16) SCP: min cx, s.t. Ax >= 1, x binary (17)

where A is a 0-1 matrix, and c is the cost vector for the columns. Both problems are well studied and good algorithms solving (16), (17) can be found in the literature (see e.g., Caprara, Fischetti, and Toth, 1996; Hoffman and Padberg, 1993).

A legal roster Y for a crew member is translated into a column of matrix A by inserting 1's into the row corresponding to the crew member and into all rows that correspond to activities used in Y . Especially in the beginning, however, it is unlikely and hard to guarantee that the columns generated so far will fit together exactly. Having n crew members and m activities, we extend A by unit-vectors ei , i = 1, . . . , n + m, ensuring that the resulting set partitioning problem always has a feasible solution. The so-called dummy rosters can be interpreted as crew members without work (i = 1, . . . , n), and uncovered activities (i = n + 1, . . . , n + m), respectively. To find meaningful solutions, we have to penalize uncovered pairings by assigning high costs to the columns representing them.

Obviously, solutions consisting of many dummy rosters are not of interest. Therefore we relax the last n constraints to SCP constraints, i.e., every activity must be covered at least once. Due to the high costs of the dummy rosters, a solution will contain few or even no dummy rosters. But in the solution some of the chosen columns might collide in the sense that there are activities that are assigned more than once. Then, a solutions respecting SPP constraints is heuristically obtained by adding new legal subrosters extracted from colliding ones.

However, in some cases it is not possible to simply fix collisions without generating new rosters in the subproblem. E.g., a rule limiting the minimum working time for a roster might not allow to build subrosters of a colliding roster. In such a case, the solution of the SPP will contain dummy rosters and the subproblem has to generate different rosters from scratch using new dual information.

76 FAHLE ET AL. 3.2. Multiple crew member rules In real world applications of crew assignment, there is also a class of multiple crew member rules that involve properties of several rosters. E.g., for cabin crew it might be necessary to have at least n1 people speaking a certain language on a certain flight. Another typical example is to have at most n2 unexperienced persons in the cockpit. As the subproblem only handles single rosters, these rules have to be handled in the master problem.

A simple way of integrating linear multiple crew member constraints (as the ones sketched above) is to extend the SPP by additional constraints. These constraints are usually expressed by a weighted sum over some attributes of the crew members. The only complication arising then is to compute the reduced costs when generating rosters in the subproblem. To do this, the column generator just needs to have knowledge about the coefficients of the multiple crew member constraint that will arise when adding an activity to a roster. In essence Eq. (10) is adapted by adding dual values of all those multiple crew member rules in which the current crew member provides a nonzero attribute.

Therefore, multiple crew member rules do not change the behavior of the negative reduced cost constraint in principal. Thus to keep the setting simple we will not use multiple crew member rules in the experiments (Section 4).

3.3. Overview of the approach With the different components discussed before, we are now able to describe their interaction. First, we set up the master problem and add dummy rosters (i.e., crew members without work and unassigned activities) to ensure the existence of a solution. We additionally append a certain number of initial rosters for each crew member. Then we initialize the column generator and define the search strategies to be used.

Entering the (outer) loop of master iterations (see figure 1), we solve the current SPP-IP and get a first current solution and new dual values of the LP-relaxation. The column generator then defines the next subproblem to be solved by picking a crew member and maybe additionally applying other search limitations as, e.g., fixing some assignments according to

Figure 1. The entire approach: The inner loop generates columns using dual information, the outer loop solves the master problem.

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 77 a time window focus and the current SPP solution. We start generating a specified number of rosters, then add the corresponding columns to the master problem, solve its continuous relaxation, and update the current dual values. This inner loop corresponds to Algorithm 1.

After rosters have been generated for all crew members, we solve the set covering relaxation of the SPP master problem and generate subrosters of the rosters used in the SCP optimal solution to resolve collisions in the SPP. Afterwards, the SPP itself is being solved and a new loop begins.

This process is either interrupted after a given time limit has been exceeded or when no more rosters have been generated that yield to an improvement of the LP-relaxation in any of the subproblems.

4. Numerical results In this section, we show that constraint programming based column generation is able to solve non-trivial crew assignment problems. In particular, we demonstrate the effect obtained by the propagation of the path constraint.

As mentioned before, the problem instances used for the experiments stem from a major European airline. The rules, regulations, and objective function have directly been abstracted from the real-world case and preserve the essential characteristics of this case. The data sets are sufficiently large to measure the effects of constraint propagation, but they are small enough to run experiments in a reasonable time frame.

To characterize an instance, we specify the number of crew members, the number of preassigned activities, and the number of activities to be assigned. For example, an instance of type 67-165-280 consists of 67 crew members, 165 preassignments, and 280 tasks. All experiments were run on a SUN Ultra 4 with 296 MHz CPU and 1024 MB main memory. For the constraint model of the CAP, the ROSTER LIBRARY (1997) based on ILOG SOLVER 4.4 (1999) was used. The LP and IP problems were solved with ILOG PLANNER 3.3 (1999).

It is important to note that the size of a problem instance is not only determined by the number of crew members and tasks, but also by the number of subtasks (e.g. flight legs and ground duties) and the number of attributes per tasks. In the example above, the 280 tasks consist of 1422 sub-tasks. The given rules and regulations are formulated with the help of 66 attributes per task, 32 per sub-task, and 7 per crew member. A part of these attributes is translated into constrained variables.

In the experiment for figure 2 we show the effects of negative reduced cost constraint (NRC) and shortest path constraint (SPC). We compare both results with a total enumeration, where neither NRC nor SPC is used to reduce the search space. The left picture shows the reduction of choice points. In the end SPC used less than half the number of choice points than the NRC. This gain is not consumed by a significant increase in computation time per choice point. As shown in the left figure the decrease in running time is quite similar to the decrease in the number of choice points. As expected, total enumeration is not competitive at all.

To demonstrate the superiority of the shortest path constraint against the negative reduced cost constraint in more detail we run a test on a small instance where in each master iteration the number of choice points was noted. Figure 3 again shows that the shortest path constraint uses much less choice points than the negative reduced costs constraint. Furthermore, in the

78 FAHLE ET AL. Figure 2. Number of choice points versus master iteration (left), and running time versus master iteration (right) for SPC, NRC, and total enumeration. The tests were run with a data instance of type 10-00-20 that was solved to optimality.

Figure 3. Number of choice points versus master iteration using SPC, NRC with a data set of type 7-0-30. last iteration the shortest path constraint does not find any columns with negative reduced costs anymore, thus proving optimality for the continuous relaxation of the master problem. The negative reduced cost constraint, however, still visits an increasing number of choice points per iteration.

One reason for the efficiency of the shortest path constraint and the reason why there is almost no gap between the reduction of choice points and the reduction in time is the use of the incremental version as mentioned in Section 2.7. In figure 4 we compare a

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 79 Figure 4. The picture shows time versus the number of calls of the propagation routine using the incremental and the non-incremental implementation of the shortest path constraint. Both versions were stopped after 10 000 seconds total CPU time. The experiment was run with a data instance of type 10-00-70.

non-incremental version of the shortest path constraint with an incremental one. For a fixed time of 10 000 sec. for the entire optimization the faster incremental version uses only 2 000 seconds for the propagation, whereas for the non-incremental version almost 60% of total calculation time goes into that part of the algorithm. Thus, the incremental version allows to perform nearly 3 times as many propagations as the non-incremental version and hence helps to improve solution quality.

Figure 5 shows a time versus quality comparison of NRC and SPC. After a first big drop in the objective, the NRC falls into huge search trees that only consist of rosters with nonnegative reduced costs. The SPC can prune those search trees much earlier and therefore continuously reduces the objective without stalling.

The numerical results clearly prove the potential of SPC and that the overhead created in the subproblem pays off when comparing it to NRC. However, our experiments also showed that there is room for improving the generation subproblem, using various techniques to

Figure 5. Time versus quality on a data instance of type 67-165-280. The picture shows a comparison of NRC (upper curve) and SPC (lower curve).

80 FAHLE ET AL. limit the search. The present work focused on evaluating a generic framework applied to the airline crew assignment problem. Ongoing work by the authors investigates how the approach can be improved and tailored to the problem to meet performance requirements for a real world application.

5. Conclusions We have introduced a CP-based column generation approach for the airline CAP. For the case of European airlines with complex rules and regulations common approaches using constrained shortest path algorithms to solve the subproblem in a column generation framework are limited. We therefore formulated the subproblem as a constraint satisfaction problem. Tests with real data from a major European airline showed that the development of a new shortest path constraint combining methods from CP and OR yields a significant decrease in the number of choice points during the generation. An incremental update implementation of this constraint reduces the computational effort per choice point, such that overall computation times are reduced significantly as well. Branching variable selections based on shortest path information further improve the performance.

The presented approach is an example of a successful integration of CP and column generation. We believe that this approach will prove useful for a number of important optimization problems which are currently solved using only OR or only CP methods. There are still refinements and improvements to be done, but this work demonstrates the applicability and efficiency of the approach.

Notes 1. We will use activity and task synonymously. 2. Non-chronological search methods such as best-first search and limited discrepancy search are also available.

References Andersson, E., E. Housos, N. Kohl, and D. Wedelin. (1998). "Crew Pairing Optimization." In G. Yu (ed.), Operations Research in the Airline Industry, International Series in Operations Research and Management Science, Vol. 9. Dordrecht: Kluwer Academic Publishers, pp. 228-258. Barnhart, C., E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, and P.H. Vance. (1998). "Branch-and-Price:

Column Generation for Solving Huge Integer Programs." Operations Research 46(3), 316-329. Barnhart C. and R.G. Shenoi. (1998). "An Approximate Model and Solution Approach for the Long-Haul Crew

Pairing Problem." Transportation Science 32(3), 221-231. Beringer, H. and B. De Backer. (1995). "Combinatorial Problem Solving in Constraint Logic Programming with

Cooperative Solvers." In C. Beierle and L. Plumer (eds.), Logic Programming: Formal Methods and Practical Applications. Amsterdam: Elsevier, pp. 245-272. Bessi`ere, C. (1994). "Arc-Consistency and Arc-Consistency Again." Artificial Intelligence 65, 179-190. Bockmayr, A. and T. Kasper. (1998). "Branch and Infer: A Unifying Framework for Integer and Finite Domain

Constraint Programming." INFORMS Journal on Computing 10(3), 287-300. Caprara, A., M. Fischetti, and P. Toth. (1996). "A Heuristic Algorithm for the Set Covering Problem." In Integer Programming and Combinatorial Optimization, 5th International IPCO Conference Proceedings. Berlin: Springer, pp. 1-15.

CONSTRAINT PROGRAMMING BASED COLUMN GENERATION 81 Caprara, A., F. Focacci, E. Lamma, P. Mello, M. Milano, P. Toth, and D. Vigo. (1998a). "Integrating Constraint

Logic Programming and Operations Research Techniques for the Crew Rostering Problem." Software--Practice and Experience 28(1), 49-76. Caprara, A., P. Toth, D. Vigo, and M. Fischetti. (1998b). "Modeling and Solving the Crew Rostering Problem."

Operations Research 46(6), 820-830. Cavique, L., C. Rego, and I. Themido. (1999). "Subgraph Ejection Chains and Tabu Search for the Crew Scheduling

Problem." Journal of the Operational Research Society 50, 608-616. Chu, H.D., E. Gelman, and E.L. Johnson. (1997). "Solving Large Scale Crew Scheduling Problems." European

Journal of Operational Research 97, 260-268. Cormen, T.H., C.E. Leierson, and R.L. Riverste. (1990). Introduction to Algorithms. New York: McGraw-Hill. Dantzig, G.B. and P. Wolfe. (1961). "The Decomposition Algorithm for Linear Programs." Econometrica 29(4),

767-778. Day, P.R. and D.M. Ryan. (1997). "Flight Attendant Rostering for Short-Haul Airline Operations." Operations

Research 45(5), 649-661. Desaulniers, G., J. Desrosiers, Y. Dumas, S. Marc, B. Rioux, M.M. Solomon, and F. Soumis. (1997). "Crew Pairing

at Air France." European Journal of Operational Research 97, 245-259. Desrosiers, J., Y. Dumas, M.M. Solomon, and F. Soumis. (1995). "Time Constrained Routing and Scheduling."

In Ball, Magnanti, Monma, and Nemhauser (eds.), Network Routing, Handbooks in Operations Research and Management Science, Vol. 8. Amsterdam: North-Holland, pp. 35-139. Gamache, M., F. Soumis, D. Villeneuve, J. Desrosiers, and E. G'elinas. (1998). "The Preferential Bidding System

at Air Canada." Transportation Science 32(3), 246-255. Gilmore, P.C. and R.E. Gomory. (1961). "A Linear Programming Approach to the Cutting Stock Problem."

Operations Research 9, 849-859. Hoffman, K.L. and M. Padberg. (1993). "Solving Airline Crew Scheduling Problems by Branch-and-Cut." Management Science 39(6), 657-682. Hooker, J. (1999). "Unifying Optimization and Constraint Satisfaction." Invited talk at IJCAI '99. Slides available

at http://ba.gsia.cmu.edu/jnh/ijcai.ppt. ILOG PLANNER 3.3. (1999). Reference manual and user manual. ILOG. ILOG SOLVER 4.4. (1999). Reference manual and user manual. ILOG. Kohl, N. and S.E. Karisch. (1999). "Airline Crew Assignment: Modeling and Optimization." Carmen Report. Mackworth, A.K. (1977). "Consistency in Networks of Relations." Artificial Intelligence 8(1), 99-118. Montanari, U. (1974). "Networks of Constraints: Fundamental Properties and Applications." Information Science

7(2), 95-132. Nuijten, W.P.M. and E.H.L. Aarts. (1996). "A Computational Study of Constraint Satisfaction for Multiple Capacitated Job Shop Scheduling." European Journal of Operational Research 90(2), 269-284. PARROT. (1997). Executive Summary. ESPRIT 24 960. Rodosek, R., M. Wallace, and M.T. Haijan. (1999). "A New Approach to Integrating Mixed Integer Programming

and Constraint Logic Programming." Annals of Operations Research 86, 63-87. Rushmeier, R.A., K.L. Hoffman, and M. Padberg. (1995). "Recent Advances in Exact Optimization of Airline

Scheduling Problems." Technical Report, George Mason University. Ryan, D.M. (1992). "The Solution of Massive Generalized Set Partitioning Problems in Aircrew Rostering."

Journal of the Operational Research Society 43(5), 459-467. Van Hentenryck, P., Y. Deville, and C.M. Teng. (1992). "A Generic Arc-Consistency Algorithm and its Specializations." Artificial Intelligence 57, 291-321. Yu, G. (ed.). (1998). Operations Research in the Airline Industry, International Series in Operations Research and

Management Science, Vol. 9. Dordrecht: Kluwer Academic Publishers.