1 Aircraft Allocation in a Parallel Constraint Logic Programming Environment
- 格式：pdf
- 大小：155.41 KB
- 文档页数：31
Aircraft Allocation in a Parallel Constraint Logic Programming EnvironmentGrant Report: IED3/45/91/015Science and Engineering Research CouncilDepartment of Trade & IndustryDionisios Pothos, Barry Richards and Davor StokicIC-ParcImperial College1 IntroductionThis paper describes research supported over the past two years by a grant from the Department of Trade and Industry to IC-Parc under the auspices of the London Parallel Applications Centre. The aim of the project was to assess the benefits of parallelism for the generic constraint-based planning architecture parcPLAN1 developed at IC-Parc. parcPLAN[2] addresses industrial applications where resource handling and optimisation is of primary importance. parcPLAN consists of two modules; an action-introduction module which finds a set of actions that potentially achieve a set of goals and a collapsing module which establishes whether the actions are actually sufficient to realise the goals; they are sufficient if the actions can be scheduled consist with the resources available. The collapsing module addresses both the feasibility of a set of actions to the goals specified and the optimisation of resources, both temporal and non-temporal.The collapsing phase constitutes the major computational burden in parcPLAN, and the performance of this part of the system can be well below desired response times. If large industrial problems are to be handled, the performance of the collapsing module must be substantially improved. There are two general approaches which promise to yield improvements, viz. heuristic search and parallelism. We shall explore several aspects of these approaches in this report by addressing a large industrial application, the British Airways Short-haul Aircraft Allocation (SAA) problem. The programming environment will be the constraint logic programming language ElipSys [4, 5, 7, 11] which provides OR-parallelism together with constraint handling facilities. We shall describe several algorithms developed in ElipSys and indicate their performance on the SAA problem.1.1 ElipSys: OR-Parallel Constraint Logic Programming SystemIn the ElipSys environment constraint logic programming[1] and OR-parallel logic programming[3,12] are combined with a view to addressing hard combinatorial optimisation problems. Constraint solving and OR-parallelism are complementary [9]: the former is used to reduce search (by pruning) while the latter is used to speed-up search (by exploring simultaneously independent parts of the search space). ElipSys is the first programming system which combines these two technologies.1parcPLAN is a successor of IQ-PLAN [6]ElipSys inherits the constraint part over finite domains from its ancestor CHIP[9] CLP language. I t provides constraints over finite domains (i.e. #<2, #², ##, #>, #³ ) and a number of high-level constraints (i.e. element/3, disjunctive/4 etc.), together with the necessary propagation mechanisms and other advanced constraint handling facilities[7]. Constraint propagation has been shown to improve search efficiency by pruning parts of the search space which do not contain any solutions. ElipSys also has built-in branch&bound primitives which facilitate the development of optimisation algorithms.ElipSys is equipped with annotations which enable the programmer to express during search where the search tree can be split into sub-trees that can be traversed in parallel (OR-parallelism). Any non-deterministic predicate can be used as a source of parallelism by declaring it as parallel. For example, consider the following non-deterministic predicate clause/1.:- parallel clause/1.clause(X):- goals1(X).clause(X):-goals2(X).OR-parallel execution of clause/1 results in the concurrent execution of goals1(X) and goals2(X). Other specific ElipSys built-in parallel predicates can be used for the concurrent treatment of a set of data (data parallelism).The programmer is free of any implementation details regarding parallelism; his task is to use the implemented parallelism to solve his problem efficiently. However, this transparent way of exploiting parallelism does not come for free; it generates significant overhead for the system to spawn and allocate parallel work to processors. The grain size of the computations (grain size of predicate calls) which the programmer creates must be at least as large as this overhead in order to be worth executing in parallel. Because of this we say that ElipSys has coarse-grained parallelism [4] and the programmer must be aware of this to maximise efficiency. Estimating the grain size of the computations is not an easy task (because of the dynamic flow of computations). Unfortunately, no analysis and transformational tools are available at the moment to help the programmer to estimate the grain size of the parallel work it creates.2 “#” is a reserved symbol in ElipSys used to differentiate between normal arithmetic operators and constraints.1.2 The SAA problemFleet assignmentAircraft assignmentFlight route constructionFigure 1.2 The organisation view of the flight management problemThe Shorthaul Aircraft Allocation (SAA) problem is part of the general flight management problem (see Figure 1.2). SAA addresses aircraft assignment, that is, the start-of-day allocation of aircraft to flights and their reallocation during the day arising from unexpected events (delays, aircraft defects, etc.). Aircraft allocation is of high business value since approximately 80% of the assets of an airline are aircraft.The SAA problem consists of the following.• A set of aircraft located at specific airports and available for use after a certain time,• A set of flights and maintenance requests,• A set of preferences concerning the operational status of an aircraft and its allocation to flights.Each aircraft is in a specific operational status, defined in terms of potential “defects”, e.g. some problem with the ventilation or a toilet's being out of order. An aircraft is defined by a tuple of the form,aircraft(Aircraft_id, Release_time, Start_Airport, Start_Terminal)and the operational status of an airplane by a set of tuples, one for each “defect”.aircraft_status(Aircraft_id, Part_id, Part_Status)Flights are structured into tours consisting of sequences of flights. This reflects a preference that the same aircraft should take all the flights in a tour. At the start of a given day, however, not all tours are necessarily consistent; this can be caused by temporary changes in the flight specifications or by delays which occurred the previous day. The flight specifications are modified incrementally to reflect these changes. These are given in the form of flight requests which are specified as follows.request(Request_id, Aircraft, Type, Start_time, End_time,Start_airport, Start_terminal, End_airport, End_terminal, Tour_id).Maintenance requests are distinguished by the fact that their start and end airports are the same.Preferences are used to assert that an aircraft in a specific operational status should not take a specific flight or that a specific aircraft should avoid ending its “tour” at specific airports. There is a large number of such preferences concerning aircraft assignment. A preference is specified by a tuple of this form.preference(Conditions, Prohibited_Aircraft_Status, Weight)The SAA problem is to assign aircraft to all flights satisfying maintenance requirements and minimising,•the number of aircraft used,•the violations in the “original” tour structure,•the violations of the preferences.There are two general solution requirements. (1) Dynamic scheduling : It must be possible to react quickly to all changes (flight delays, aircraft availability and status). (2) Flexibility and scalability : It must be possible to deal quickly with new requirements and constraints.The data sets for the problem are given below.Table 1.2 Data sets for this studySix real size data sets, which have been supplied by British Airways, consist of sets of European flights to be allocated to specific fleet of aircraft. A data set is specified by 5 parameters: number of aircraft, number of attributes describing the operational status of aircraft (OSA), number of flights, number of flight delays and number of aircraftmaintenance requests. All b3 data sets involve the same aircraft fleet (16 aircraft) and similarly for b5 data sets (26 aircraft). All aircraft in a fleet are of the same type.2 The basic CLP approachIn order to solve a problem in a CLP environment, we must model it as a constraint satisfaction problem (CSP) [8]. A CSP consists of a set of variables (the problem objects) each defined over a set of alternatives (the variable’s domain) and a set of constraints (the relations between problem objects). A solution to a CSP is an assignment to the problem variables which satisfies all the constraints. The search for a solution is conducted through the space of possible assignments.The methodology for solving a problem in CLP consists of three steps.• Identify the variables necessary to model the problem. This is the most crucial choice since there are usually many ways to model the problem.• State the constraints.• State additional constraints and domain specific heuristics in order to improve the efficiency and the robustness of the constraint solver.2.1 The SAA as a CSPGiven that the temporal information (start and end times) for each request is fixed, the SAA problem can be completely specified in terms of the directly precedes relation, where TA1 and TA2 are constant turn-around times.directly_precedes(a,b) ⇔end_airport(a) = start_airport(b) ∧((end_terminal(a) = start_terminal(b) ∧start(b) ³ end(a) + TA1) ∨(end_terminal(a) _ start_terminal(b) ∧start(b) ³ end(a) + TA2))Using the directly precedes relation, we can represent the SAA problem as a directed disjunctive graph (DDG) where the nodes represent resources (aircraft) and requests (flights and maintenance), and the directed arc between two nodes a and b is represented in terms of the relation directly_precedes(a,b). For example, see Figure 2.1.AircraftsFlightsMaintenance precedes b)________________________________________________________________Figure 2.1 A representative SAA problemHere the node labelled N-A is a request whose start airport is N and end airport A. This request has three nodes which directly precede it, viz. M-N, H-N and A3(N). The last of these represents an aircraft located at airport N. A solution to a directed disjunctive graph is a set of paths such that each path begins with a resource node (an aircraft) and every node belongs to one and only one path. In the case of the DDG in Figure 2.1 there are three resource nodes and hence, a solution can have at most three paths, although it might have less.The SAA problem is formulated as a CSP in the following way: Let R={r 1,...,r n ) be the set of requests and A={a 1,...,a m } the set of aircraft.VariablesFor each request r i ∈ R , let the variable X i range over the set of aircraft.X={X 1,...,X n }, Dx i = A 3, 1 ² i ² nFor each request r i ∈ R , let the variable Y i range over the direct predecessors of r i .Y={Y 1,...,Y n }, DY i ={v j ∈ A U R | directly_precedes(v j ,r i )},3 Where r i is a maintenance request, X i =a i (DX i ={a i }), a i is the maintenance aircraft.1 ² i ² nFor each request r i∈ R, let RP i be the set of aircraft which are not among those preferred for that request.RP={RP1,...,RP n}, RP i={a j∈ A | not_prefer(r i,a j)}Constraintsc1 expresses the constraint that two distinct requests cannot have the same direct predecessor.c2 expresses the constraint that if two requests overlap in time, then different aircraft must be assigned to them. This is a redundant constraint since if two requests overlap neither can be the direct predecessor of the other and so cannot be assigned the same plane. Nevertheless, given that the temporal information is fixed, c2 can be used to reduce the domains of the variables in X from the beginning since the temporal information is fixed; that is, it is determined for each pair of requests whether they overlap or not. The overlap relation is defined as follows.overlap(r i,r j) ⇔(start_time(r i) ³ start_time(r j)- TA1 ∧start_time(r i) ² end_time(r j)+TA1) ∨(start_time(r j) ³ start_time(r i)-TA1 ∧start_time(r j) ² end_time(r i)+TA1)c3 and c4 establish links between the variables in Y and X. Together the constraints imply that if request r j is the direct predecessor of request r i, the same aircraft must serve both of them; where the direct predecessor is an aircraft a k, a k will be assigned to request r i. These constraints allow propagation to “flow” between X and Y variables, thereby enhancing the pruning of values from their domains.c5 expresses the preference that among the predecessors of a request, the one that belongs to the same tour is preferred.c6 expresses the preference that the aircraft selected to perform request r i should not be in the set RP i.c7 is a constraint which dynamically calculates the cost of a solution to the problem; here f4i, f5i and f6i are Boolean variables instantiated through the following formulas• Y i = r j xor f4i•c5i xor f5i•c6i xor f6iAC is the fixed cost of aircraft use, BC the fixed cost of breaking a tour and w(x i) a function that returns the penalty of a preference violation.Definition 2.1 A feasible solution is an assignment to the variables in Y∪X which satisfies the hard constraints c1-c4.Theorem 2.1 A consistent assignment to the variables in Y with respect to the constraints c1-c4 will produce a consistent assignment to the variables in X.ProofBy virtue of constraint c1 and the modelling strategy, the following properties hold.1)The direct-predecessor relation partitions the set of Y variables into a set of disjoint chains.2) Each chain has as its first element a Y variable which must take an aircraft assignment. This is a consequence of the fact that the model imposes two properties: i) every flight request has at least one predecessor and ii) no aircraft has a predecessor.3) The partition of the Y variables creates an isomorphic partition of the X variables. Each Y variable is associated with an X variable through its associated flight request. Thatis, for each variable Y i, there is an associated request r i which itself has an associated aircraft variable X i.4)For any consistent assignment to the Y variables, the assignment to each chain <Y1,a>,<Y2, r1>,...,<Y n,r(n-1)> determines an assignment to the corresponding chain X1, X2, ... , X n. By constraint c4, X1=a, for some aircraft a.By virtue of the first disjunct of constraint c3, X1=X2,X2=X3,...,X(n-1)=X n.5)Given that the assignment to the Y variables is consistent, the assignment to the X variables is consistent. It is sufficient to show that each X variable receives a unique assignment. There are two cases to consider.i)Suppose that there are two overlapping requests r i and r j such that the resulting constraint X i_X j, arising from c2, involves variables in the same chain. From (3) above, it also follows by transitivity that X i=X j. The resulting contradiction implies that for some adjacent pair of variables in the chain, X n and X m, X n_X m, which by constraint c3 implies that Y n_r m. But it holds from the assignment to the Y variables that Y n=r m. This implies that the assignment to the Y variables is not consistent, contradicting the assumption.ii) Suppose that one of the Y variables in a chain is assigned a maintenance request involving aircraft b. And suppose, furthermore, that the initial Y variable in the chain Y1 is assigned a different aircraft a. This implies a contradiction in the assignment to the X variables, of the sort exhibited in (i). By a similar argument it follows that the assignment to the Y variables is also inconsistent, contradicting the hypothesis that the assignment to the Y variables is consistent.EndA consequence of Theorem 2.1 is that search for a feasible solution need only involve the variables in Y; each consistent assignment to the Y variables determines a feasible solution to the problem.In the following sections we describe the search algorithms for the SAA problem and their parallel versions.2.2 The basic CLP approach: Algorithm A-IThe basic CLP algorithm (A-I) treats the labelling part of the search for a solution through standard backtracking, i.e. without the aid of any special value selection or variable ordering heuristics. Variables are considered in the order in which their corresponding requests appear in the database; and the values are selected in some pre-determined way until a solution is found or all the values are exhausted.optimality; it converges to the optimal solution very fast for all them. It should be noted, nevertheless, that the proof of optimality for b3a is four times slower than that for the other variants. In the case of the larger data sets (b5), A-I does not terminate before the time limit. The parallel version of A-I, viz. PA-I, is much faster for the b3 data sets (using four processors), but it is still unable to find an optimal solution for the b5 data sets within the time limit of half an hour. In fact, it does not always improve the best sequential solution found within this time limit.There are two possible explanations for the poor performance of A-I and PA-I.(1)The number of solutions for the problem is very large and hence, the search for an optimal solution is rendered almost infeasible for “medium” size problems, e.g. the b5 cases.(2)The solutions are partitioned into large “clusters” with the same or similar costs, which weakens the pruning capability of branch & bound (B&B). One might expect the size of such clusters to increase as the number of soft constraints decrease. This would explain why A-I and PA-I can prove optimality for the smaller data sets (b3) but not for the larger ones (b5).Table 2.3 Results of applying A-I and PA-IThe disappointing results yielded by A-I and PA-I indicate that exact systematic optimisation algorithms are not scaleable to larger problems. This should not be interpreted as reflecting negatively on the techniques of CLP, which address the task of finding solutions to the hard constraints of a problem. Optimisation introduces another dimension. Here the objective function is treated as a special kind of hard constraint, i.e. one whose instantiation is changing dynamically. This is used through B&B to “sift” the solutions of a problem to find the optimal one. CLP can be efficient in finding solutions but inefficient in finding optimal ones. This is demonstrated in the performance of A-I (and PA-I) on the b3 and b5 data sets.To address the special burden of searching for optimal solutions, we shall enhance the constraint solving facilities of CLP with a range of general purpose heuristics related to variable ordering and value selection. Parallelism will be seen to yield significant benefits here. In the next chapter we describe a heuristically driven optimisation algorithm for the SAA problem.3 Approximate CLP solutionWe shall now describe an approximate algorithm based on dynamic search re-arrangement and local optimisation. We shall also analyse the results of applying this algorithm, and its parallel version, to the b3 and b5 data sets.4 The times for the experiments with A-I, and all the following algorithms, are user times, not CPU times.5 The hardware platform is a DRS6000 with 4 Sparc processors.3.1 Solution Algorithm 2 (A-II)Figure 3.1 outlines the algorithm A-II. Unlike A-I, this algorithm does not backtrack while searching for a solution. In step 3.2 it selects the locally best value for a variable in Y and does not backtrack if it fails to yield a solution. When A-II finds a solution, it returns to the root of the search tree, re-arranges the order in which variables are selected and attempts to find a better solution. This process continues until either it cannot improve on the previous solution or it cannot satisfy the hard constraints. The variable re-arrangement heuristic has the effect of visiting different parts of the search space at each iteration.A-II algorithm is incomplete both for the optimisation and for the decision parts of the problem. However, constraint propagation together with the earliest start time ordering (EST) of variables for the first iteration, minimises the probability of A-II missing a solution when there exists one.The EST ordering minimises backtracking and furthermore, in the absence of maintenance requests, guarantees that A-II will converge to a solution if the problem has one. Any other ordering threatens to result in a failure as the example in Figure 3.2 shows. In the example shown, if we label R8 before R5-R7 and the best choice is R1, we leave only two choices for the other three flights and thus we will fail later during the search. By following the EST ordering of the flights, we can find a solution for the example without backtracking._________________________________________________________________________Begin1. Order the variables in Y according to the earliest start time (EST) ofthe start times of their corresponding requests.6Goto 32. 2.1Record the current solution and its cost2.2 Post the constraint cost < cost_of_current solution2.3 Make all variables in Y uninstantiated2.4 Order the variables Y in decreasing order according to their localcosts3.While Y _ {} doBegin3.1 Select an uninstantiated variable y i according the variable order,Y <- Y - {y i}3.2 Select a value v in Dy i with the minimum "local" cost consistentwith the hard constraints,3.3 If there is no such value t henexit with the best solution found so far, otherwise the problemhas no solution3.4 Record the increase in cost caused by the instantiation of y iEnd4. Goto 2End_________________________________________________________________________Figure 3.1 A-II (Y)Figure 3.2 The situation in an airport over time. In arcs represent flights ending and out arcs flightsstarting at this airport6 EST abbreviates "earliest state time".Theorem 3.1 The complexity of A-II is bounded by a high order polynomial on the size of the problem.ProofEvery iteration of A-II consists of nd steps, where n is the number of requests and d is the maximum domain size. Each step triggers constraint propagation which takes O(ed2) time, where e is the number of constraints and is bounded by O(n2). So the overall time complexity of A-II is O(kn3d3), where k is the number of iterations. Given that d is connected with n (being the average connectivity of the disjunctive graph of the problem) A-II has time complexity in the order of O(kn6)7.End3.2 Experimental resultsThe table below shows the results of applying A-II to the b3 and b5 data sets. The last column shows the number of iterations before A-II exits with the best solution it can find.Table 3.2 Results of applying A-IIComparing Table 3.2 with Table 2.3, one can immediately see that A-II performs much better than A-I with respect to execution time. For the b3 cases A-II finds the optimal solution in a fraction of the time taken by A-I; and for the b5 cases it terminates in 275 seconds or less yielding very similar solutions to A-I, which times out after half an hour.3.3 Parallel A-II (PA-II)A-II offers little room to exploit parallelism, since it is largely deterministic at each step. Parallelism might be used at step 3.2, where there is search for the best local value for a7 k is not fixed for each problem and it is bound in the worse case by the number of the different cost-solutions for the problem instance. This can be an exponetial factor. However, the probability that k is very small approaches 1 because there are many solutions with similar or worse cost and many dead-ends scattered throughout the search space.variable, but this would not yield any gain due to the very fine grain nature of the computations involved. To exploit parallelism we must modify A-II; fortunately, the revision is both small and effective. Before discussing the parallel algorithm, however, let us consider further the experimental results of A-II (Table 3.1).It will be noted that A-II exits on four of the six problems after only two iterations. There are two possible explanations for this, one being that it finds the optimal solution on the first iteration. Another is that the algorithm reaches a local minimum on the first iteration and the reordering heuristic, used in the second iteration, is ineffective in escaping from this minimum. It will emerge below that A-II has a general problem with local minima. As we shall see, there are much better solutions to the b5 problems which A-II does not find; and this is due to its being “trapped” in local minima.We shall now experiment with two promising fixed variable orderings and a random variable ordering in contrast to heuristic reordering used in A-II. Furthermore, in order to give more chances to the new orderings to converge to a solution, we must introduce a limited amount of non-determinism. Good candidates for introducing non-determinism into A-II are the maintenance requests; first there are few in each problem and second since they already occupy an aircraft, any solution should be lie in the parts of the search space they define. Figure 3.3 outlines the parallel version of A-II, PA-II, with the above modifications.__________________________________________________________________________ PA-II(Y )BeginSelect a maintenance request variable y i from Y, Y <- Y - {y i}for each minimal choice v in Dy i do in parallely i=v;label(Y,Order)Endlabel(Y,Order)BeginWhile Y_{} doselect the next variable y i in Y according to Order, Y<-Y-{y i}Fail = select the minimal value v in Dy i with respect to cost, y i=vIf Fail thenexit with failureEndEnd_________________________________________________________________________________________Figure 3.3 PA-II(Y, Order)Within PA-II we experiment with three static variable ordering heuristics.(1)Order the variables according to the start time of the corresponding requests, withthe order determined by latest start time first (LST).The LST order is promising since it results in the early instantiation of variables involving soft constraints, leaving more flexibility for variables which involve the assignment of aircraft; these variables occur later in the order. This variable order, however, is very likely to reach a dead-end, that is, to fail.(2)Instantiate the variables participating in soft constraints first (SCF).SCF ordering stands in the middle of the LST and EST orderings; minimises the probability of failure while at the same time tries to make visible the effects of the assignments of aircraft to requests.(3)Ordering the variables in Y randomly (RAND) .The experiments with A-I and A-II show that as the problem size increases, there are large “plateaus” around the local minima in the solution space, which have a dramatic effect on the optimisation process. A-I takes long time to escape from these “plateaus”. In A-II the reordering heuristic is likely to follow a gradient that leads to the same solution “plateau”. Here a random variable ordering can provide an effective escape mechanism.3.4 Experimental resultsThe table below shows the results of applying PA-II to the b5 data sets with the three different variable orderings.Table 3.4Results of applying PA-IIFor the RAND ordering the figures represent the average of results on ten runs. A “*” entry indicates that the algorithm failed to find a solution.Note that PA-II, with RAND and SCF variable orderings, finds much better solutions than A-II. Moreover, in some cases PA-II reduces the computation time over A-II by as much as 60%. Let us summarise the results.The performance of PA-II with LST ordering is mixed. It computes the best solution for b5 with a relatively small increase in computation time relative to A-II. However, it fails to find a solution for the b5a and b5b. This was not unexpected since the probability of reaching a dead-end for LST is high. The increase in the computation time may be attributed to the fact that little pruning is achieved and thus a larger amount of time is spent determining the best local choice for each variable. It may also be noted that b5 does not contain any flight delays and hence any tour inconsistencies. LST can be expected to perform much better on such data sets.PA-II with the SCF ordering finds a solution for all data sets and in addition outperforms all other orderings, both in quality and in time. This suggests that SCF is well suited to data sets where there are few soft constraints.。
