ࡱ> ZWXY`! oG^qp$ i5{S.H_v(<f x͜oy)٩ ED-PҤdkuIvpT.KY X.5`-ً.A\]/{!8O>zsx~HC&9$k$/%\';Y>{{l߾vWm?Ϧw/^,v|O{w6Ν|vԿ7 _7yW?q1đf,\c}_C`}d k:%>2mkcڧ潝7/Fߩ'ٟ皱Bsu~&~+i,?WWRh)vk i"?Õ?p]^L~xGWImp"޷6{&+6DߝpjUtrM^Lh>rޤtSD̐9 G9o!zMP 7p4!r7dϛ sXE ȹGiO}g!sמSt^##8fȜtyyʮiNF?O8fȜÚ.*r^Dλ*B?c9\{^cc?Iyasd37fng˨d02j}~V̅ A=:zt{Ą~~fл2w}#As+;aR*n᭍!> WIw{/Rr^yNNggSߠ7?x|6/o5BTqU[4qUoiUWTuU0QU諺'w+K/Wu]_SQSUU_Ս4F:~U cU]Wu_TuXU[KLTY\UbgY!b9ܙ3077ÚxM-i̝9{liXN3w` &Ge5g1̝);ss*nĻ9r3sg`nυ5~1#r3sg`nC55x9sfLaM/&x?c9ܙ30I^{lşq,rf(fbMͿϧhEA965>߷smG}T |?ѻޒlS}$<Ǟަt\K%W*ˈ{Ro)JeĿ9[JUS)w1Kɿ+ˈ-*R *2e`̿_H㪎O0R^A)w'o)WQU ނXAUZ_X cͿVki Oci,w4ZZ*|1Vkk_n͂XAUZ/ZE cͿVki jQ-w4ZZ*|/1Vkk_^܂XA?'_E?-,翅bV P=Z_VB ~[(zK>R >/+osWk5W_{eU.~Y %Ղ?=֒W*:LW %[Gj_5iւW֒W8W1.*Z^A-w'o-WQU ށr_s >)ׁͿNi<:S:G9(uJo:»9x7uJ?=~/:Sz9_Ձҷ5_؁+k_u4:wsIʃXCWz»yx7c Ϳ^i =w54zz+{L5<~8g~7w&>S>5 SqDıCu uFx6N?3^};}b|bGl>'9~i)|h)=9B9h^jgįRQD|йPV:6dGϏJmxjV" {ywxhiv[,ݬ*\\٫`W\2ױZOxΫNG^s*zezgVV^p\/uy:Z flMg 3&^sֆ[{ކ[I׿f{. U-S n:t:X ZekhݖT)%U=Hu_ N7\tТ?Q|ΞFx|/nj)SuJ\k)GK^gV6{Qj)e8/egz}2Y#{>VmzgcŞ6s28YPmz Yi33 uttypP>9=txk}>#UoRG2OX凌'f uCY^?[y_W;0όrh=9;9ys}cX,>[}gRfs}cآy[ 3 C=az ~Cٶx9gc(gV9s9x#ccиk^W3q1v̌ 'Q;fƆݓP32cCa!36 rrCfl(>1606dƆ0cCl<[!361606dƆ0cC<CƂ93cAƜر cر`OƼׁ3 5a6yor0k59g]MA]M4yYXc֒wcJXKn?GZ==-+=h^]AN^+myez3u2?j=]o[l'|κΜj=]oۢ[ 3 `yq0o{8g=Az=xy;x;dޒt zac[j;-H뷎ZK}/ 'e6y;v2i=8y!ہ-6>ggRf!ہm׆POzOr(=߳ 7Ml y'{C y'y;x;eޒ)Tz?Y}?Rn:1FL]3\ j As̠8L߮?w:_[ FilteringWe are able to solve a sub-problem: a method is available CP uses this method to remove values from domain that do not belong to a solution of this sub-problem: filtering E.g: x < y and D(x)=[10,20], D(y)=[5,15] => D(x)=[10,14], D(y)=[11,15]$ HF FilteringrA filtering algorithm is associated with each constraint (sub-problem). Can be simple (x < y) or complex (alldiff)jArc consistency All the values which do not belong to any solution of the constraint are deleted. Example: Alldiff({x,y,z}) with D(x)=D(y)={0,1}, D(z)={0,1,2} the two variables x and y take the values 0 and 1, thus z cannot take these values. FA by AC => 0 and 1 are removed from D(z)[G PropagationDomain Reduction due to one constraint can lead to new domain reduction of other variables When a domain is modified all the constraints involving this variable are studied and so on ... UWhy Propagation?A problem = conjunction of easy sub-problems. Sub-problems: local point of view. Propagation tries to obtain a global point of view from independent local point of view The conjunction is stronger that the union of independent resolutionsEWhy Propagation??A problem = conjunction of easy sub-problems. Sub-problems: local point of view. Propagation tries to obtain a global point of view from independent local point of view The conjunction is stronger that the union of independent resolution To help the propagation to have a global point of view: use global constraints ! @Q ConstraintsPrimitives Global constraints PrimitivesNo decomposable constraints: x < y x y x + y = z x =3, x =y atmost(xarray,#time,val), atleast etc...$h%BP>?Global Cardinality ConstraintGCC(X,{li},{ui}) Defined on a set X of variables, the number of times each value vi can be taken must be in a given interval [li, ui] Example: D(x1)={a,b,c,d}, D(x2)={a,b,c,d}, D(x3)={b,c},D(x4)={c,d}. Values b and c must be taken at most 2, values a and d must be taken at least 1.vD,PpGlobal constraints3 categories: - pseudo-primitives - grouping of constraints based on variables - specific nonbinary constraints (complex primitive ?) Z #Pseudoprimitives|Can be represented by a conjunction of primitives The definition is  closed x + y = z *t: x + y = a, b=z*t, a=b SumEqProd(x,y,z,t): X(C) cannot change Currently, only a few are predefineds C*Grouping of constraints based on variablesJThe semantics of the constraint is defined from primitive constraints which are ensured on a set of variables. X(C) can be changed Ex: alldiff(X) : primitive , vars: X global cardinality constraint: primitives: atmost, atleast sum: primitive exp1 + exp2 = exp3 Currently a lot are predefined&  P/BSpecific constraintsThe meaning is global, and cannot be represented by primitives constraints. X(C) can be changed Ex: path constraint: defined from a graph, a source and a sink. The notion of path is global (connectivity) Global constraints x + y = z * t alldiff(X) path(G) Global constraintsW2 interests: - definition of the problem - strength of CP thanks to Filtering AlgorithmFiltering Algorithmbased on constraints addition (from the simultaneous presence of constraints, new constraints are added) general (GAC-Schema) ad-hoc (integration of OR algorithm)Constraints addition 5 variables: X={x1,x2,x3,x4,x5} domains: [0..4] constraints: atleast(X, 1,1) , atleast(X,1,2) atleast(X,1,3), atleast(X, 1,4) What will happen ? ~P=  Constraints addition 5 variables: X={x1,x2,x3,x4,x5} domains: [0..4] constraints: atleast(X, 1,1) , atleast(X,1,2) atleast(X,1,3), atleast(X, 1,4) atleast(X,1,val): local view: while val belongs to 1+1=2 domains of variable, nothing can be deduced~e=   =Constraints addition H5 variables: X={x1,x2,x3,x4,x5} domains: [0..4] constraints: atleast(X, 1,1) , atleast(X,1,2) atleast(X,1,3), atleast(X, 1,4) atleast(X,1,val): local view: while val belongs to 1+1=2 domains of variable, nothing can be deduced x1=0, x2=0, x3=0 is ok, any combination of 3 variables containing 2 times val 0 is ok. This is stupidI~=   Constraints addition F5 variables: X={x1,x2,x3,x4,x5} domains: [0..4] constraints: atleast(X, 1,1) , atleast(X,1,2) atleast(X,1,3), atleast(X, 1,4) From the simultaneous presence of constraints we can deduce other constraints: if (4 values must be taken atleast 1) then the other values can be taken at most n-4=5-4=1 New constraint: atmost(X,1,0) G~t=  sH 8Constraints addition Done for the global cardinality constraint (the unconstrained values becomes constrained) Therefore, done for the alldiff constraint and permutation (each value has to be taken exactly once)rEConstraints additionThere is no new filtering algorithm Only implicit constraints are added The previous problem is solved! Easy and really interesting: a kind of presolve.9Filtering Algorithmbased on constraints addition (from the simultaneous presence of constraints, new constraints are added) general (GAC-Schema) ad-hoc (integration of OR algorithm).h& GAC-SchemaA generic framework for achieving AC for any kind of constraint (can be non binary). Bessiere and Regin, IJCAI 97 You just have to say how to compute a solution. Manages the incrementality for you (notion of support).$">U GGAC-Schema: instantiation(\List of allowed tuples List of forbidden tuples Predicates Any OR algorithm Solver reentrace>#  GAC-SchemaIdea: tuple = solution of the constraint support = valid tuple - while the tuple is valid: do nothing - if the tuple is no longer valid, then search for a new support for the values it contains a solution (support) can be computed by any OR algorithm H :P/ &ExampleBX(C)={x1,x2,x3} D(xi)={a,b} T(C)={(a,a,a),(a,b,b),(b,b,a),(b,b,b)}CC/ExampleX(C)={x1,x2,x3} D(xi)={a,b} T(C)={(a,a,a),(a,b,b),(b,b,a),(b,b,b)} Support for (x1,a): (a,a,a) is computed and (a,a,a) is added to S(x2,a) and S(x3,a), (x1,a) in (a,a,a) is marked as supported. $ExampleJX(C)={x1,x2,x3} D(xi)={a,b} T(C)={(a,a,a),(a,b,b),(b,b,a),(b,b,b)} Support for (x1,a): (a,a,a) is computed and (a,a,a) is added to S(x2,a) and S(x3,a), (x1,a) in (a,a,a) is marked as supported. Support for (x2,a): (a,a,a) is in S(x2,a) it is valid, therefore it is a support. (Multidirectionnality). No need to compute a solution *K,,"ExamplepX(C)={x1,x2,x3} D(xi)={a,b} T(C)={(a,a,a),(a,b,b),(b,b,a),(b,b,b)} Support for (x1,a): (a,a,a) is computed and (a,a,a) is added to S(x2,a) and S(x3,a), (x1,a) in (a,a,a) is marked as supported. Value a is removed from x2, then all the tuple in S(x2,a) are no longer valid: (a,a,a) for instance. The validity of the values supported by this tuple must be reconsidered. qq>cExampleX(C)={x1,x2,x3} D(xi)={a,b} T(C)={(a,a,a),(a,b,b),(b,b,a),(b,b,b)} Support for (x1,a): (a,a,a) is computed and (a,a,a) is added to S(x2,a) and S(x3,a), (x1,a) in (a,a,a) is marked as supported. Support for (x1,b): (b,b,a) is computed, and update ... $GAC-Schema: complexityCC complexity to check consistency (seek in table, call to OR algorithm): seek for a Support costs CC n variables, d values: for each value: CC for all values: O(ndCC) For any OR algorithm which is able to compute a solution, Arc consistency can be achieved in O(ndCC). V&,aGAC-Schema: complexityAfter 1 modification: consistency in O(CC)) arc consistency in O(ndCC) After k modifications consistency in O(CC) arc consistency in O(ndCC) 6AC Table Constraint: An examplecConfiguration problem: 5 types of components: {glass, plastic, steel, wood, copper} 3 types of bins: {red, blue, green} whose capacity is red 5, blue 5, green 6 Constraints: - red can contain glass, cooper, wood - blue can contain glass, steel, cooper - green can contain plastic, copper, wood - wood require plastic; glass exclusive copper - red contains at most 1 of wood - green contains at most 2 of wood For all the bins there is either no plastic or at least 2 plastic Given an initial supply of 12 of glass, 10 of plastic, 8 of steel, 12 of wood and 8 of copper; what is the minimum total number of bins?.dL Table Constraint: results:Filtering Algorithmbased on constraints addition (from the simultaneous presence of constraints, new constraints are added) general (GAC-Schema) ad-hoc (integration of OR algorithm).}$Semantics of a constraintISpeed-up the search for a support (solution which contain a value (x,a))Semantics of a constraintSpeed-up the search for a support (solution which contain a value (x,a)): x < y, D(x)=[0..10000], D(y)=[0..10000] support for (x,9000): immediate any value greater than 9000 in D(y);Semantics of a constraint^Design of ad-hoc filtering algorithm: x < y : (a) max(x) = max(y) -1 (b) min(y) = min(x) +1Semantics of a constraintDesign of ad-hoc filtering algorithm: x < y : (a) max(x) = max(y) -1 (b) min(y) = min(x) +1 Triggering of the filtering algorithm: no possible pruning of D(x) while max(y) is not modified no possible pruning of D(y) while min(x) is not modified $qSemantics of a constraintuSpeed-up the search for a support (solution which contain a value (x,a)) Design of specific algorithm Incrementalityg Alldiff constraint  Alldiff constraint  Alldiff constraint Alldiff constraint  Value networkA feasible flowResidual graphResidual graphArc consistency$Alldiff results'Color the graph with cliques: c0 = {0, 1, 2, 3, 4} c1 = {0, 5, 6, 7, 8} c2 = {1, 5, 9, 10, 11} c3 = {2, 6, 9, 12, 13} c4 = {3, 7, 10, 12, 14} c5 = {4, 8, 11, 13, 14} clique size:27 Global: #fails: 0 cpu time: 1.212 s Local: #fails: 1 cpu time: 0.171 s clique size:31 Global: #fails: 4 cpu time: 2.263 s Local: #fails: 65 cpu time: 0.37 s clique size:51 Global: #fails: 501 cpu time: 25.947 s Local: #fails: 24512 cpu time: 66.485 s clique size:61 Global: #fails: 5 cpu time: 58.223 s Local: ?????????????&(  2 6(3 'Alldiff constraint  Compute a feasible flow Compute the strongly connected components Remove every arc of flow value 0 for which the ends belong to two different components Linear algorithm achieving arc consistency Idem for global cardinality constraints work well due to (0,1) arcsAlldiff constraint: complexity^After 1 modification: - consistency computed in O(nd) - arc consistency computed in O(nd) After k modifications: - consistency in O(nd k) - arc consistency in O(nd k + nd) . b3",Filtering algorithmOx + y = z*t: conjunction of primitive constraints ad-hoc constraints additionFiltering algorithm`Grouping of constraints based on variables: - constraint addition recommended - ad-hoc algorithmFiltering algorithm1Specific non-binary constraint: -ad-hoc algorithmGood Filtering AlgorithmWhat is a good filtering algorithm ? Or what is a poor one ? (The FA is considered and not the idea of using an OR algorithm) GAC-Schema: - After 1 modification: consistency in O(CC)) arc consistency in O(ndCC) - After k modifications consistency in O(CC) arc consistency in O(ndCC).>>,E!Good or Poor ?UIf O(CC) for consistency then arc consistency: - O(ndCC) poor (reached by GAC-Schema)3"Good or Poor ?cIf O(CC) for consistency then arc consistency: - O(ndCC) poor (reached by GAC-Schema) - O(CC) good!3-#Good or Poor ?If O(CC) for consistency then arc consistency: - O(ndCC) poor (reached by GAC-Schema) - O(CC) good! - and between ? Not so bad ...3LGood FA'Alldiff, global cardinality constraint! Medium FAAlgorithm such that arc consistency is in: O(nCC) (a factor of d is gained): - Global cardinality with cost - Symmetric alldiff (alldiff U {xi =j <=> xj =i}) - sum with binary inequalities - edge-finder$/b-H2 Poor FA ?nI hope there is none :-) Be careful with algorithms that successively try all values of variables (or ranges) < Perfect FA ?Idea: FA has no cost. Complexity of the FA is always the same as the complexity of the consistency checking algorithm All the possible cases are considered and not only the worst case Another possibility O(1) per deletion. Alldiff: 1 modification: if the deleted arc does not belong to the current maximum matching, then consistency in O(1), AC in O(nd): not perfect No perfect FA is known *+G,x'7Incremental algorithms An incremental approach is not always the best. (cf IJCAI-2001 paper on AC-2001) The consequence of the deletions is a good approach if the number of modifications is less than the number of remaining things. Otherwise it is not good. The incremental aspect is quite important for a FA1AAC-2001 vs AC-6BAdaptive Algorithm: Adaptive ACA= v in (j) (|Svj| + 1) B=|D(i)| If A < B then run AC-6 If B < A then run AC-2001 If 2|(j)| < |D(i)| then run AC-6 else run AC-2001 .   rxCClosure or not ?.Is the FA closed w.r.t a property? Consider the values deleted by the FA. The consequence of these new deletions can be: 1) taken into account by the same pass of the FA (alldiff) 2) ignored by the same pass of the FA (Table) 1) no need to call again the FA 2) need to call again the FA It is a choice.//}DAmortized ComplexityQIt is possible to define the complexity in regards to the number of deletions (ex: O(CC) per deletion) Symmetric alldiff: AC: from every var, run algorithm A. Algorithm A can remove some values. AC Complexity: nO(A). Pb systematic. Other FA: pick one variable, run A, and set k=#deletions. You gain k runs! Complexity O(A) per deletion RPPqFuIncomplete algorithms ,The constraint is an NP-Hard problem Try to characterize what is done useful in practice but sometimes difficult to handle: - no fixpoint (largest clique depends on the way the graph is defined): - less constraints can lead to more pruning - debug is difficult global sequencing constraint (fixpoint)$-%, %/Global Constraint and over-constrained problems0/( Real world over-constrained problems: - General purpose method gives poor results after more than 10 years of research RLFAP are not solved, best results obtained from RDS which is a B&B variation. Unable to detect an inconsistency in: x < y, y < z, z < x - WHY ?. ()&/Global Constraint and over-constrained problems0/(Filtering algorithms associated with constraints are needed to solve some problems Relaxation of global constraints is needed Specific filtering algorithms are needed '/Global Constraint and over-constrained problems0/(>Filtering algorithms associated with constraints are needed to solve some problems Relaxation of global constraints is needed Specific filtering algorithms are needed That is: successful ideas for satisfaction problems are still valid for over-constrained problems (cf MAC vs FC CP 96)$ X,  $Over-constrained: Cost of violations<The enumeration of all elements of the Cartesian Product with an associated cost is not realistic. In practice, the cost has always a meaning: x < y: if violated cost=x-y Use this semantic and exploit it: define (x < y AND cost=0) OR (cost = x -y) Define the cost as a variable Domain reduction from cost to var@=r p9Soft Global ConstraintsGTwo different general costs: - Variables based violation cost: the cost is equal to the number of variables that should change their value in order to satisfy the constraint - Primal Graph Based Violation Cost: the cost is equal to the number of binary inequalities violated in the CSP corresponding to the primal graph of C. 6H?n&qVariable based violation costAlldiff({x1,x2,x3,x4,x5}) (a,a,a,b,b) cost = 3 (a,a,a,a,b) cost = 3 General definition can be applied to all constraints that are not pseudoprimitive$!Primal graph based partition costAlldiff({x1,x2,x3,x4,x5}) (a,a,a,b,b) cost = triangle(a,a,a) + pair (b,b) = 3 + 2 =5 (a,a,a,a,b) cost = quadrangle (a,a,a,a) = 6 Can be used for the constraint defined by grouping primitive constraintsSoft global constraintsJFor the alldiff constraint specific algorithm have been designed. These FA are able to take into account a cost variable w.r.t. the defined cost (see paper in CP 01)5Over-constrained problemsMAX-CSP is a global constraint! One satisfiability variable (bi) per constraint A sum constraint on this bi defined a MAX-CSP problem.>$ *) Some results4Car sequencing Sports scheduling All-interval series/Car sequencingopt cap configurations 0 1 2 3 4 5 0 1/2 X X X 1 2/3 X X X 2 1/3 X X 3 2/5 X X X 4 1/5 X #cars 1 1 2 2 2 2 v%T0Car sequencingopt cap configurations 0 1 2 3 4 5 0 1/2 X X X 1 2/3 X X X 2 1/3 X X 3 2/5 X X X 4 1/5 X #cars 1 1 2 2 2 2 Sequences 4,4 or 4,5 or 0,4 or 0,5 are forbbiden% 1Car sequencingopt cap configurations 0 1 2 3 4 5 0 1/2 X X X 1 2/3 X X X 2 1/3 X X 3 2/5 X X X 4 1/5 X #cars 1 1 2 2 2 2 Sequences 2,2,1 or 2,3,0 are allowed Sequences 2,2,3 or 5,3,2 are fobbiden%2Car sequencing0Instances provided by Barbara Smith: 100 cars, 25 configurations, 5 options We proved (in 1997) that: one instance has no solution in 3.5s one instance has no solution in 422s. As far as we know, this is currently the only one method which is able to obtain this result We solve some other open problems 3Sports scheduling4Sports scheduling  ConclusionFiltering algorithm are one of the main strength of CP. Define your model by using them If you write an FA: - try to write a good or a medium one. Do not forget that GAC-Schema exists - take care of the semantics of the constraint and especially the triggering of the FA( ConclusionIncremental algorithms are not always the best. General filtering algorithms are efficient in lack of other algorithms, when some predefined FA exist, use them. Over-constrained problems: use the semantics of constraints9} ReferencesAlldiff constraint: J-C. Regin, AAAI-94 Global Cardinality constraint: J-C. Regin, AAAI-96 GAC-Schema: C. Bessiere and J-C. Regin, IJCAI-97 GAC-Schema with computation on the fly: C. Bessiere and J-C Regin, CP 99 Sequence: J-C. Regin and J-F. Puget, CP 97 Sum with binary inequalities: J-C Regin and M. Rueher, CP 00 Gcc with costs: J-C Regin, CP 99 Symmetric alldiff: J-C Regin, IJCAI-99 Soft global constraints: T. Petit, J-C Regin, C. Bessiere, CP 01 &.  6 $E'G /T   X  ` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd@,3f|?" dd@  " @ ` n?" dd@   @@``@n?" dd@  @@``PR    @ ` ` p>>  (       T&e&e 00`  X Click to edit Master title style!!  8  N&e&e   RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S    NH&e&e ``  p*      N&e&e `   r*      N\2&e&e `   r*    T  <3fd޽h ? ̙33 "Modle par dfautr 0 @(    HWv   P   v  P*    H<e      v  R*  d  c $ ?  e .  HT]v    @ e  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  N\bv   `P  v  P*    Nhv   `  v  R*  H  0޽h ? ̙3380___PPT10.m0~ ph0( p   Hv   P   v  X*   Hv      v  Z*   Nv   `P  v  X*   Nv   `  v  Z* H  0޽h ? ̙3380___PPT10.m@C; Po(  x  c $T{6 p 6 x  c $]6  `   6 7  Z6Ԕ?p j\ 7Jean-Charles REGIN ILOG, Sophia Antipolis regin@ilog.fr88> T  <3fd޽h ? f̙  `8( w 8l 8 C 6 00`  6 l 8 C 6  6 H 8 0޽h ? ̙33  $(  r  S P6 00`  6 r  S $6  6 H  0޽h ? ̙33  h$(  hr h S p6 00`  6 r h S D6  6 H h 0޽h ? ̙33  l$( w lr l S t6 00`  6 r l S H6  6 H l 0޽h ? ̙33  $(  r  S 6 00`  6 r  S 6  6 H  0޽h ? ̙33  $( w r  S H6 00`  6 r  S 6  6 H  0޽h ? ̙33  ( w l  C 6 00`  6 l  C T6  6 H  0޽h ? ̙33  $( w r  S e  00`  e  r  S e   e  H  0޽h ? ̙33  P$(  r  S  e  00`  e  r  S  e   e  H  0޽h ? ̙33  `$( w r  S pe  00`  e  r  S De   e  H  0޽h ? ̙33  p$( w r  S e  00`  e  r  S de   e  H  0޽h ? ̙33   $(  r  S Ce  00`  e  r  S De   e  H  0޽h ? ̙33  $( w r  S Se  00`  e  r  S `Te   e  H  0޽h ? ̙33  ( w l  C Ze  00`  e  l  C P[e   e  H  0޽h ? ̙33  $(  r  S h`e  00`  e  r  S (ae   e  H  0޽h ? ̙33  $( w r  S je  00`  e  r  S be   e  H  0޽h ? ̙33   $( w  r   S te  00`  e  r   S `ve   e  H   0޽h ? ̙33   $( Sz r  S {e  00`  e  r  S |e   e  H  0޽h ? ̙33  0$( w r  S e  00`  e  r  S `e   e  H  0޽h ? ̙33  ,$( X ,r , S  B  # lDԔ??B   `DԔ?`B   `DԔ?`B    `DԔ?@B    `DԔ?@0 B    `DԔ?0 B    `DԔ?@ B    `DԔ?  B   `DԔ?` B   `DԔ?  B   `DԔ?  B   `DԔ?  B   `DԔ? pB   `DԔ? pB   `DԔ?p`  Z@n Ԕ? $The value graph:  Zx{n Ԕ?p   aMD(x1)={1,2} D(x2)={2,3} D(x3)={1,3} D(x4)={3,4} D(x5)={2,4,5,6} D(x6)={5,6,7}H  0޽h ? ̙33'  ` g(  r  S 4n  00`  n    T|n   *x1 x2 x3 x4 x5 x6  T(n   '1 2 3 4 5 6 7   `n  ? J > B  # lDԔ??B   `DԔ?`B   `DԔ?`B    `DԔ?@B    `DԔ?@0 B    `DԔ?0 B    `DԔ?@ B    `DԔ?  B   `DԔ?` B   `DԔ?  B   `DԔ?  B   `DԔ?  B   `DԔ? pB   `DԔ? pB   `DԔ?p`  Ztn Ԕ?  1sB   `DԔ?` B   `DԔ?`` B   `DԔ?@` B @  `DԔ?`  B @  `DԔ?`  B @  `DԔ?`  B @  `DԔ?` `B @  fDԔ?P  Z8n Ԕ? @ 'Default orientationH  0޽h ? ̙33J  p %%(  r  S вn  00`  n    Tn   *x1 x2 x3 x4 x5 x6  T n   '1 2 3 4 5 6 7   `Dn  ? J > B  # lDԔ??B   `DԔ?`B   `DԔ?`B    `DԔ?@B    `DԔ?@0 B    `DԔ?0 B    `DԔ?@ B    `DԔ?  B   `DԔ?` B   `DԔ?  B   `DԔ?  B   `DԔ?  B   `DԔ? pB   `DԔ? pB   `DԔ?p`  Zn Ԕ?  1t  ZXn Ԕ?  1sB   `DԔ?` B   `DԔ?`` B   `DԔ?@` B @  `DԔ?`  B @  `DԔ?`  B @  `DԔ?`  B @  `DԔ?` `B @  `DԔ?` B   `DԔ?` B    `DԔ?0 ` B !  `DԔ?`  B "  `DԔ?`  B #  `DԔ?` B $@  fDԔ?P % Zn Ԕ? @ 'Default orientationH  0޽h ? ̙33   ++*( ry B  # lDԔ??B   `DԔ?`B   `DԔ?`B    `DԔ?@B    `DԔ?@0 B    `DԔ?0 B    `DԔ?@ B    `DԔ?  B   `DԔ?` B   `DԔ?  B   `DԔ?  B   `DԔ?  B   `DԔ? pB   `DԔ? pB   `DԔ?p`  Z B (  `DԔ? @ B )@  `DԔ? @ B *@  fDԔ?P + Z(n Ԕ? @ 'Default orientationH  0޽h ? ̙33f   ..( ry B  # lDԔ??B   `DԔ?`B   `DԔ?`B    `DԔ?@B    `DԔ?@0 B    `DԔ?0 B    `DԔ?@ B    `DԔ?  B   `DԔ?` B   `DԔ?  B   `DԔ?  B   `DԔ?  B   `DԔ? pB   `DԔ? pB   `DԔ?p`  Z0q Ԕ?  1t  Zq Ԕ?  1sB   `DԔ?` B   `DԔ?`` B   `DԔ?@` B @  `DԔ?`  B @  `DԔ?`  B @  `DԔ?`  B @  `DԔ?` `B @  `DԔ?` B   `DԔ?` B    `DԔ?0 ` B !  `DԔ?`  B "  `DԔ?`  B #  `DԔ?` B $  `DԔ? @@B %@  `DԔ?@@B &  `DԔ? @@ ' Zq Ԕ?`nR A(6,6)  ( ZH q Ԕ? A(0,1)  ) Z&q Ԕ?  A(0,1)  * Z*q Ԕ?` A(1,1) B +  `DԔ? @ B ,@  `DԔ? @ B -@  fDԔ?P . Z1q Ԕ? @ 'Default orientationH  0޽h ? ̙33  vn ..( ry B  3 rDԔ??B   `DԔ?`B   fDԔ?`B    `DԔ?@B    fDԔ?@0 B    `DԔ?0 B    `DԔ?@ B    fDԔ?  B   `DԔ?` B   `DԔ?  B   fDԔ?  B   `DԔ?  B   `DԔ? pB   fDԔ? pB   `DԔ?p`  Z(Hq Ԕ?  1t  ZKq Ԕ?  1sB   fDԔ?` B   fDԔ?`` B   fDԔ?@` B @  fDԔ?`  B @  fDԔ?`  B @  fDԔ?`  B @  fDԔ?` `B @  fDԔ?` B   fDԔ?` B    fDԔ?0 ` B !  fDԔ?`  B "  fDԔ?`  B #  fDԔ?` B $  fDԔ? @@B %@  fDԔ?@@B &  fDԔ? @@ ' ZSq Ԕ?`nR 5(6,6) ( ZVq Ԕ? 5(0,1) ) ZXZq Ԕ?  5(0,1) * Z]q Ԕ?` 5(1,1)B +  fDԔ? @ B ,@  fDԔ? @ B -@  fDԔ?P . Zcq Ԕ? @ 'Default orientationH  0޽h ? ̙33   C(  r  S Thq  00`  q    T kq   *x1 x2 x3 x4 x5 x6  Toq   '1 2 3 4 5 6 7   `qq  ? J > B  3 rDԔ??B   `DԔ?`B   fDԔ?`B    `DԔ?@B    fDԔ?@0 B    `DԔ?0 B    `DԔ?@ B    fDԔ?  B   `DԔ?` B   `DԔ?  B   fDԔ?  B   `DԔ?  B   `DԔ? pB   fDԔ? pB   `DԔ?p`  Zyq Ԕ?  1sB   fDԔ?` B   fDԔ?`` B   fDԔ?@` B @  fDԔ?`  B @  fDԔ?`  B @  fDԔ?`  B @  `DԔ?` `B @  fDԔ?P  ZXq Ԕ?  @  orientationB  # lDԔ?PH  0޽h ? ̙33c    ( ry B  3 rDԔ??B   `DԔ?`B   fDԔ?`B    `DԔ?@B    fDԔ?@0 B    `DԔ?0 B   # lDԔ?@ B   3 rDԔ?  B  # lDԔ?` B  # lDԔ?  B   fDԔ?  B   `DԔ?  B   `DԔ? pB   fDԔ? pB   `DԔ?p`  Z8q Ԕ?  1sB  3 rDԔ?` B  3 rDԔ?`` B  3 rDԔ?@` B @ 3 rDԔ?`  B @  fDԔ?`  B @  fDԔ?`  B @  `DԔ?` `B @  fDԔ?P  Zq Ԕ?  @  orientationB  # lDԔ?PH  0޽h ? ̙33     X ( ry B  # lDԔ??B   `DԔ?`B   `DԔ?`B    `DԔ?@B    `DԔ?@0 B    `DԔ?0 B    `DԔ?  B    `DԔ?  B   `DԔ?  B   `DԔ? pB   `DԔ? pB   `DԔ?p`  Zܷq Ԕ? $The value graph:  ZHq Ԕ?p   [GD(x1)={1,2} D(x2)={2,3} D(x3)={1,3} D(x4)={4} D(x5)={5,6} D(x6)={5,6,7}H  0޽h ? ̙33   ( w l  C q  00`  q  l  C `q   q  H  0޽h ? ̙33   $( ry    6Qs  Ԕ?`   (Sja={a,b} Sjb={c} Sjc={d} Sjd={} Sje={e}))Z  6PZs  Ԕ?`J  z"Last=a Last=a Last=b Last=c Last=e<#  <_s  Ԕ? s d If (j)={a,b,c} and (i)={a,b,c} then: recomputation from scratch: 4 operations study of the consequences of the deletions: 6 operations(TvB  NDԔ?  H  0޽h ? ̙33  $(  r  S xis  00`  s  r  S is   s  H  0޽h ? ̙33   ( w l  C rs  00`  s  l  C @ss   s  H  0޽h ? ̙33  0( w l  C xs  00`  s  l  C xs   s  H  0޽h ? ̙33  @ $( w r  S ćs  00`  s  r  S s   s  H  0޽h ? ̙33    $( w  r   S s  00`  s  r   S ĕs   s  H   0޽h ? ̙33    $(  r  S s  00`  s  r  S os   s  H  0޽h ? ̙33   @ $(  r  S xs  00`  s  r  S Ls   s  H  0޽h ? ̙33  P $( w r  S s  00`  s  r  S Įs   s  H  0޽h ? ̙33  ` $( w r  S s  00`  s  r  S (s   s  H  0޽h ? ̙33  p $( w r  S s  00`  s  r  S s   s  H  0޽h ? ̙33   $( w r  S `s  00`  s  r  S  s   s  H  0޽h ? ̙33   $( w r  S s  00`  s  r  S s   s  H  0޽h ? ̙33  @ X( w Xl X C s  00`  s  l X C s   s  H X 0޽h ? ̙33  p $( w $l $ C s  00`  s  l $ C s   s  H $ 0޽h ? ̙33   <,(   <r < S @s  00`  s   <  6s 1   s  pB < HDԔ?@ pB < HDԔ?  H < 0޽h ? ̙33T   @(  @r @ S s  00`  s   @  6xs 1   s  pB @ HDԔ?@ pB @ HDԔ?  jB @ BDԔ?  pB @ HDԔ? vB @@ NDԔ?`H @ 0޽h ? ̙33  z  D(  Dr D S X v  00`  v   D  6, v 1   v  pB D HDԔ?@ pB D HDԔ?  pB D HDԔ?  pB D HDԔ? vB D@ NDԔ?`pB  D HDԔ?  H D 0޽h ? ̙33   H$(  Hr H S ,v  00`  v  r H S v   v  H H 0޽h ? ̙33j   L(  Lr L S !v  00`  v   L0 6A ?   v n L Z#v Ԕ?P  n teams and n-1 weeks and n/2 periods every two teams play each other exactly once every team plays one game in each week no team plays more than twice in the same period!H L 0޽h ? ̙33     P4(  Pr P S ,-v  00`  v   P0 6A ?   v H P 0޽h ? ̙33   $( w r  S h1v  00`  v  r  S <2v   v  H  0޽h ? ̙33  `  ( w  l   C  9v  00`  v  l   C 9v   v  H   0޽h ? ̙33  H( w Hl H C p@v  00`  v  l H C DAv   v  H H 0޽h ? ̙33& 0 0  (  X  C    v   S wv  @  v  " H  0޽h ? ̙33' 0 P  (  X  C    v   S }v  @  v  " H  0޽h ? ̙334 0 0 T (  TX T C    v  T S v  @  v  " H T 0޽h ? ̙33x uǻgwoO,NYC-Kٵ$q8Y (b78ؕT*U@(`rRP&$Tc;zz\ Bwߞy=~=W;/òe)Cʘ?;==eO@s(mqfP haATv  %6J*{AA.]ZZ j]ZZAUAA@Ak@[@]nPkA hAfBzFMnݒ8>C퀊à]wm_ .HٽP0^YwXA/?1S??30~6*3i-P[]l5\%0 1PZ8NDwewqǎF%>kwgM܍i|~jrs2-׾so?>8]`N- +vgyVky5ha&o1H &`VQrΒe\H<aD={RqСnv'Ŭ̓MRmi`8s /@_ʜLD5jDE""р/fz1*c> 賠@~aI$諠S@gb-y߃tϠA"DWOA?cj@@ւ6pq .{%L<=s-tmPq^vW[E|]ڛ&Xe5erٜf.=pbFнHA+bBWX,7Y|[kqQ8cAﱃ6e-as:RٽISׯ:84?# p%8>V hA 2znsXScM~I$t_rSw˕,[ZjZjF08ۀ?E*8Gl߉}4l 趪ŠvۂՍlh_HeК6#R~,lCfwx>Lb}D0ލM-DKWti)[ ދ5%ʚ8: -VYΌ[|NL-΃{KoZq"Glãîا}޻pO(%#kՖ5>+py Zae9#"r:>k5Kߘk?0ٯ` +ثb2H\gOC[XPy⚟C.H_OsՂRLM/Gn>~-({܏e>EnSBOkyXLM/i,s%)&J_ljew X6hE Ayk\>'rl''sM\q^IO96ic(&?}<8v٤K-4Hkeq}QUl9 y-L4<~x@{ע :oߌ+bǰ%a ǘ- YnENmj:{ZgTWZ֪ۼVZMp"?}<+5DRqd4H뼀隖\[@>ow[wIߒο=DPR1=4-);?4-Ro_Z[coIzgPߒοLgRk5AK:4-)[ [נVT/Adu AuoW$cC_ q0q"u2:qq18H_ǀ_̿A` yE2: :du bTcT7+1_!c;;ȿq^̿:ȿXXALV"eߢTĹL[4+8/v2o` -xY&-gEEH|hp. "^_[BbĿ=oEߊ¿Ӭh[XEߊ¿=h[Z[Qw~h[ט*V*Vt5&͊ƿ_Wh[coEzRZAEߊ¿Πʿ jL5]]_p5/\/\_0qk.K_ q1q]8Gȿ.]88Eu c+&:ȿ.]Eu 9"du EE5!y5Q]Q]_0nm5]]_0V}ο.K_ w1wݺ3Y28Ml0?q.$o`(0I߲]1z̿e1$YǮI2 Ɩ2#d-\e'[6x}Mߚƿ5_z"mk7i[טjkt5ƿ5秧ƿ5oMoM_i[Sw~i[coMUjt5^+i[ST$S= zz7Ϋ3_#g_x_xȿq^̿zȿ=ØCd CQQoW%gG_ v0v*==2zU3Q=Q=8J_π=_̿A\a\!yU2z!zd bqcq7Ϋ7Y'-o.v>>|tyZ9 vQ5#3cF'?M N1N1U81 Ϳ>{Xٞ+% hxʦDc|JSؚF#|H)i 'gk9 K>UOMszz&w͖?b Oi^>F-^ayiwGle-ʤO&2/巴IwW$d %|Hz}eN|@%vꕙ2?޷G'~eMԹ7/sz_ ]to~{efx;}RKd0 @wgԾOQQV>I>'シߏ&ۢXxK}$]7]{.+-3hiV*:DՠFPwo4PV>emz[oh-t>+;{#,Ȁ؂VʝjyuK&VvWpM -OXuuwr,9Q'A@w%Ǝ{AA.c˟}軠~@`Y Zth]Nfh|Ƭ dēy߹7yzk W2츸FxcKMʼnb=6y ͬ=aEZ(cl4ދDX<4GM9\>?W<ќ_rT_1M킲-0/_{xg׿6Oleb{~ɻȂᓉ#L>N<\<L>],{4ţE+\nm[\T!˛{ O5.xWHkWu9<2vg^utGEYL~W?9g[;mn" <  be8QRK-RK-RK-R;ߖc͞G뷊Ϸ˟kGXgNu^ldrJ^/gL6bMN&jfr~&׀~uG@"jL &T1Ta7ﲙk=bHʹ{;f\SQV.ibakZ~zТVYؚ{G5w k3]:~t'n̓X:ϰ^6X7낽fxoVa;ak|n`ZjZjZjy?x]kpu>$Dʔ,ˎ#˴L pH3ă8dTd9u3MIM Lb't:5&jmqd܌d<IȌiN&?ǸU=gjΥ1{8{v{ww/hƟK Ԕ>}iuu6򮒋=Vp@BF ٍHԍעnBu37FnA u+ͨnCu6(@DBu#1^ \&QGQS;PӨcwZ܅N]8ߋP@=zckr ^8y (!r>Hܽy΅;qՊhG*)ag<6YI8:G$S;nlYx<]5OK"Lཉm_ڋe]y"9a}w;g?17PsSΘcʽ Mf28 GeG0b6p+d;!4 5)=^_w^} h {QY9<Ɨø>z|NmQ-ϡL ReKN JQlj>.dwAyi}2/ H|:!@nWn9*vvo~r, WvHGay Ncdpi\1Il"A?D@apEYJJl7K_ ,}vʴmskܾ۰-~G?F4]T#TZ\B,#}c-/OwN],%35_|_|_|w&rq Ļ\AܧESov=k/a/7arCBμm6#JnhFǹQZ7!aRgّA,q9Is t+Zwi!ʧs*mYoǶ s/͠om[YK_ཁrSO[uCe@ b|Qp'l<:=;u?27;yJ)7jZBMd1<<\fjr4GwAmuX^&_!>4SV ~Z?:}ر֞Føֺ,B-0x͚vVI:t6kO*Τk]Fj!d._COtj)3`̰* vLOhB/xlY3@g,2G7&HQaO M0<t6̔*ʎῪׄ&ޱen7KPaǻP؎-'",I>#-ڿQj%& aA;~D`?[6a,AfuFk;m3cH m h,mՋ"̅=(#Qá-G/cVđ[67lQ6G4x=xU5G>ׄeslTQ c؋*eATyͱQ>4iӭDD.dWd5ja҇P>4Od2x?}9ے%`r7l[mVOoͺfmjb#JF(ԳO^\3n0{pbtr5fiK帑HYt=b0FaUSapV 8g /eTnkS{lo=^6l2A1^6L17ׄ6*s{Q>s,lK|+X88W}cqÜg\˩q? ]D3BўѴ>Y8HO/s90؜XeL|8/xl liplNq,2&~neslö؜Ƕʷf19pXeކe.h}Aa¶ނY3韏%VK>YP_j˱%ǖ1!ͱ%űEE98ѽ8\QqlQıE -*-9yQqlQıE -*-9[E[EűE|#-jplQqlͱE|.|.*-q/4^R.9Yͱ% T[蓒jr[x88?'Vpq"Y:Lh_8W˧g+g)ȳ5lYwe[ͳe -+aQzفValYgˊgy1/g g<[V<*#kmyvͳ UlhࠢيFTTlóuų}HĴ+hC"JhlóuųaH g;pV<[ٺYeL|X/xl+lkl],2&~~elöٺ϶ʹf1spV< (.Ϯh`EyFxGy,g)AuGp,Y$R/YHEl oW:nװ",/3Et2|l~_tنY9e\9MkmeIjWa;¶^Y3韏^ VK>Uh˳ &RGDIh˵YfR὾fok-ɵcbt(NXW:|mV-I5No'47_c˲vBo'0)cc~ǖeN(偌g%buw(5@9@D^5w/-6yŷYTԖo=|E$vY9_J'C;FkNSgϊɼ+"ur-񷤁% 2u4XwI.2&>/xll]`%źl1mɑm66ll]`%ź2YL _rdxMml]vm?ccCU#*eY#U6:<#QUQe_栆株UU5AˊoxeWkmt^4[ғ܏.-|4ߗ&d|Zz8 l>j.asC.kڮUk뫮VK$?`,)77a׭.YwY[\KVqd~DN6ْonǽmo| ֲ]_8%H<C($x]Z3zBxa؈Ar1h%Ǎ4q5icjʈNGx*c3㸏AAAV0v1+HrVЈ%҆V#u0z{z/ ̷,CQ!?CBC݂zͨP#QAajuLA7c߀#.(m|@\? >ٝЫ79M0t 9{ccm.:xGZӇ ׼={QBc~NCBFE=okɡ.>8Pe?F}+EԿB]B&x/\DJ]w:GpjϝS`mGX-}r~. L0Q+j]jS޳s/p׌ 5a |p-wPo}oC=h_^DO# ~!|F{Z=BoBNN%wӞu }^:fg'gm*+X*n|,^+??0if*מt/}_|_|_|jK3XkD]_[ՖwsI'_~ߟ7Mrْ564q\# Orr,_C]rΈ-s*@lW|hn09J.,l1 \铅m*t̔rH-cʪvܣj a78܃1\a#-cÿ=4%;p{$3[cXs>_|_|_|hr˖+G9= F tLU,iЯ`lXDP0 0|@hT,`@@,%3<%Vral׵s /S3pkWC  C$68k"`TP? J Oh+'0) px     ,8@No Slide TitleStanislas BerteloottanDpartement Informatiquei86aMicrosoft PowerPointque@@HF@Y݁@o@ nM G'g  "  --- @ !$---- @ !$---- @ !<---- @ !S---- @ !h---- @ !v---- @ !---- @ ! ---- @ ! ---- @ ! ---- @ ! ---- @ ! ---- @ ! ---- @ !---- @ !---- @ ! ---- @ !---- @ ! ---- @ ! ---- @ ! ---- @ !---- @ !---- @ ! ---- @ !&---- @ !,---- @ !2---- @ !8---- @ !=---- @ !C---- @ !K---- @ !O---- @ !U---- @ ![---- @ !a---- @ !f---- @ !l---- @ !r---- @ !v---- @ !{---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ !---- @ ! --~-- @ !--|-- @ !--z-- @ !--x-- @ !--v-- @ !%--t-- @ !*--r-- @ !.--p-- @ !3--n-- @ !9--l-- @ !=--j-- @ !B--h-- @ !H--f-- @ !N--d-- @ !S--b-- @ !W--`~-- @ !\--^|-- @ !b--\|-- @ !g--[z-- @ !k--Yz-- @ !o--Wx-- @ !t--Uw-- @ !z--Sv-- @ !--Qu-- @ !--Os-- @ !--Mr-- @ !--Kq-- @ !--Ip-- @ !--Go-- @ !--En-- @ !--Cm-- @ !--Al-- @ !--?k-- @ ! --=j-- @ !--;i-- @ ! --9h-- @ !--7h-- @ ! --5g-- @ ! --3f-- @ !---'@Times New Roman-.  2 1 ."System4i-@Times-. 3f"2 SGlobal Constraints5&&!2&&!%.-@Times New Roman-.  2 !gJean .-@Times New Roman-.  2 !- .-@Times New Roman-. 2 ! Charles REGIN   .-@Times New Roman-. 2 IT ILOG, Sophia     .-@Times New Roman-. 2 I Antipolish  .-@Times New Roman-. 2 qregin@  .-@Times New Roman-.  2 qilog .-@Times New Roman-.  2 q/. .-@Times New Roman-.  2 q8fr .-՜.+,0     5 Affichage l'cran ILOG S.A. aU]A cTimes New RomanTimesSymbolArialModle par dfautMicrosoft Word DocumentGlobal ConstraintsPlanConstraint Programming&Problem = conjunction of sub-problems Filtering FilteringArc consistency PropagationWhy Propagation?Why Propagation? Constraints PrimitivesGlobal Cardinality ConstraintGlobal constraintsPseudoprimitives+Grouping of constraints based on variablesSpecific constraintsGlobal constraintsGlobal constraintsFiltering AlgorithmConstraints addition Constraints addition Constraints addition Constraints addition Constraints addition Constraints additionFiltering Algorithm GAC-SchemaGAC-Schema: instantiation GAC-SchemaExampleExampleExampleExampleExampleGAC-Schema: complexityGAC-Schema: complexityTable Constraint: An exampleTable Constraint: resultsFiltering AlgorithmSemantics of a constraintSemantics of a constraintSemantics of a constraintSemantics of a constraintSemantics of a constraintAlldiff constraintAlldiff constraintAlldiff constraintAlldiff constraintValue networkA feasible flowResidual graphResidual graphArc consistencyAlldiff resultsAlldiff constraintAlldiff constraint: complexityFiltering algorithmFiltering algorithmFiltering algorithmGood Filtering AlgorithmGood or Poor ?Good or Poor ?Good or Poor ?Good FA Medium FA Poor FA ? Perfect FA ?Incremental algorithms AC-2001 vs AC-6 Adaptive Algorithm: Adaptive ACClosure or not ?Amortized ComplexityIncomplete algorithms 0Global Constraint and over-constrained problems0Global Constraint and over-constrained problems0Global Constraint and over-constrained problems%Over-constrained: Cost of violationsSoft Global ConstraintsVariable based violation cost"Primal graph based partition costSoft global constraintsOver-constrained problems Some resultsCar sequencingCar sequencingCar sequencingCar sequencingSports schedulingSports scheduling Conclusion Conclusion References Polices utilisesModle de conceptionServeurs OLE incorporsTitres des diapositives]0_Lv Dpartement InformatiqueDpartement Informatique  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./013456789:;<=>?@ABCDEFHIJKLMNPQRSTUV[Root EntrydO)PicturesCurrent UserOSummaryInformation(28)PowerPoint Document( LDocumentSummaryInformation8G