ࡱ> (e >/ 0|DTimes New RomanȷȷԳ0 0DArialNew RomanȷȷԳ0 0" DWingdingsRomanȷȷԳ0 00DSymbolgsRomanȷȷԳ0 0@DCourier NewmanȷȷԳ0 01   @n?" dd@  @@`` c   ! 4f#)/&&') fCC?pHF)LfC@?@B^&ab4c/f$(2?C???&@%()!)LC:Cf$(2?C???&@%C()!)G LCAC;56;78'9!:;<=>?%@BD+E$)F,HIJKLMNfOPQ(RS2TU?VWXYZ[\]^_`4     ' !"#$%4&'()*+,-.C/0;123  1? 33ff@33338 g4adad 0ppp@ <4!d!dȷ<4BdBdȷvn___PPT9Pz<DCDSD\DbD=DD&D6D? %O =M'Constraint Programming and Local Search'Filippo Focacci, Andrea Lodi CP -AI-OR 02, School on Optimization2C$4NOutline/Introduction A didactic optimization problem (dTP) Motivations for cooperation A zoo of CP / LS hybrids Sequential combination Master / sub-problem decomposition Improved neighborhood exploration Neighborhoods in CP Large neighborhood search Local moves over a heuristic Local moves during construction v3ZZZ ZZ3  $.>What this tutorial addressesSolving large hard combinatorial optimization problems Systematic description of ways of combining LS and CP techniques Goal: provide a check-list of recipes that can be tried when tackling a new optimization application Illustrated on a didactic problem "ZZ?/When should you enquire about CP / LS hybrids ?/When you have: A large complex optimization problem No solution neither with CP nor with LS The problem specification may change over time Best in case of strong execution requirements Limited planning resource On-line optimizationT|./|./@(When can t it help ?When modeling is the issue When optimization is the single difficulty When thousands of man.year have been spent studying your very problem => useless for solving a 1M node TSP 2%&AComparing CP and LSConstraint Programming Solves complex problems Models capturing many side constraints Solves by global search and propagation Local search Solves problems with simple models Efficiency: quick first solution, rapid early convergenceTg ]g ]BOpportunities for collaboration  cExpected combination of : Generality (solve complex problems) Nice modeling Generic methods from the model Easy to add/modify constraints Efficiency (solve them fast) Initial solution Quick convergence Address both feasibility and optimization issues keep constraints hard Difficulty to combine: monotonic reasoning (CP) non-monotonic modifications (LS)Z$ZLZZ$Z1ZZZ;Z$L$1  ;cCOutline1Introduction A didactic transportation problem (dTP) Motivations for cooperation A zoo of CP / LS hybrids Sequential combination Master / sub-problem decomposition Improved neighborhood exploration Neighborhoods in CP Large neighborhood search Local moves over a heuristic Local moves during construction 5ZZZ ZZ (f  $0D!A didactic transportation problem""(!Collect goods from clients Set of trucks located in a depot Each truck can carry two bins Each bin may contain only goods from the same type Clients have time window constraints Bins have capacity constraints(EA simple model for dTPi,j {1, ..., n}: clients (their locations) k {1, & , M}: trucks h {1, & , 2M}: bins l {1, & , P}: types of goods      FModelRMinimize totCost = Sk=1M costk On "k, costk 0 truckk: UnaryResource(tt,c,costk) "h, collectsh [1 .. P] "i, starti [ai .. bi] servicei : Activity(starti,di,i) visitedByi [1 .. M] collectedIni [1 .. 2M]$ZZZ  "              #        G Model (2) \Subject to "i, servicei requires truck[visitedByi] "h, Si | collectedIn i = h qi C "i, collects[collectedIni ] = typei "i, visitedByi = collectedIni / 2   $$        H A CP approach Strengthen the model Add redundant constraints Add global constraints Add constraints evaluating the cost of the solutions Symmetry breaking (dominance) constraints Find a search heuristic Variable / value orderings Explore part of the search tree through Branch and Bound\ZZZTZTI A CP approach Redundant models for stronger propagation Example: redundant routing model "k, firstk [1 .. N] "i, nexti [1 .. N+M] succi [{} .. {1, & , N}] multiPath(first,next,succ,visitedBy) costPaths(first,next,succ,c,totCost) "i,j, j succi (visitedByi = visitedByj starti > startj)fK "  "  "!U  """* "*""*"*"N   *     JSolving through CPInstantiate visitedByi Rank all activities on the routes ( instantiate nexti / succi ) Instantiate starti to their earliest possible value94 " "Z 1!KDifficulties with CPPoor global reasoning Poor cost anticipation Goes backtracking forever As propagation is strengthened, the model is slowed downLA local search approachTwo possibilities: Work in the space of feasible solutions Accept infeasible solutions by turning constraints into preferences Choose the first method, by adding, if needed, extra resources (trucks and bins)6lQlQMLocal search for dTPGenerate an initial solution Select clients i in random order Assign it to a truck that has a bin of typei , or to a truck that can be added an extra bin of typei Move from a solution to one of its neighbors, in order to improve the objectiveP72P6d2ONNeighborhoods for dTPZNode transfer: Change values of visitedByi and collectedIni for some i Bin swap: Select bins h1, h2 on trucks k1= h1/2, k2= h2/2 For all clients i, collectedIni = h1 collectedIni = h2, visitedByi =k2 collectedIni = h2 collectedIni = h1, visitedByi =k1 Swap collectsh1 and collectsh26Z:Z ZZ;ZZ             ]    #O Neighborhoods k-opt: select i1, i2, i3 such that visitedByi1 = visitedByi2 = visitedByi3 Exchange edges: Replace nexti1=j1, nexti2=j2, nexti3=j3 By nexti1=j2, nexti2=j3, nexti3=j1 hUL           P Driving the local search process Main iteration: Until a global stopping criterion is met: generate a new initial solution perform a local walk Each walk: Until a local criterion is met: Iterate the neighborhood, until a neighbor satisfying all constraints as well as the acceptance criterion is found Perform the move Z*Z5Z Z ZZ*5 QDifficulties with LSGenerating a good feasible first solution becomes harder Explore neighborhoods takes longer: constraints checks is less interesting: fewer valid nodes more local optima appear&OaOaR Conclusion BNeither of the  pure approaches works Need for hybridization with other techniques Try a cooperation between CP and LS Expect to retain : Good sides of CP: handling side constraints, building valid solutions, systematic search Good sides of LS: quick easy improvements, quick convergence.dT7T7I.!SOutline/Introduction A didactic optimization problem (dTP) Motivations for cooperation A zoo of CP / LS hybrids Sequential combination Master / sub-problem decomposition Improved neighborhood exploration Neighborhoods in CP Large neighborhood search Local moves over a heuristic Local moves during construction 3ZZZ ZZ3f  f  $.TSequential combination: LS-CPUse local search for the beginning of the optimization descent  switch to CP at time t0YZYXU Discussion ;A good idea When the feasibility problem is easy For time-constrained optimization But, the switch from LS to CP is not immediate CP starts with a good upper bound, but without no-goods On the didactic Transportation Problem (dTP) Lack of good lower bounds => Systematic CP search is stuck near the optimal region  G/8-9 G/8-  9    $UVSequential combination: CP-LSBuild a first feasible solution with CP Greedy heuristic Try to improve it through LS Constraints can be softened to support dense neighborhoods `(;(;WGreedy insertion algorithm XGreedy insertion for dTP Y Discussion CP then LS: can be interesting for dTP In particular in case of tight side constraints One-shot use of CP: as long as no valid solution has been found, we look for one Guarantees than during LS, a valid solution is always availableL'0}'0}$"ZA systematic combinationSolve the problem through CP (global search tree) Try to improve each solution found through local search Improve the optimization cutsZ[ Discussion Local moves should change the assignment of early variables Avoid visiting the same region as with backtracking Especially interesting in case of incomplete search CP provides a set of diversified seeds for local searchL@448@448\Outline/Introduction A didactic optimization problem (dTP) Motivations for cooperation A zoo of CP / LS hybrids Sequential combination Master / sub-problem decomposition Improved neighborhood exploration Neighborhoods in CP Large neighborhood search Local moves over a heuristic Local moves during construction 3ZZZ ZZ3  #  f  $.]"Master / sub-problem decomposition##("Idea: identify two sub-problems and solve them by different techniques Master problem Induced sub-problem Decomposition: the sub-problem can only be stated once the master problem is solved. BG$UG$V^Purpose of decompositionDecompose into easier problems Smaller size Simpler models Well known structure Traditional approach with exact methods (Dantzig, Lagrangean, Benders)61G1G6y  _A decomposition on dTPRMaster Problem: Assignment of clients to trucks (visitedBy) Induced sub-problem: Traveling salesman with time windows Algorithms: Assess a cost for each client (e.g. distance to neighbor), solve assignment with some method Solve small TSPs with CP Analyze TSPs, re-assess client cost and try improving local moves on the master problem. Z,ZZ%Z ZZZ! %     H1 Ma Discussion Decomposition makes the problem easier to solve Estimating the cost in the master problem may be difficult Try local changes on the evaluated cost of the master problem improve subsequent optimization (feedback from the sub-problem) >Z@ZZ@bOutline/Introduction A didactic optimization problem (dTP) Motivations for cooperation A zoo of CP / LS hybrids Sequential combination Master / sub-problem decomposition Improved neighborhood exploration Neighborhoods in CP Large neighborhood search Local moves over a heuristic Local moves during construction 3ZZZ ZZ3:  "  f    fX  $.cConstrained local search<Small neighborhoods A neighbor solution S1 can be reached from a given solution S* by performing  simple modifications of S*. Examples: Choose two visits i1 and i2, remove i1 from its current position and reinsert it after i2 Choose two visits i1 and i2 and exchange their positionsxa 1dConstrained local searchNode Exchange Choose two visits i1 and i2 assigned to different trucks and exchange their positions Accept the first exchange improving the costfheNode Exchange: version 1 Procedure exchange(P,S) forall nodes i1 forall nodes i2 | (svisitedByi1 svisitedByi2 ) exchangeInstantiate(P,S,i1,i2) // check feasibility and check cost function if (propagate(P) && improving(P,S)) storeSolution(P,S) resetProblem(P) exit iterations // reinitialize the domain variables resetProblem(P) ZhZ5ZZZ      !  533r33(33 t *hDfNode Exchange: version 1 Procedure exchangeInstantiate(P,S,i1,i2) // exchange i1 and i2 next[sprevi1] = i2; next[i2] = snexti1; next[sprevi2] = i1; next[i1] = snexti2; // restore the rest forall k {i1,i2,sprevi1,sprevi2} next[k] = snextk;$#  33333333            33      > (gNode Exchange: version 1  hNode Exchange: version 2 Add inlined constraint checks Procedure exchange(P,S) forall nodes i1 forall truks k | (k svisitedByi1 ) if (not binCompatible(P,S,svisitedByi1,k)) continue forall nodes i2 | (svisitedByi2 = k) if (not timeWindowCompatible(P,S,i1,i2)) continue if (not improving(P,S,i1,i2)) continue exchangeInstantiate(P,S,i1,i2) // check feasibility && check cost function if (propagate(P) && improving(P,S)) storeSolution(P,S) resetProblem(P) exit iterations resetProblem(P); // reinitialize the domains8Z,Z9ZZf    f ff f   *fffff ffffff f!  93333+ % 0Ep!iNode Exchange: version 2  =Outline0Introduction A didactic optimization problem (dTP) Motivations for cooperation A zoo of CP / LS hybrids Sequential combination Master / sub-problem decomposition Improved neighborhood exploration Neighborhoods in CP Large neighborhood search Local moves over a heuristic Local moves during construction 3ZZZ ZZ3\    fX  $.nNode Exchange: even more CP(CP based neighborhoods The neighborhood of a solution S for a problem P is defined by a constraint problem NP(P,S) :: [{I1,& ,In},{C1,& ,Cm}] Each solution of NP represents a neighbor of S for PZUZ#Z6Zm    6oNode Exchange: nhood model(Variables: I::[0..n-1], J::[0..n-1], DCost::[-..0] I, J are domain-variables representing the nodes i,j that we want to exchange. Constraints: // neighborhood cst I > J svisitedBy[I] svisitedBy[J] next[I] = snext[J] next[J] = snext[I] next[sprev[I]] = J next[sprev[J]] = I // interface cst forall k, (k I k J) next[k] = snext[k], visitedBy[k] = svisitedBy[k] 4ZQZ ZZ.2 33Z33A$w      !  pNode Exchange: nhood model(aDCost represents the gain w.r.t S: DCost = cost[sprev[J], I] + cost[I, snext[J]] + cost[sprev[I],J] + cost[J,snext[I]] - cost[sprev[I], I] - cost[I,snext[I]] - cost[sprev[J],J] - cost[J,snext[J]] // improving cst DCost < 0 Search (explore the neighborhood via tree search): instantiate(I) && instantiate(J) $ZZ4Z!ZZ# 33 4!" [qNode Exchange: nhood model ( rNode Exchange: nhood model ( sNode Exchange: nhood model ( tNode Exchange: nhood model ( u Local Search via solution deltas!!$QGoal: avoid instantiating and un-instantiating ALL problem variables while moving from one neighbor to the other A neighbor is identified by the modification over the original solution S. This modification is defined solution delta. A neighborhood is an array of deltas. The exploration of the neighborhood takes place on a tree search.hrZZqhBw&LS via solution deltas : Node Exchange''$Procedure exchange(P,S) SolutionArray neighborArray forall nodes i1 forall nodes i2 | (svisitedByi1 svisitedByi2 ) Solution delta = {(next[sprev[i2]] = i1), (next[i1] = snext[i2]), (next[sprev[i1]] = i2), (next[i2] = snext[i1])} neighborArray.add(delta) exploreNeighborhood(P,S,neighborArray) ,Z`ZZCZZ*            $     C  # E+ +   x0LS via solution deltas: explore the neighborhood11 y3Exploring the neighborhood through solution deltas44  z Local Search via solution deltas!!$ FOutline/Introduction A didactic optimization problem (dTP) Motivations for cooperation A zoo of CP / LS hybrids Sequential combination Master / sub-problem decomposition Improved neighborhood exploration Neighborhoods in CP Large neighborhood search Local moves over a heuristic Local moves during construction 3ZZZ ZZ3p    f>  .Large neighborhood searchIdea: partition the variables of the current solution into two subsets A fragment: assignments are kept as they are A shuffle set: assignments may be changed 6GWGW! Large neighborhood search on dTP!!(From a solution  Large neighborhood search on dTP!!(Select a shuffle set ! Large neighborhood search on dTP!!(Example on dTP " Large neighborhood search on dTP!!( %Large neighborhood searchExploring the neighborhood#Selecting shuffle sets+Select a set: large enough to introduce enough flexibility small enough to reduce the overall problem of inter-dependent variables of ill-assigned variables (an improvement can be expected) Vary the types of sets that are shuffled Vary the size of sets that are shuffled variable neighborhood searchTQQ$Shuffle sets for dTPLA set of clients that are Within short distance of some specific client Visited by the same truck Sharing a common type of goods Visited within a common time frame & 2%A few hints for LNS with CP Use incomplete tree search to speedup the sub-problem solution (e.g. LDS) Use strong constraint propagation to reduce the neighborhood exploration Compute relaxations to prune non-improving neighbors Rather switch neighborhood than fully explore one by backtracking , v&Outline/Introduction A didactic optimization problem (dTP) Motivations for cooperation A zoo of CP / LS hybrids Sequential combination Master / sub-problem decomposition Improved neighborhood exploration Neighborhoods in CP Large neighborhood search Local moves over a heuristic Local moves during construction 3ZZZ ZZ3    f!  $.'Local moves over a heuristicLS is defined as variations over a solution. LS can also be applied over an encoding of a solution For a greedy CP method, the search heuristic itself is an encoding Idea: instead of exploring the whole tree, explore variations of the constructive heuristic.*dZZd(Local search over a heuristic,      Two family of methods Local moves over a value ordering heuristic Restricted candidate lists GRASP Discrepancy based search Local moves over a variable ordering heuristic List scheduling heuristics Preference-based programmingl,:/8,:/8  )/Local search over the value selection heuristic *Restricted candidate list.At each choice point a function h is evaluated for all possible choices: the k  worst choices (with high value for h) are discarded the choice that minimizes h is considered as preferred decision the preferred decision is taken, the remaining choices are taken upon backtrackingI (&*x+Restricted candidate list ,Restricted candidate list -GRASPp Greedy Randomized Adaptative Search Procedure At each choice point a function h is evaluated for all possible choices: the preferred decision is chosen by a random function biased towards choices having small value for h the preferred decision is taken the process is iterated until a stopping condition is metFyZZydZ .GRASP /Discrepancy based searchIdea: good solutions are more likely to be constructed by following always but a few times the heuristic during search, count the number of times the heuristic is not followed (number of discrepancies) a maximal number of discrepancies is allowed when generating solutions in the tree.BiiR V0Discrepancy based search 1%CP + some LS: putting things together&&$Example:2%CP + some LS: putting things together&&$Example:32Local search over the variable selection heuristicIn some problems, a solution can be described by a variable ordering Natural value ordering heuristics Examples: List-scheduling heuristics Configuration problems Local moves can be applied on the variable sequence itselfjE" 2;E" 2;4Local moves on a heuristicStandard process in Genetic Algorithms: Encode the solution Apply local changes to the encoding Construct the new solution (can be done by a CP-based solver) In CP: Preference-based programming6(v$(v$5Preference-based programmingExample on Job-Shop scheduling: Consider a ordered list of tasks (priority list) Choice point: (Schedule asap OR Postpone) Take one task at a time from the list and schedule it at its earliest start time otherwise  postpone the decision on the task for later Local moves on the preferred list of tasks generate different schedules Use tree search to explore a neighborhood of the preferred list Z1ZZ*ZZZ 1 *  j!6Outline/Introduction A didactic optimization problem (dTP) Motivations for cooperation A zoo of CP / LS hybrids Sequential combination Master / sub-problem decomposition Improved neighborhood exploration Neighborhoods in CP Large neighborhood search Local moves over a heuristic Local moves during construction 3ZZZ ZZ3  !  f$.7$Local Search and Greedy Construction%%&Local search is most often applied to complete solutions First build a solution, then improve it Idea: better repair while building than afterwards. => Incremental Local Optimization#8Incremental Local OptimizationThe greedy algorithm makes a mistake at step n The mistake is discovered at step n+k Try to repair the steps n .. n+k Resume the greedy construction at step n+k+1Z-" '9ILO for general CSPs A simple incomplete method: For a variable ordering v1& vn Compute a lower bound lb Start assigning variables Choose the value aik such that vi = aik yields the least increase in lb Whenever lb strictly increases, keep vi = aik , un-assign all variables linked to vi and try to re-assign them to find the least increase for lb ZZsZZ  ,       & :P7DKg;ILO illustrated on dTPDEnriched greedy construction scheme: Place clients on a stack Insert them one by one minimizing the insertion cost. For client i, instantiate visitedByi succi Apply local optimization on the truck assigned to i Change the order of visits j (forall j | visitedByj = visitedByi ) If an improving sub-route is found, change itZ%i4D.%Z    2      .PT  1<Illustration on a search space* Related to conflict-directed search++C'Ejection chains during a greedy processRecursive version of the ILO approach For a variable ordering v1& vn Choose the value aik such that vi = aik yields the least increase Dlb in lb When Dlb > 0, un-assign some variable vl so that lb decreases Reassign vl to some other value Go-on un-assigning / re-assigning past variables until the least increase in lb is found &!&        a bAJoLEjection chains on dTP MFinding a good ejection chainqSearch for the smallest ejection chain in breadth first search Similar to the search for augmenting paths (flows)rZr} Conclusion Real life combinatorial optimization problems often require crafting hybrid optimization methods: local search is a technique that can complement CP many hybrids are possible PcZM-Z -ZcM/{P4  ` f3|` 3f3` ___>?" dd@,f?lPd@  d " @ `"  n?" dd@   @@``PV    @ ` ` p>> % *( @   6Z?P`    "   NdQfgֳgֳ ?P  e1Cliquez pour modifier le style du titre du masque2 2"`  HSfgֳgֳ ?  vCliquez pour modifier les styles du texte du masque Deuxime niveau Troisime niveau Quatrime niveau Cinquime niveau4 w"  NDYfgֳgֳ ?0`P  ?*"   NQfgֳgֳ ?0P   A*"   T$Xfgֳgֳ ?0 P  C*"   `Of1? P rpage *" "f  Nvd޽h @? ? f3| >Prsentation gnrale du projet  % LD` (      Ngֳgֳ ?p f g1Cliquez pour modifier le style du titre du masque2 2 "   Hgֳgֳ ? p f n8Cliquez pour modifier le style des sous-titres du masque9 9 "  NDgֳgֳ ?0`P f ?*"  Ngֳgֳ ?0P  f A*"  Tgֳgֳ ?0 P f A*"  6?    "f  Nv޽h @? ? f3| 0 @0( 0 9  C xDyiyi1 ?28  f y*  G##GGjjX  C  5f  f  C xyiyi1 ? 6d f vCliquez pour modifier les styles du texte du masque Deuxime niveau Troisime niveau Quatrime niveau Cinquime niveau4 w ;  C xyiyi1 ?h 8 f {*  G##GGjj?  S ~dyiyi1 ?-2e  f y*  G##GGjjA  S ~Čyiyi1 ?-h e f {*  G##GGjjB  s * g _ ? ̙33 0PD( )pM P9 P c ĉyiyi1 ?28   _*  G##GGjj"; P c $yiyi1 ?h 8  a*  G##GGjj"? P s yiyi1 ?-2e   _*  G##GGjj"A P s yiyi1 ?-h e  a*  G##GGjj"H P 0 g _ ? ̙33 PL(    c $ p@ x "  c $d   x "B  s *޽h ? f3  F(  x  c $P  x   c $ x "p`PpH  0޽h ? f3|  0(  x  c $P  x x  c $ x H  0޽h ? f3|  0(  x  c $$P  x x  c $ x H  0޽h ? f3|  0(  x  c $P  x x  c $ x H  0޽h ? f3|  0(  x  c $dP  x x  c $ij x H  0޽h ? f3|  0(  x  c $P  x x  c $D x H  0޽h ? f3|  F(  x  c $P  x   c $ x "p`PpH  0޽h ? f3|  0(  x  c $ĶP  x x  c $$ x H  0޽h ? f3|  0(  x  c $P  x x  c $ x H  0޽h ? f3|  0(  x  c $DP  x x  c $A x H  0޽h ? f3|   0(  x  c $AP  x x  c $$B x H  0޽h ? f3|  00(  x  c $DP  x x  c $dD x H  0޽h ? f3|  xp@&&(  x  c $EP  x x  c $E x F    pP    `1?  2  Z1?  2  Z1? ` 2  Z1?  2   Z1? P 2   Z1?  2    `1? `@ 2    `1? P 2    `1?   2   `1? p` B  ZD1?P`  B  ZD1?0 B  ZD1?   B B ZD1?P P B B ZD1?P P B  ZD1?  B  ZD1?P P B  ZD1?`P  B B ZD1? 0 B  ZD1? 0 2  Z1? @p 2  Z33331?p2  Z33331?2  Z33331?  2  Z33331?0p2  Z1?0 ` B  ZD331? B   ZD331?pB !B ZD331?0@B "B ZD331?p B # ZD331? P B $B ZD1?p  B % ZD1?@@ 0 B & ZD1?` 0 H  0޽h ? f3|  P0(  x  c $FP  x x  c $G x H  0޽h ? f3|  `0(  x  c $dGP  x x  c $G x H  0޽h ? f3|  p0(  x  c $$HP  x x  c $H x H  0޽h ? f3|   0(   x   c $IP  x x   c $J f H   0޽h ? f3|  0(  x  c $$KP  f x  c $K f H  0޽h ? f3|  0(  x  c $KP  f x  c $DL f H  0޽h ? f3|  0(  x  c $?fP  f x  c $$@f f H  0޽h ? f3|  0(  x  c $AfP  f x  c $Bf f H  0޽h ? f3|   0(   x   c $BfP  f x   c $$Cf` f H   0޽h ? f3|  $F(  $x $ c $EfP  f  $ c $dEf f "p`PpH $ 0޽h ? f3|   U M  ( (  (x ( c $$FfP  e x ( c $Ff 0 e  (  `Ff1?@ `  Ftime 2  vB ( NDo?p vB ( NDo?p q  (  B\C8DEF<o?%% p<HHa} 85q-$hOzCRh$X]-$|8<,G0\0@            @0H  (  B C DEFTo?77 ,DXHl~s =(p*?` *@XXsm8Y,xCXnuG #, P8 h b hh t \ '(@                   |B  ( TDo?   (  `DGf1? P  Dt0 2    (  `Hf1?  K objective 2     (  `dHf1?P  DCP 2    (  `Hf1?@  DLS 2  H ( 0޽h ? f3|  ,0(  ,x , c $IfP  e x , c $DJf e H , 0޽h ? f3|  00(  0x 0 c $KfP  e x 0 c $le e H 0 0޽h ? f3|   V N 4 (  4x 4 c $meP  e l L    4# p N    4   B 4 TD1?  B 4B TD1?  B 4B TD1?   N    4   B  4B  fD1? "B  4  fD1? p"B  4B  fD1?p  "B  4B  fD1?` ` "B  4B  fD1?` ` "B 4  fD1? ` "B 4B  fD1? ` "B 4B  fD1?  "B 4  fD1? 0 "B 4B  fD1?0  " 4  fne1?P0  $ At each choice point a function h is evaluated for all possible choices The choice that minimizes h is considered as preferred decision The preferred decision is taken^ lP2!BFH 4 0޽h ? f3|0[  ZZ08pZ(  8x 8 c $tneP  e  F `  8 U ln  8  `jJ?6 ! 2 8 ZjJ?6 ! 2 8 ZjJ?Db  2 8 ZjJ? q 2 8  `jJ?  B  8 ZDjJ? D6 B  8 ZDjJ?  B  8B ZDjJ?q  B  8 ZDjJ?  B  8 ZDjJ?;  2 8 ZjJ?[ 7 2 8 Z3333jJ?` 2 8 Z3333jJ?E' B 8 ZD33jJ?E B 8B ZD33jJ?'  B 8 ZD33jJ? q B 8B ZDjJ?m [ B 8 ZDjJ?7;  2 8 Z1?q,$D 02 8 Z1?q4,$D 02 8  fne1?qP <  2 8 Z1?qLz    8  : ,$D 0@ t z  8   ,$D 0B 8 ZDjJ?t 0T B 8 ZDjJ?  B 8B ZDjJ? _ z @   8  ,$D 0B  8 ZD33jJ?=  B !8B ZD33jJ?9 B "8 ZD33jJ? z Ls  #8   ,$D 0 $8  `jJ? T ? 2 %8 ZjJ? T ? 2 &8 ZjJ?0  2 '8 ZjJ? s 2 (8  `jJ?)  B )8 ZDjJ?   B *8 ZDjJ? Y  2 +8 ZjJ?y # 2 ,8 Z3333jJ?L  2 -8 Z3333jJ? 1 E B .8B ZDjJ?Y  y B /8 ZDjJ?# Y 2 08 ZjJ?S  c z 7  18  l ,$D 0  O  28 g } ,$D 06 38 C x4oe1?;3,$D 0 DdCost1" "<N \ E 48 O N  s  58 \ B 68 # lDjJ?0  s  "B 78B # lDjJ?\ X "B 88 ZD33jJ? ~B 98 ZD33jJ?d~E@ t z  :8  7 ,$D 0B ;8 ZDjJ?t 0T B <8 ZDjJ?  B =8B ZDjJ? _ z hz t  >8  . ,$D 0 nI  ?8  D ,$D 0N " ^ >  @8 n> B A8 ZD33jJ?% " 2 N   B8 - ^ >    C8#  ,$D 0B D8 # lDjJ?  "B E8 # lDjJ? "B F8B ZD33jJ? =( G8 C xoe1?m I B,$D 0 DdCost2" @ t z  H8  t ,$D 0B I8 ZDjJ?t 0T B J8 ZDjJ?  B K8B ZDjJ? _ z  z ! 7  L8  : ,$D 08   M8 ! w ,$D 0vN   N8    |  O8# q ,$D 0B P8 # lDjJ? "B Q8 # lDjJ? | "B R8B ZD33jJ? B S8 ZD33jJ?v ( T8 C xoe1?99S1,$D 0 DdCost3" @ t z  U8  7 ,$D 0B V8 ZDjJ?t 0T B W8 ZDjJ?  B X8B ZDjJ? _ z  z    Y8  4 ,$D 08 #  Z8 / U T ,$D 0vN )  [8 M  w   \8# ) ,$D 0B ]8 # lDjJ?  "B ^8B # lDjJ?w  "B _8 ZDjJ?8  B `8 ZDjJ?`9^( a8 C xTpe1?#=,$D 0 DdCost4" @   b8  ,$D 0B c8 ZD33jJ?=  B d8B ZD33jJ?9 B e8 ZD33jJ?  z    f8  . ,$D 08   g8  A J ,$D  0vN   h8      i8# 2Y,$D 0B j8 # lDjJ? G "B k8 # lDjJ?   "B l8 ZDjJ?gB m8B ZDjJ?n ( n8 C xpe1? ,$D 0 DdCost5" @   o8  ,$D 0B p8 ZD33jJ?=  B q8B ZD33jJ?9 B r8 ZD33jJ? z  =  s8  . ,$D 0 SCr t8 { ? =n ,$D  0<N SCr u8 SCrN ? - 7  v8 SC'MB w8 # lDjJ?? c ` 7 "B x8 # lDjJ? -  "B y8 ZDjJ?B z8B ZDjJ?Wr( {8 C xqe1?2?L8,$D 0 DdCost6" @   |8  ,$D 0B }8 ZD33jJ?=  B ~8B ZD33jJ?9 B 8 ZD33jJ?  z 4  8 4 ,$D  0    8 57  ,$D  0 8  `jJ?6 ! 2 8 ZjJ?6 ! 2 8 ZjJ?yb  2 8 ZjJ?P q 2 8  `jJ? P B 8 ZDjJ? y6 B 8 ZDjJ? P B 8B ZDjJ?)q P B 8 ZDjJ?  B 8 ZDjJ?);  2 8 ZjJ?[ l 2 8 Z3333jJ?  2 8 Z3333jJ?z' B 8B ZD33jJ?' D B 8 ZD33jJ? q B 8B ZDjJ? [ B 8 ZDjJ?l;  2 8 Z3333jJ?E T  |  8# z  B 8 # lD33jJ? "B 8 # lD33jJ? | " 8 3 r1?4  8  `tqe1?`P F&  2$  H 8 0޽h ? f3|  @<0(  <x < c $qeP  e x < c $4re e H < 0޽h ? f3|@   P33@(  @x @ c $TseP  e x @ c $sep P e F % @  Pp 2 @  `1?g vB @B TD1?D B @ TD1?1 D [ 2 @  `1? > O 2  @  `1? B c 2  @  `1?' c 2  @  `1? , P B  @B TD1? B  @ TD1? ] B @B TD1? 1 P 2 @  fte1?) *  <  B @ TD1? G u * 2 @  `1?> D 2 @  `1?^ c 2 @  `1? c B @B TD1?  B @ TD1?   2 @  ftte1?6+   <  B @B TD1?c + 2 @  fte1?* x  <  B @ TD1?eG "P 2 @  `1?A*  2 @ Z1?S*  2 @ Z1? 4B @B TD1? * B @ TD1? 3 B @B TD1?  2  @  f4ue33331?2  <  B !@ TD1? X 2 "@  `1?) c 2 #@  `1? v 2 $@ Z1?v  2 %@  fue33331?O < <  B &@B TD1?x J Pv B '@ TD1?G  B (@B TD1? j 2 )@  fue1? : <  B *@ TD1?~  2 +@ Z33331? m <B ,@B TD1?= 2 -@  fTve1?l  : <  B .@ TD1? 2 /@  fve1?[ <  2 0@  fwe1?`  % <   1@B  fG>H*I"1?  2@B  fG5H0*I+1?` r 3@ # lZGHI1? m &H @ 0޽h ??` @/@1@%@0@2@+@+@3@ f3|  `D0(  Dx D c $tweP  e x D c $we e H D 0޽h ? f3|  pHF(  Hx H c $teP  e  H c $e e "p`PpH H 0޽h ? f3|  L0(  Lx L c $eP  e x L c $e e H L 0޽h ? f3|  P0(  Px P c $TeP  c x P c $e c H P 0޽h ? f3|  T0(  Tx T c $eP  c x T c $te c H T 0޽h ? f3|  \0(  \x \ c $4eP  c x \ c $e c H \ 0޽h ? f3|  `F(  `x ` c $eP  c  ` c $Te c "p`PpH ` 0޽h ? f3|  d0(  dx d c $eP  c x d c $te c H d 0޽h ? f3|&  %%BBhT%(  hx h c $TeP  c x h c $e0 c  z @ `p h  @`p,$D 0 h  `1?@0  2 h Z1?@0  2 h Z1?0 p 2 h Z1?@  2  h Z1? `` 2  h Z1? 0  2  h  `1? P 2  h  `1? p` 2  h  `1? 2 h  `1?pB h ZD1?p 00 B h ZD1? @@ B h ZD1?  B hB ZD1?` ` B hB ZD1?0` ` B h ZD1? P B h ZD1?p`  B h ZD1?`  B hB ZD1? @B h ZD1? @ z 0 P p h  0 P p,$D 0 h  `1?0 0 2 h Z1?0 0 2 h Z1?  p 2 h Z1?0  2 h Z1? P ` 2 h Z1? 0 p 2  h  `1?p P 2 !h Z1? ` ` 2 "h  `1? 2 #h  `1?  pB $h ZD1? p 0 B %h ZD1? 0 @ B &h ZD1?  B 'hB ZD1?p ` ` B (hB ZD1? `  ` B )h ZD1? @ B *h ZD1?` ` B +h ZD1? ` B ,hB ZD1?  @B -h ZD1? @ z  p .h  p,$D 0 /h  `1?0  2 0h Z1?0  2 1h Z1? @p 2 2h Z1? P 2 3h Zff1? ` 2 4h Z1?0 0 2 5h  `1?0 P 2 6h Z1? ` 2 7h  `1?P 2 8h  `1?@pB 9h ZD1?p 0 B :h ZD1?@ @ B ;hB ZD1?` ` B h ZD1? @@B ?h ZD1?   B @hB ZD1?00 ` B Ah ZD1?`  B BhB ZD1?`  H h 0޽h ? f3||  ,$l(  lx l c $eP  c x l c $4ep  c |B l TDԔ?   |B l TDԔ?p00|B l TDԔ?@@H l 0޽h ? f3|%  %%::p4%(  px p c $TeP  c x p c $e0  c L  ` p#  P p  `1?w p 2 p Z1?w p 2 p Z1? M 2 p Z1?_  2  p Z1?K:  2  p Z1?w t 2  p  `1?tp  2  p Z1?$:  2  p  `1?hK2 p  `1?M`B p ZD1?` w B p ZD1?M _A B p ZD1? K: B pB ZD1?t K B pB ZD1?  B p ZD1?2 9p B p ZD1? hB p ZD1? $p B pB ZD1?"B p ZD1? M" p 3 r@b1?H G  Fi1(  p 3 r$Ab1?]U aU  Fi2(  p 3 rAb1?.   Ksprevi2(  p 3 rAb1?  Ksnexti1(  p 3 rDBb1?`  Ksprevi1(  p 3 rBb1?^   Ksnexti2( L  +0 p#  g5  p  `1? b R 2 !p Z1? b R 2 "p Z1?6 s 2 #p Z1? . 2 $p Zff1?'  2 %p Z1?Zb  2 &p  `1?R C 2 'p Z1?~'  2 (p  `1?.A2 )p  `1? 0B *p ZD1? s 6b B +p ZD1? 7 B ,pB ZD1?6 Z B -p ZD1?  R B .pB ZD1?Z.B /p ZD1? B 0p ZD1? ' B 1pB ZD1?b ~ B 2p ZD1?C  B 3pB ZD1? A 4p 3 rCb1?r7 v6  Fi1(  5p 3 rdCb1?y y  Fi2(  6p 3 rCb1? V  Ksprevi2(  7p 3 r$Db1?+ Ksnexti1(  8p 3 rDb1? f Ksprevi1(  9p 3 rDb1? v  Ksnexti2( |B :p TDԔ?   H p 0޽h ? f3|  >6t(  tx t c $dFbP  c  t HFbgֳgֳ ?  Pros: Independent from side-constraints Cons: CP imposes monotonic changes while moving from one neighbor to the next one all problem variables are un-instantiated and re-instantiated Constraints are checked in  generate and test inefficient0lPZ$0 Z0lPZ0 Z0 Z00 Z0 Z#~38 #  AH t 0޽h ? f3|0   xp(  xx x c $$GbP  c  x TGbgֳgֳ ?  c |B x TDԔ? pp`|B x TDԔ?p00|B x TDԔ?@@|B x TDԔ? H x 0޽h ? f3|  0|>(  |x | c $dIbP  b  | HIbgֳgֳ ?  Pros:  Almost independent from side-constraints Some constraints are tested before performing the move much more efficient Cons: CP imposes monotonic changes Some constraints are still checked in  generate and test 0lPZd0 Z0 Z0lPZZ0 Zd;8 {  ;H | 0޽h ? f3|  @F(  x  c $$JbP  b   c $Jb b "p`PpH  0޽h ? f3|  P0(  x  c $DKbP  b x  c $Kb b H  0޽h ? f3|%  %~%`:: %(   x   c $dLbP  b x   c $ 0P b #F 9p     @T  5 `  # 9p     `1?w p 2   Z1?w p 2   Z1? M 2   Z1?_  2   Z1?K:  2   Z1?w t 2    `1?tp  2   Z1?$:  2    `1?hK2    `1?M`B   ZD1?` w B   ZD1?M _A B   ZD1? K: B  B ZD1?t K B  B ZD1?  B   ZD1?2 9p B   ZD1? hB   ZD1? $p B  B ZD1?"B   ZD1? M"   3 rd 1?H 'G  Fi1(    3 r 1?]U U  Fi2(    3 r$ 1?. S  Ksprevi2(    3 r 1? 5  Ksnexti1(    3 r 1?_  Ksprevi1(    3 rD 1?^   Ksnexti2( T  0  #   !   `1? b R 2 "  Z1? b R 2 #  Z1?6 s 2 $  Z1? . 2 %  Zff1?'  2 &  Z1?Zb  2 '   `1?R C 2 (  Z1?~'  2 )   `1?.A2 *   `1? 0B +  ZD1? s 6b B ,  ZD1? 7 B - B ZD1?6 Z B .  ZD1?  R B / B ZD1?Z.B 0  ZD1? B 1  ZD1? ' B 2 B ZD1?b ~ B 3  ZD1?C  B 4 B ZD1? A 5  3 r 1?s7 6  Fi1(  6  3 r 1?y y  Fi2(  7  3 rd 1?   Ksprevi2(  8  3 r 1? Ksnexti1(  9  3 r$! 1?  Ksprevi1(  :  3 r! 1?   Ksnexti2( H   0޽h ? f3|  p0(  x  c $! P   x  c $D"    H  0޽h ? f3|  RJ&&(  x  c $d# P     H# gֳgֳ ? ` MOSearch: instantiate(I) && instantiate(J) Each leaf defines a feasible exchange VO0lPZ0 ZNn           ]F H  0N     2   `1?  B B TD1?_ B  TD1?< _    # l$ 1?[  bI::[1..3], J::[2..4] 2    `1? uZ 2    `1?R T 2    `1? TT 2    `1?t R AB B TD1?  B  TD1?1  B B TD1?  2  # l$ 1?P Q <  B  TD1?0 P   # l% 1?$k  aI::[2..3],J::[3..4]   # ld& 1?0   ^I::[2],J::[3..4]   # l$' 1?4 H  [ I::[3],J::[4]    # l' 1?0 D [ I::[2],J::[3]    # l( 1?`t [ I::[2],J::[4]  2   `1?t AZ 2   `1? T 2   `1? T B B TD1?b  B  TD1? R   # ld>1?  ^I::[1],J::[2..4] >N  0   00 2  # l>1? R  <  B  B TD1?T R 2 ! # l$?1?P  <  B " TD1?0 |  # # l?1?   [ I::[1],J::[2]   $ # l@1?  ^I::[1],J::[3..4]  % # ldA1? 4 [ I::[1],J::[3]   & # l$B1?  [ I::[1],J::[4]  H  0޽h ? f3|\    (  x  c $BP     HBgֳgֳ ? ` \Suppose that in S: clients 1,2 are visited by truck 1, clients 3,4 are visited by truck 2 0lPZH0lPZ0lPZ0 ZHT        L   #  2   `1?  B B TD1?_ B  TD1?< _   # lC1?[  bI::[1..3], J::[2..4] 2    `1?K O 2    `1? 1 2    `1? V !S|B  @ TD1?  |B  @ TD1?  2  # lD1? `+Q <  |B  TD1?    # lD1?x U  _I::[2,3],J::[3,4]   # lE1?V  3  ^I::[2],J::[3..4]   # lDF1?S !0 [ I::[2],J::[3]    # lG1?S=I0 [ I::[2],J::[4]  2   `1?K j5   # lG1? p  _I::[1],J::[2,3,4] F     ` o DT  0  # $  2  # l$H1? R  <  B B TD1?T R 2  # lH1?P  <  B  TD1?0 |   # lDI1? & [ I::[1],J::[3]    # lJ1?  [ I::[1],J::[4]  |B  TDԔ? PP |B  TDԔ? P `   # lTK1?{  :svisitedBy[I] svisitedBy[J]B$  H  0޽h ? f3|>  ~(  x  c $KP     HLgֳgֳ ?  NPros: Independent from side-constraints Constraint Propagation removes infeasible neighbors a priori. efficient when many side constraints efficient when large neighborhood May freely mix tree search and local search Cons: Overhead due to tree search 0lPZb0 ZO0 Z-0 Z0lPZ0 ZbO,$  H  0޽h ? f3|   P(   x   c $tLP      HLgֳgֳ ?  lOverhead due to tree search Often most problem variables are instantiated by the interface constraints only when ALL neighborhood variables are instantiated (at every leaf of the nhood tree search) In this case the nhood tree search keeps  doing and  undoing the instantiations of ALL the problem variablesN0lPZ0lPZ, XH   0޽h ? f3|  $0(  $x $ c $4MP   x $ c $M@  H $ 0޽h ? f3|   ,`(  ,x , c $tO`P    , TOgֳgֳ ?`0  H , 0޽h ? f3|  h`0(  0x 0 c $tR`P   @ 0 HRgֳgֳ ?0 Map the array of deltas in a tree search recursively split the array of deltas in two parts a split correspond to a branching node in the tree search each feasible neighbor is a leaf of the tree at each node restore the fraction of S that is shared by all neighbors in that node x)0lPZ0  PZ0  PZ)   '         )                H 0 0޽h ? f3|k  $$4(  4x 4 c $4S `P    4 HSgֳgֳ ?0 &Example: deltas = [d1,d2,d3,d4,d5,d6]  &0lPZ0lPZ          F @ 4 @2 4  `1?  2 4  `1? Z 2 4  `1? qZ 2 4  `1?m :T 2  4  `1? o T 2  4  `1?N  T 2  4  `1? PT 2  4  `1?p R = 2  4 # lTT1?R m <  B 4B TD1?_ B 4B TD1? L B 4B TD1?)T R B 4 TD1?< _ B 4 TD1? B 4B TD1?  B 4 TD1?-  B 4B TD1?   4 # lU1?/ [d1,d2,d3,d4,d5,d6]       V 4 # lU1?s   [d1,d2,d3]r      V 4 # ld1?Q   [d4,d5,d6]r      5 4 # lTe1? `  [d1,d2]T    4 # le1?  p[d3]6  5 4 # lf1?   [d4,d5]T    4 # ltf1?a   p[d6]6   4 # lf1?  7 p[d1]6   4 # l4g1? ) a @ p[d4]6  2 4 # lg1?P } <  2  4 # lg1? P M <  B !4 TD1? 0  B "4 TD1? 0 P  #4 # lTh1?@ 7 p[d5]6   $4 # lh1?O 7 p[d2]6  H 4 0޽h ? f3|  8<(  8x 8 c $iP    8 Htigֳgֳ ?  Pros: Independent from side-constraints Constraint Propagation removes infeasible neighbors a priori. efficient when many side constraints efficient when large neighborhood May freely mix tree search and local search Reduced overhead of the tree search Cons: Requires an explicit generation of the neighborhood Requires to fully specify each move0lPZb0 ZO0 ZR0 Z0lPZX0 ZbOQX$  XH 8 0޽h ? f3|  dF(  dx d c $iP    d c $4j  "p`PpH d 0޽h ? f3|   H$(  Hr H S jP   r H S Tk  H H 0޽h ? f3|  xp0&'(  x  c $kP   x  c $l  F    P 0   `1?  2  Z1?  2  Z1? ` 2  Z1?  2   Z1? P 2   Z1?  2    `1? `@ 2    `1? P 2    `1?   2   `1? p` B  ZD1?P`  B  ZD1?0 B  ZD1?   B B ZD1?P P B B ZD1?P P B  ZD1?  B  ZD1?P P B  ZD1?`P  B B ZD1? 0 B  ZD1? 0 2  Z1? @p 2  Z33331?p2  Z33331?2  Z33331?  2  Z33331?0p2  Z1?0 ` B  ZD331? B   ZD331?pB !B ZD331?0@B "B ZD331?p B # ZD331? P B $B ZD1?p  B % ZD1?@@ 0 B & ZD1?` 0 H  0޽h ? f3|  bZ@(*L(  Lx L c $tl   L # ll1? ` &  ZSelect a subset of clients i1, i2 , & , ik Cl.   'F 0   L ` 0 L  `1?p 0 2 L Z1?p 0 2 L Z1?` ` 2  L Z1?p 2  L Z1?0 P 2  L Z1?P 2  L  `1? @ 2  L Z1?@ P 2 L  `1? 0 2 L  `1? ` B L ZD1? ` ` B L ZD1? p0 B L ZD1? 0 B LB ZD1? P 0P B LB ZD1?` P P P B L ZD1?0 B L ZD1?P  B L ZD1?P @ B LB ZD1?P 0 B L ZD1?0  0 2 L Z1?  p 2 L Z331?P p 2 L  f4m331?`   <  2 L Z33331?0 2 L Z33331?  p2 L Z1? 0  2  L s vd @1? ` B !L ZD1?0  B "L ZD1?  pB #LB ZD1? ` @B $LB ZD331? p B %L ZD331? p P B &LB ZD1? p  B 'L ZD1? @ 0 B (L ZD1?  0  *L Zmgֳgֳ ?P   H L 0޽h ? f3|E  P#Py(  Px P c $m   P  f1?e .C 2 P  `1?e .C 2 P  `1? ; 2  P  `1?  2  P  `1? 2  P  `1?e l 2  P  f1? l% 2  P  `1? < 2 P  f1? P2 P  f1?PB P  `D1?E C' B P@  `D1?P B P  `D1? C2 P  `1? zp 2 P  `1?l[ 2 P # lTn1?P <  2 P  `33331?  2 P  `33331?0_2 P  `1?0B P@  `D331?z B P  `D331? z. B P@  `D1?E J. B P  `D1?% B P  `D1? s P  `o1?p  G Shuffle set D !P  `to1?0@ L For all clients i from the shuffle set : Unassign variable: - visitedByi , collectedIni - starti Undo all ordering decisions between i and other clients j Unassign all cost variables Post a cost improvement cut cost getValue(cost,S) - e **[  %?t+  < <  #P Zogֳgֳ ?P   H P 0޽h ? f3|  `'+\(  \B \ ZD1?E C' ,$D 0B \@ ZD1?P ,$D 0B \ ZD1? C,$D 0h z   \ P 0,$D  0 \  `1? 0 F N    \  2  \ Z1? 0 2  \ Z33331? E 2  \ Z1?  E 2  \ Z1?& P 2 \ Z1?r  2 \  `1? 0 2 \ Z1? V P 2 \  `1? [ & 2 \  `1? - 2 \ Z1? {  2 \ Z33331?r e 2 \  f4p33331?   <  2 \ Z33331?%  2 \ Z33331?de2 \ Z1?;4B \@ ZD331?z ,$D 0B \ ZD331? z. ,$D 0B \@ ZD1?E J. ,$D 0B \ ZD1?% ,$D   0B \ ZD1? s,$D   0B \ ZD331?; e ,$D  0B \@ ZD331?_{,$D  0B  \ ZD1?%  ,$D 0B !\ ZD1? C ,$D 0B "\ ZD1?e l< B #\ ZD1?e  e B $\ ZD1?  ,$D  0B %\@ ZD1?[ e ,$D 0B &\ ZD331?  ,$D 0B '\ ZD331? (\  `p1?d P  o= Look for a new solution by solving the remaining sub-problem>> *\ Z4ugֳgֳ ?P   H \ 0޽h ? f3|x   (  p $(  $x $ c $uP   x $ c $u  p $ HTvgֳgֳ ?  Procedure moveLNS(P,S,algorithm) // define current sub-problem Problem P = P (cost getValue(cost,S)  e) propagate(P ) while (not stop()) VariableSet shuffleSet = defineShuffleSet(P,S) foreach variable X | X shuffleSet P = P (X = getValue(X,S)) if solve(P ,algorithm,S) succeeds stop iteration<"0lPZ"0 Z"33" G 9             = |B $ TDԔ?|B $ TDԔ? |B $ TDԔ?@|B  $ TDԔ? P H $ 0޽h ? f3|  d$(  dr d S vP   r d S w  H d 0޽h ? f3|  h$(  hr h S xP   r h S Ty  H h 0޽h ? f3|  l$(  lr l S zP   r l S tz  H l 0޽h ? f3|  pF(  px p c $4{P    p c ${  "p`PpH p 0޽h ? f3|  t0(  tx t c $T|P   x t c $|  H t 0޽h ? f3|  x0(  xx x c $}P   x x c $4~  H x 0޽h ? f3|=  T=L=ee|<(  |x | c $~P   ZL p p  |#   `T    |# p p B | TD1?  B |B TD1?  B |B TD1?   T    |#  p B  |B  fD1? "B  |  fD1? p"B  |B  fD1?p  "B  |B  fD1?` ` "B  |B  fD1?` ` "B |  fD1? ` "B |B  fD1? ` "B |B  fD1?  "B |  fD1? 0 "B |B  fD1?0  "N 0   | 0  B |  fD331?p` "B |B  fD331?`  "B |B  fD331?@ P "N P   | P  B |  fD331?@P  "B |B  fD331?@ p "B |B  fD331?p @ "B |  fD331? @ "B |B  fD331? @ "B |  fD331? 0P "B |  fD331?0P  "B |B  fD331?0 p "ZN p 0   | p 0 B !|B  fD331?p 0 "B "|  fD331? 0 "B #|B  fD331? 0 "B $|  fD331?0p  "B %|  fD331?  "B &|B  fD331?  "B '|B  fD331?P P "B (|B  fD331? p "B )|B  fD331?0p  "B *|  fD331?0  "B +|B  fD331?0  " L `0 `0 ,|# 80 T    -|# `0 `0B .| TD1?  B /|B TD1?  B 0|B TD1?   T    1|# 0 `0B 2|B  fD1? "B 3|  fD1? p"B 4|B  fD1?p  "B 5|B  fD1?` ` "B 6|B  fD1?` ` "B 7|  fD1? ` "B 8|B  fD1? ` "B 9|B  fD1?  "B :|  fD1? 0 "B ;|B  fD1?0  "B <|  fD331?@ 0"B =|B  fD331? 0"l L    >|#  0 N    ?|   B @| TD1?  B A|B TD1?  B B|B TD1?   N    C|   B D|B  fD1? "B E|  fD1? p"B F|B  fD1?p  "B G|B  fD1?` ` "B H|B  fD1?` ` "B I|  fD1? ` "B J|B  fD1? ` "B K|B  fD1?  "B L|  fD1? 0 "B M|B  fD1?0  " L    N|#  8`n N    O|   N    P|   B Q| TD1?  B R|B TD1?  B S|B TD1?   N    T|   B U|B  fD1? "B V|  fD1? p"B W|B  fD1?p  "B X|B  fD1?` ` "B Y|B  fD1?` ` "B Z|  fD1? ` "B [|B  fD1? ` "B \|B  fD1?  "B ]|  fD1? 0 "B ^|B  fD1?0  "N   _|  B `|  fD331?P @ "B a|B  fD331? P"B b|B  fD331?  "B c|  fD331? "B d|  fD331?@  " e| # l1?  HConstructive heuristic"H | 0޽h ? f3|  0(  x  c $P   x  c $t  H  0޽h ? f3|c  cc,c(  x  c $tP    F `   U ln    `jJ?6 ! 2  ZjJ?6 ! 2  ZjJ?Db  2  ZjJ? q 2   `jJ?  B   ZDjJ? D6 B   ZDjJ?  B  B ZDjJ?q  B   ZDjJ?  B   ZDjJ?;  2  ZjJ?[ 7 2  Z3333jJ?` 2  Z3333jJ?E' B  ZD33jJ?E B B ZD33jJ?'  B  ZD33jJ? q B B ZDjJ?m [ B  ZDjJ?7;  z      : ,$D 0@ t z     ,$D 0B  ZDjJ?t 0T B  ZDjJ?  B B ZDjJ? _ z @     ,$D 0B  ZD33jJ?=  B B ZD33jJ?9 B  ZD33jJ? z Ls     ,$D 0    `jJ? T ? 2 ! ZjJ? T ? 2 " ZjJ?0  2 # ZjJ? s 2 $  `jJ?)  B % ZDjJ?   B & ZDjJ? Y  2 ' ZjJ?y # 2 ( Z3333jJ?L  2 ) Z3333jJ? 1 E B *B ZDjJ?Y  y B + ZDjJ?# Y 2 , ZjJ?S  c z ! 7  -  L ,$D 0   . ! w ,$D 0ZN   /    |  0# q ,$D 0B 1 # lDjJ? B 2 # lDjJ? | B 3B ZD33jJ? B 4 ZD33jJ?v ( 5 C x1?99S1,$D 0 DdCost3" @ t z  6  7 ,$D 0B 7 ZDjJ?t 0T B 8 ZDjJ?  B 9B ZDjJ? _ z z  =  :  : ,$D 0 SCr ; { ? =n ,$D  0 N SCr < SCrN ? - 7  = SC'MB > # lDjJ?? c ` 7 B ? # lDjJ? -  B @ ZDjJ?B AB ZDjJ?Wr( B C x41?2?L8,$D 0 DdCost6" @   C  ,$D 0B D ZD33jJ?=  B EB ZD33jJ?9 B F ZD33jJ?  z 4  G 4 ,$D  0    H 57  ,$D  0 I  `jJ?6 ! 2 J ZjJ?6 ! 2 K ZjJ?yb  2 L ZjJ?P q 2 M  `jJ? P B N ZDjJ? y6 B O ZDjJ? P B PB ZDjJ?)q P B Q ZDjJ?  B R ZDjJ?);  2 S ZjJ?[ l 2 T Z3333jJ?  2 U Z3333jJ?z' B VB ZD33jJ?' D B W ZD33jJ? q B XB ZDjJ? [ B Y ZDjJ?l;  2 Z Z3333jJ?E T  |  [# z  B \ # lD33jJ? B ] # lD33jJ? |  ^ 3 r1?4  z  2t _   ,$D 0 7  `  2t,$D 0 O  a g } ,$D 0( b C x1?;3,$D 0 DdCost1"  N \ E c O N  s  d \ B e # lDjJ?0  s  B fB # lDjJ?\ X B g ZD33jJ? ~B h ZD33jJ?d~E@ t z  i  7 ,$D 0B j ZDjJ?t 0T B k ZDjJ?  B lB ZDjJ? _ z N Vx m l z B n 3 rD)?PxB oB 3 rD)?Vr2 z .& p  . ,$D 0    q .&,$D 0 #  r / U T ,$D 0ZN )  s M  w   t# ) ,$D 0B u # lDjJ?  B vB # lDjJ?w  B w ZDjJ?8  B x ZDjJ?`9^( y C x1?#=,$D 0 DdCost4" @   z  ,$D 0B { ZD33jJ?=  B |B ZD33jJ?9 B } ZD33jJ? N Vx ~  B  3 rD)?PxB B 3 rD)?Vr z    F ,$D 0T t   ,$D 0z nI    D ,$D 0N " ^ >   n> B  ZD33jJ?% " 2 N    - ^ >    #  ,$D 0B  # lDjJ?  B  # lDjJ? B B ZD33jJ? =(  C xT1?m I B,$D 0 DdCost2" @ t z    t ,$D 0B  ZDjJ?t 0T B  ZDjJ?  B B ZDjJ? _ z N Vx    B  3 rD)?PxB B 3 rD)?Vr2 z dw   . ,$D 0     dw,$D 0     A J ,$D  0ZN         # 2Y,$D 0B  # lDjJ? G B  # lDjJ?   B  ZDjJ?gB B ZDjJ?n (  C x1? ,$D 0 DdCost5" @     ,$D 0B  ZD33jJ?=  B B ZD33jJ?9 B  ZD33jJ? N Vx  $B  3 rD)?PxB B 3 rD)?Vr4F P  P2  Z1?q,$D 02  Z1?4q,$D 02   f1?qP <  2  Z1?qL   `t1?`P F&  2$  H  0޽h ? f3|  '':(  x  c $P   l L    # @N       B  TD1?  B B TD1?  B B TD1?   N       B  B  fD1? "B    fD1? p"B  B  fD1?p  "B  B  fD1?` ` "B  B  fD1?` ` "B   fD1? ` "B B  fD1? ` "B B  fD1?  "B   fD1? 0 "B B  fD1?0  "B  # lD1? >"B  # lD1?x $ " F  <@   2  Z1?4    C x41? <0  Xhmin"T $p  # Mq _   # l1?$p"  3 r1? "  C x1?@ `  Xhmax"B B TD1?P@@B B TD1?P @B   fD1?   "B B  fD1? @"B    fD1? @"B !B  fD1?0 @"B "  fD1?  @"B #  fD1?p 0("B $B  fD1?p p("B %  fD1?  ("B &  fD1?  p "B '  fD1?p @"H  0޽h ? f3|   0(  x  c $P   x  c $T  H  0޽h ? f3|b   011(  x  c $P   l L    # @N       B  TD1?  B B TD1?  B B TD1?   N       B  B  fD1? "B    fD1? p"B  B  fD1?p  "B  B  fD1?` ` "B  B  fD1?` ` "B   fD1? ` "B B  fD1? ` "B B  fD1?  "B   fD1? 0 "B B  fD1?0  "vF 0rp @  r0p @B   fD1?` r "B   fD1? > "B B  fD1?  "B   fD1?  f "B B  fD1? f 5 "B   fD1? 5  "B B  fD1?  "B B  fD1?`  "B B  fD1? ` q "B B  fD1?wq  @"B   fD1?  "B   fD1? p f "B  B  fD1? f p 5 "B !  fD1? 5 p  "B "B  fD1?  p "B #B  fD1? "B $B  fD1? q "B %  fD1? q @"B &  fD1?  f "B 'B  fD1?` f 5 "B (B  fD1? 5 `  "B )B  fD1?w  "B *  fD1?w w "B +  fD1?w wq "B ,B  fD1?q w@"B -B  fD1?25  "B .B  fD1? 2 "B /B  fD1?0  "B 0  fD1?0 q "B 1B  fD1?0q @"H  0޽h ? f3|  @0(  x  c $4P   x  c $  H  0޽h ? f3|,  ,,P>>,(  x  c $P   |B @ TDo?@p B   fDo?V "B @  fDo?K "B   fDo?@ K"B   fD33o?K "|B @ TDo? zpB    fDo?H "B  @  fDo?0 ZZ"B    fDo? pZ0 "B    fD33o?0 Ze"|B  @ TDo? `VB   fD33o?H kk"B @  fD33o?0 @ @ "B   fD33o? V@ 0 "B   fDfo?0 @ K "|B @ TDo? B   fD33o?H "B @  fD33o?0 uu"B   fD33o? u0 "B   fDfo?0 u"|B @ TD33o? B   fDfo?H "B @  fDfo?0 "B   fDfo? 0 "B   fDo?0 "  C x41? PD22 "  C x1? PD12 "  C x1? PD12 "  C xT1?^z PD02 "   C x1?   PD32 " ! C x1?~ x PD22 " " C x1? < PD22 " # C xT1? PD12 " $ C x1?.J PD32 " % C x1?p.j PD22 " & C xt1?T p PD22 " ' C xԮ1?   PD12 " ( C x41?n PD42 " ) C x1?p,j PD32 " * C x1?`| PD32 " + C xT1?@\ PD22 " , C x1? X maxDiscr = 1   "F    -   @ B .  fD)?  "B /B  fD)?  "F    0 8 ; B 1  fD)?  "B 2B  fD)?  "F    3 8 % B 4  fD)?  "B 5B  fD)?  "F    6 8 k B 7  fD)?  "B 8B  fD)?  "F    9  0@ B :  fD)?  "B ;B  fD)?  "F    < (B =  fD)?  "B >B  fD)?  "H  0޽h ? f3|  f^`(  x  c $tP   x  c $Ա  2  H4gֳgֳ ? VProcedure solve(P) while (not stopping condition) Solution S = int failLimit = 50 bool result = solveGRASP(P,S,failLimit) if (result) P = (P (Cost(P) < Cost(S))0lPZ0 Z-T          .|B  TDԔ?p |B  TDԔ?pp |B  TDԔ?@ PP H  0޽h ? f3|  5-p(  x  c $P   x  c $T    Hgֳgֳ ?  @ ;Procedure solveGRASP(P,S,failLimit) while (unscheduled clients exist and failLimit not reached) Client v = selectVariable(P,S) discardBadValues(P,S) //Restricted Candidate List InsertionPosition position = evaluateRandom(P,S,v) try (insert(P,S,v, position) OR notInsert(P,S,v, position)) %0lPZ0 Z0 Z0 Z%y33}              $ +|B  TDԔ?   |B  TDԔ?@@ H  0޽h ? f3|  0(  x  c $tP   x  c $Դ@`  H  0޽h ? f3|  0(  x  c $P   x  c $   H  0޽h ? f3|  0(  x  c $P   x  c $t  H  0޽h ? f3|  F(  x  c $P     c $D  "p`PpH  0޽h ? f3|  0(  x  c $P   x  c $d  H  0޽h ? f3|  0(  x  c $P   x  c $D  H  0޽h ? f3|  0(  x  c $P   x  c $  H  0޽h ? f3|  0(  x  c $ĄP   x  c $$   H  0޽h ? f3|   V N   (  x  c $P   x  c $     B CDEF1?  @`@    B CDEF1?  @`@     BCDEF o?0`@` @@0     BCDEFo?0` @ p     B`CDEFo?`0P` @ p     BCDEF o?0`@` @@@      BCDEFo?0` @ `      B`CDEFo?`0P` @    @ ZG633331?p@     `G?I533331? ` H  0޽h ? f3|  $(  r  S DP   r  S   H  0޽h ? f3|!  {!s! 13 !(  r  S $P   2  Z1?p2  Z1?0 p 2  Z1? p 2  Z1? p0     `o?`     `1?@ [ visitedByi1" 2    2   Z1? p 2   Z1? p @2   Z1?0  p 2  Z1?  p 2  Z1?  p 0    `o?    `1?  [ visitedByi2" 2    2  Z1?@2  Z1?@@2  Z1?0 @ 2  Z1? @ 2  Z1? @0    `o?P    `d1?` [ visitedByi3" 2       `$1?  Xtruck k1" 2      `1?Pp Xtruck k2" 2      `1?  Xtruck k3" 2      `D1? @  Xtruck k4" 2      `1?p   Xtruck k5" 2   l `  ' ` ,$D 0 !  BCDEF1? P  @`P P< $  `1?`P  Reschedule k4 ok without i28 2    ,     l   ( ,$D 0  "  BCDEF1? P  @` < %  `1? P  Reschedule k1 ok without i38 2    ,     l   ) ,$D 0  #  BCDEF33331? P  @` B &  `D1?P  "Reschedule k3 ok with all clients8# 2   ,      2 * Z1?p@*l pp  1pp ,$D 0r  ZG_71?p 2 + Z1?p  2 . Z1?p@0l     2  ,$D 0r   `G|:H(@ B.DOQSy`}y=CGGpOh+'0x` p|    )Constraint Prrogramming and Local SearchMi LS and CP P0Filippo Focacci, Franois Laburthe, Andrea LodiUC:\Program Files\Microsoft Office\Templates\1036\Prsentation gnrale du projet.pot6michela815Microsoft PowerPoint 7.0t O@@½p@@踔@s@ ZmaG"oM   =& &&#TNPPp0D x & TNPP &&TNPP    &&--&&/_- $1b- $--4h- $--CC7o- $CCZZ Presentazione su schermoe&ILOG, BOUYGUES, Universiti di Bologna ^j dTimes New RomanArial WingdingsSymbol Courier New Prsentation gnrale du projet(Constraint Programming and Local SearchOutlineWhat this tutorial addresses0When should you enquire about CP / LS hybrids ?When cant it help ?Comparing CP and LS Opportunities for collaborationOutline"A didactic transportation problemA simple model for dTPModel Model (2)A CP approachA CP approachSolving through CPDifficulties with CPA local search approachLocal search for dTPNeighborhoods for dTPNeighborhoods!Driving the local search processDifficulties with LS ConclusionOutlineSequential combination: LS-CP DiscussionSequential combination: CP-LSGreedy insertion algorithmGreedy insertion for dTP DiscussionA systematic combination DiscussionOutline#Master / sub-problem decompositionPurpose of decompositionA decomposition on dTP DiscussionOutlineConstrained local searchConstrained local searchNode Exchange: version 1 Node Exchange: version 1 Node Exchange: version 1 Node Exchange: version 2 Node Exchange: version 2 OutlineNode Exchange: even more CPNode Exchange: nhood modelNode Exchange: nhood modelNode Exchange: nhood model Node Exchange: nhood model Node Exchange: nhood model Node Exchange: nhood model !Local Search via solution deltas'LS via solution deltas : Node Exchange1LS via solution deltas: explore the neighborhood4Exploring the neighborhood through solution deltas!Local Search via solution deltasOutlineLarge neighborhood search!Large neighborhood search on dTP!Large neighborhood search on dTP!Large neighborhood search on dTP!Large neighborhood search on dTPLarge neighborhood searchSelecting shuffle setsShuffle sets for dTPA few hints for LNS with CPOutlineLocal moves over a heuristicLocal search over a heuristic0Local search over the value selection heuristicRestricted candidate listRestricted candidate listRestricted candidate listGRASPGRASPDiscrepancy based searchDiscrepancy based search&CP + some LS: putting things together&CP + some LS: putting things together3Local search over the variable selection heuristicLocal moves on a heuristicPreference-based programmingOutline%Local Search and Greedy ConstructionIncremental Local OptimizationILO for general CSPs ILO illustrated on dTPIllustration on a search space(Ejection chains during a greedy processEjection chains on dTPFinding a good ejection chain Conclusion Caratteri utilizzatiModello strutturaTitoli diapositive^ 6> _PID_GUIDAN{EE30EE3E-425B-11D6-B7C2-0050046C92E7}_michela  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghiklmnopqrstuvwyz{|}~Root EntrydO)Current UserSummaryInformation(j4PowerPoint Document(DocumentSummaryInformation8xRoot EntrydO)ިtCurrent UserhSummaryInformation(j4PowerPoint Document(0_Dpartement InformatiqueDpartement Informatique