644:
651:
The figure shows a simple graph coloring example with colors as vertices, such that no two vertices which are joined by an edge have the same color. The available colors at each vertex are shown. The colors yellow, green, brown, red, blue, pink represent vertex
42:(CSP). A CSP is a mathematical problem in which objects, represented by variables, are subject to constraints on the values of those variables; the goal in a CSP is to assign values to the variables that are consistent with the constraints. If two variables
101:
The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene
Freuder in 1991. The interchangeability algorithm reduces the search space of
769:
Weigel, R., Faltings, B.: Interchangeability for Case
Adaptation in Configura- tion Problems. In Proceedings of the AAAI98 Spring Symposium on Multimodal Reasoning, Stanford, CA, TR SS-98-04. (1998)
633:
391:
440:
787:
Full
Dynamic Substitutability by SAT Encoding by Steven Prestwich, Cork Constraint Computation Centre, Department of Computer Science, University College, Cork, Ireland
656:
and are fully interchangeable by definition. For example, substituting maroon for green in the solution orange|X (orange for X), green|Y will yield another solution.
505:
537:
472:
209:
17:
242:
The algorithm can be used to explicitly find solutions to a constraint satisfaction problem. The algorithm can also be run for
742:
Haselbock, A.: Exploiting
Interchangeabilities in Constraint Satisfaction Problems. In Proc. of the 13 th IJCAI (1993) 282–287
190:
with respect to a set A of variable assignments if and only if they are fully interchangeable in the subproblem induced by A.
542:
692:, Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Centre de Mathématiques et d'Informatique, France.
803:
39:
778:
Neagu, N., Faltings, B.: Exploiting
Interchangeabilities for Case Adaptation. In Proc. of the 4th ICCBR01 (2001)
751:
Weigel, R., Faltings, B.: Compiling constraint satisfaction problems. Artificial
Intelligence 115 (1999) 257–289
311:
300:
In the case of neighborhood interchangeable algorithm, if we assign the worst case bound to each loop. Then for
730:
78:
variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the
760:
Choueiry, B.Y.: Abstraction
Methods for Resource Allocation. PhD thesis, EPFL PhD Thesis no 1292 (1994)
689:
665:
664:
In
Computer Science, the interchangeability algorithm has been extensively used in the fields of
403:
669:
477:
285:
Move to if present, construct if not, a node of the discrimination tree corresponding to w|W
224:
Move to if present, construct if not, a node of the discrimination tree corresponding to w|W
510:
445:
8:
103:
717:
150:
is neighbourhood interchangeable with value b if and only if for every constraint on
31:
107:
79:
204:
Finds neighborhood interchangeable values in a CSP. Repeat for each variable:
82:
for solutions to a CSP problem may be reduced. For example, if solutions with
797:
154:, the values compatible with v = a are exactly those compatible with v = b.
718:
643:
249:
Finds k-interchangeable values in a CSP. Repeat for each variable:
246:
steps as a preprocessor to simplify the subsequent backtrack search.
170:
if and only if every solution in which v = a remains a solution when
130:
if and only if every solution in which v = a remains a solution when
66:) without changing the nature of the problem or its solutions, then
690:"Reasoning by dominance in Not-Equals binary constraint networks"
90:=2 have been tried, then by interchange symmetry, solutions with
199:
733:, University of Artrois, Franc In the meantime, you ce.
308:
values for a variable, then we have a bound of :
174:
is substituted for a (but not necessarily vice versa).
720:. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233
545:
513:
480:
448:
406:
314:
672:, abstraction frame-works and solution adaptation.
278:constitute a solution to the subproblem induced by
27:
Technique to solve constraint satisfaction problems
627:
531:
499:
466:
434:
385:
628:{\displaystyle O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})}
234:
50:in a CSP may be swapped for each other (that is,
795:
106:algorithms, thereby improving the efficiency of
400:-interchangeability algorithm for a worst case
731:"About Neighborhood Substitutability in CSP's"
38:is a technique used to more efficiently solve
539:-tuples of values, then the bound is :
221:Repeat for each value w consistent with v:
396:Similarly, the complexity analysis of the
386:{\displaystyle O(nd(n-l)*d)=O(n^{2}d^{2})}
647:Example for Interchangeability Algorithm.
200:Neighborhood Interchangeability Algorithm
642:
218:Repeat for each neighboring variable W:
688:Belaid Benhamou and Mohamed Reda Saidi
14:
796:
712:
710:
708:
706:
704:
702:
700:
698:
295:
18:Interchangeability (computer science)
126:is fully interchangeable with value
695:
186:is dynamically interchangeable for
24:
166:is fully substitutable with value
25:
815:
40:constraint satisfaction problems
729:Assef Chmeiss and Lakhdar Sais
659:
253:Build a discrimination tree by:
781:
772:
763:
754:
745:
736:
723:
682:
622:
599:
590:
549:
526:
514:
461:
449:
429:
410:
380:
357:
348:
339:
327:
318:
304:variables, which have at most
113:
13:
1:
675:
238:-interchangeability algorithm
194:
143:Neighbourhood Interchangeable
98:=2 need not be investigated.
36:interchangeability algorithm
7:
179:Dynamically Interchangeable
10:
820:
638:
435:{\displaystyle O(n^{k-1})}
256:Repeat for each value, v:
215:Repeat for each value, v:
474:-tuples of variables and
263:− 1)-tuple of variables
670:graph coloring problems
666:artificial intelligence
500:{\displaystyle d^{k-1}}
182:A value a for variable
162:A value a for variable
146:A value a for variable
122:A value a for variable
804:Constraint programming
648:
629:
533:
501:
468:
436:
387:
274:, which together with
646:
630:
534:
532:{\displaystyle (k-1)}
502:
469:
467:{\displaystyle (k-1)}
437:
388:
270:− 1)-tuple of values
119:Fully Interchangeable
543:
511:
478:
446:
404:
312:
296:Complexity analysis
210:discrimination tree
159:Fully Substitutable
134:is substituted for
104:backtracking search
649:
625:
529:
497:
464:
432:
383:
266:Repeat for each (
259:Repeat for each (
16:(Redirected from
811:
788:
785:
779:
776:
770:
767:
761:
758:
752:
749:
743:
740:
734:
727:
721:
714:
693:
686:
634:
632:
631:
626:
621:
620:
611:
610:
589:
588:
573:
572:
538:
536:
535:
530:
506:
504:
503:
498:
496:
495:
473:
471:
470:
465:
441:
439:
438:
433:
428:
427:
392:
390:
389:
384:
379:
378:
369:
368:
32:computer science
21:
819:
818:
814:
813:
812:
810:
809:
808:
794:
793:
792:
791:
786:
782:
777:
773:
768:
764:
759:
755:
750:
746:
741:
737:
728:
724:
716:Freuder, E.C.:
715:
696:
687:
683:
678:
662:
655:
641:
616:
612:
606:
602:
578:
574:
562:
558:
544:
541:
540:
512:
509:
508:
485:
481:
479:
476:
475:
447:
444:
443:
417:
413:
405:
402:
401:
374:
370:
364:
360:
313:
310:
309:
298:
281:
277:
273:
245:
240:
202:
197:
189:
185:
173:
169:
165:
153:
149:
138:and vice versa.
137:
133:
129:
125:
116:
76:interchangeable
62:is replaced by
54:is replaced by
28:
23:
22:
15:
12:
11:
5:
817:
807:
806:
790:
789:
780:
771:
762:
753:
744:
735:
722:
694:
680:
679:
677:
674:
661:
658:
653:
640:
637:
624:
619:
615:
609:
605:
601:
598:
595:
592:
587:
584:
581:
577:
571:
568:
565:
561:
557:
554:
551:
548:
528:
525:
522:
519:
516:
494:
491:
488:
484:
463:
460:
457:
454:
451:
431:
426:
423:
420:
416:
412:
409:
382:
377:
373:
367:
363:
359:
356:
353:
350:
347:
344:
341:
338:
335:
332:
329:
326:
323:
320:
317:
297:
294:
293:
292:
291:
290:
289:
288:
287:
286:
279:
275:
271:
254:
243:
239:
233:
232:
231:
230:
229:
228:
227:
226:
225:
213:
201:
198:
196:
193:
192:
191:
187:
183:
180:
176:
175:
171:
167:
163:
160:
156:
155:
151:
147:
144:
140:
139:
135:
131:
127:
123:
120:
115:
112:
110:CSP problems.
26:
9:
6:
4:
3:
2:
816:
805:
802:
801:
799:
784:
775:
766:
757:
748:
739:
732:
726:
719:
713:
711:
709:
707:
705:
703:
701:
699:
691:
685:
681:
673:
671:
667:
657:
645:
636:
617:
613:
607:
603:
596:
593:
585:
582:
579:
575:
569:
566:
563:
559:
555:
552:
546:
523:
520:
517:
492:
489:
486:
482:
458:
455:
452:
424:
421:
418:
414:
407:
399:
394:
375:
371:
365:
361:
354:
351:
345:
342:
336:
333:
330:
324:
321:
315:
307:
303:
284:
283:
269:
265:
264:
262:
258:
257:
255:
252:
251:
250:
247:
237:
223:
222:
220:
219:
217:
216:
214:
211:
207:
206:
205:
181:
178:
177:
161:
158:
157:
145:
142:
141:
121:
118:
117:
111:
109:
105:
99:
97:
93:
89:
85:
81:
77:
73:
69:
65:
61:
57:
53:
49:
45:
41:
37:
33:
19:
783:
774:
765:
756:
747:
738:
725:
684:
663:
660:Applications
650:
397:
395:
305:
301:
299:
267:
260:
248:
241:
235:
203:
100:
95:
91:
87:
83:
80:search space
75:
71:
67:
63:
59:
55:
51:
47:
43:
35:
29:
114:Definitions
108:NP-complete
676:References
195:Pseudocode
583:−
567:−
521:−
490:−
456:−
422:−
343:∗
334:−
798:Category
208:Build a
639:Example
442:, with
94:=1 and
86:=1 and
507:, for
34:, an
74:are
70:and
58:and
46:and
212:by:
30:In
800::
697:^
668:,
635:.
393:.
282::
654:Y
623:)
618:k
614:d
608:k
604:n
600:(
597:O
594:=
591:)
586:1
580:k
576:d
570:l
564:k
560:n
556:d
553:n
550:(
547:O
527:)
524:1
518:k
515:(
493:1
487:k
483:d
462:)
459:1
453:k
450:(
430:)
425:1
419:k
415:n
411:(
408:O
398:k
381:)
376:2
372:d
366:2
362:n
358:(
355:O
352:=
349:)
346:d
340:)
337:l
331:n
328:(
325:d
322:n
319:(
316:O
306:d
302:n
280:W
276:v
272:w
268:k
261:k
244:k
236:K
188:b
184:v
172:b
168:b
164:v
152:v
148:v
136:a
132:b
128:b
124:v
96:A
92:B
88:B
84:A
72:B
68:A
64:A
60:B
56:B
52:A
48:B
44:A
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
