Interchangeability algorithm - Revision history

Maxeto0910: /* Example */ no sentence

2024-10-06T08:42:32Z

Example: no sentence

← Previous revision		Revision as of 08:42, 6 October 2024
Line 52:		Line 52:
	==Example==		==Example==

	[[File:Interchangeability.png\|thumb\|Example for ~~Interchangeability~~ ~~Algorithm.~~]]		[[File:Interchangeability.png\|thumb\|Example for an interchangeability algorithm]]
	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 {{var\|Y}} 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.		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 {{var\|Y}} 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.

David Eppstein: Undid revision 1226891997 by 2603:8000:D300:3650:54E:99BD:2917:FE0 (talk) this is a French name, not English; we should use the French spelling

2024-06-02T18:40:14Z

Undid revision 1226891997 by 2603:8000:D300:3650:54E:99BD:2917:FE0 (talk) this is a French name, not English; we should use the French spelling

← Previous revision		Revision as of 18:40, 2 June 2024
Line 2:		Line 2:
	In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.		In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.

	The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des ~~Systems~~ (LSIS), Centre de Mathématiques et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-completeness\|NP-complete]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc		The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Centre de Mathématiques et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-completeness\|NP-complete]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc
	In the meantime, you ce.</ref>		In the meantime, you ce.</ref>

2603:8000:D300:3650:54E:99BD:2917:FE0: sp

2024-06-02T12:24:46Z

← Previous revision		Revision as of 12:24, 2 June 2024
Line 2:		Line 2:
	In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.		In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.

	The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des ~~Systmes~~ (LSIS), Centre de Mathématiques et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-completeness\|NP-complete]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc		The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des Systems (LSIS), Centre de Mathématiques et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-completeness\|NP-complete]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc
	In the meantime, you ce.</ref>		In the meantime, you ce.</ref>

BD2412: /* top */clean up spacing around commas and other punctuation fixes, replaced: ,C → , C

2024-01-24T00:10:03Z

top: clean up spacing around commas and other punctuation fixes, replaced: ,C → , C

← Previous revision		Revision as of 00:10, 24 January 2024
Line 2:		Line 2:
	In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.		In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.

	The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des Systmes (LSIS),Centre de Mathématiques et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-completeness\|NP-complete]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc		The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des Systmes (LSIS), Centre de Mathématiques et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-completeness\|NP-complete]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc
	In the meantime, you ce.</ref>		In the meantime, you ce.</ref>

JL-Bot: removing orphan template as not a valid orphan

2023-07-30T07:17:15Z

removing orphan template as not a valid orphan

← Previous revision		Revision as of 07:17, 30 July 2023
Line 1:		Line 1:
	{{Short description\|Technique to solve constraint satisfaction problems}}		{{Short description\|Technique to solve constraint satisfaction problems}}
	{{Orphan\|date=August 2014}}
	In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.		In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.

Aithus: Adding short description: "Technique to solve constraint satisfaction problems"

2023-06-22T06:56:23Z

Adding short description: "Technique to solve constraint satisfaction problems"

← Previous revision		Revision as of 06:56, 22 June 2023
Line 1:		Line 1:
			{{Short description\|Technique to solve constraint satisfaction problems}}
	{{Orphan\|date=August 2014}}		{{Orphan\|date=August 2014}}
	In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.		In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.

Frap at 15:10, 21 February 2020

2020-02-21T15:10:37Z

← Previous revision		Revision as of 15:10, 21 February 2020
Line 1:		Line 1:
	{{Orphan\|date=August 2014}}		{{Orphan\|date=August 2014}}

	<s></s>

	In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.		In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.

	The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des Systmes (LSIS),Centre de Mathématiques et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-~~Complete~~]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc		The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des Systmes (LSIS),Centre de Mathématiques et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-completeness\|NP-complete]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc
	In the meantime, you ce.</ref>		In the meantime, you ce.</ref>

Line 34:		Line 31:
	::::Move to if present, construct if not, a node of the discrimination tree corresponding to w\|W<ref name="main" />		::::Move to if present, construct if not, a node of the discrimination tree corresponding to w\|W<ref name="main" />

	=== K-~~Interchangeability~~ ~~Algorithm~~ ===		=== ''K''-interchangeability algorithm ===

	The algorithm can be used to explicitly find solutions to a constraint satisfaction problem. The algorithm can also be run for {{var\|k}} steps as a preprocessor to simplify the subsequent backtrack search.		The algorithm can be used to explicitly find solutions to a constraint satisfaction problem. The algorithm can also be run for {{var\|k}} steps as a preprocessor to simplify the subsequent backtrack search.
Line 56:		Line 53:

	[[File:Interchangeability.png\|thumb\|Example for Interchangeability Algorithm.]]		[[File:Interchangeability.png\|thumb\|Example for Interchangeability Algorithm.]]
	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 Y 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.		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 {{var\|Y}} 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.

	==Applications==		==Applications==

Frap: MOS:HEAD

2019-12-25T19:24:29Z

MOS:HEAD

← Previous revision		Revision as of 19:24, 25 December 2019
Line 11:		Line 11:

	;Fully Interchangeable		;Fully Interchangeable
	:A value a for variable v is fully interchangeable with value b if and only if every solution in which v = a remains a solution when b is substituted for a and vice versa.<ref name="main" />		:A value a for variable {{var\|v}} is fully interchangeable with value {{var\|b}} if and only if every solution in which v = a remains a solution when {{var\|b}} is substituted for {{var\|a}} and vice versa.<ref name="main" />

	;Neighbourhood Interchangeable		;Neighbourhood Interchangeable
	:A value a for variable v is neighbourhood interchangeable with value b if and only if for every constraint on v, the values compatible with v = a are exactly those compatible with v = b.<ref name="main" />		:A value a for variable {{var\|v}} is neighbourhood interchangeable with value b if and only if for every constraint on {{var\|v}}, the values compatible with v = a are exactly those compatible with v = b.<ref name="main" />

	;Fully Substitutable		;Fully Substitutable
	:A value a for variable v is fully substitutable with value b if and only if every solution in which v = a remains a solution when b is substituted for a (but not necessarily vice versa).<ref name="main" />		:A value a for variable {{var\|v}} is fully substitutable with value {{var\|b}} if and only if every solution in which v = a remains a solution when {{var\|b}} is substituted for a (but not necessarily vice versa).<ref name="main" />

	;Dynamically Interchangeable		;Dynamically Interchangeable
	:A value a for variable v is dynamically interchangeable for b with respect to a set A of variable assignments if and only if they are fully interchangeable in the subproblem induced by A.<ref name="main" />		:A value a for variable {{var\|v}} is dynamically interchangeable for {{var\|b}} with respect to a set A of variable assignments if and only if they are fully interchangeable in the subproblem induced by A.<ref name="main" />

	==Pseudocode==		==Pseudocode==

	=== Neighborhood Interchangeability Algorithm ===		=== Neighborhood Interchangeability Algorithm ===


	Finds neighborhood interchangeable values in a CSP.		Finds neighborhood interchangeable values in a CSP.
Line 37:		Line 36:
	=== K-Interchangeability Algorithm ===		=== K-Interchangeability Algorithm ===

	The algorithm can be used to explicitly find solutions to a constraint satisfaction problem. The algorithm can also be run for k steps as a preprocessor to simplify the subsequent backtrack search.		The algorithm can be used to explicitly find solutions to a constraint satisfaction problem. The algorithm can also be run for {{var\|k}} steps as a preprocessor to simplify the subsequent backtrack search.

	Finds k-interchangeable values in a CSP.		Finds k-interchangeable values in a CSP.
Line 43:		Line 42:
	:Build a discrimination tree by:		:Build a discrimination tree by:
	:Repeat for each value, v:		:Repeat for each value, v:
	::Repeat for each (k-1)-tuple of variables		::Repeat for each (''k'' − 1)-tuple of variables
	:::Repeat for each (k-1)-tuple of values w, which together with v constitute a solution to the subproblem induced by W:		:::Repeat for each (''k'' − 1)-tuple of values {{var\|w}}, which together with {{var\|v}} constitute a solution to the subproblem induced by {{var\|W}}:
	::::Move to if present, construct if not, a node of the discrimination tree corresponding to w\|W<ref name="main" />		::::Move to if present, construct if not, a node of the discrimination tree corresponding to w\|W<ref name="main" />

	==Complexity ~~Analysis~~==		==Complexity analysis==

	In the case of neighborhood interchangeable algorithm, if we assign the worst case bound to each loop. Then for ''n'' variables, which have at most ''d'' values for a variable, then we have a bound of :		In the case of neighborhood interchangeable algorithm, if we assign the worst case bound to each loop. Then for ''n'' variables, which have at most ''d'' values for a variable, then we have a bound of :

Tom.Reding: /* Applications */Rep typographic ligatures like "ﬁ" with plain text; possible ref cleanup; WP:GenFixes on, replaced: ﬁ → fi (2) using AWB

2017-11-22T17:16:05Z

Applications: Rep typographic ligatures like "ﬁ" with plain text; possible ref cleanup; WP:GenFixes on, replaced: ﬁ → fi (2) using AWB

← Previous revision		Revision as of 17:16, 22 November 2017
Line 60:		Line 60:

	==Applications==		==Applications==
	In Computer Science, the interchangeability algorithm has been extensively used in the fields of [[artificial intelligence]], [[graph coloring problem]]s, abstraction frame-works and solution adaptation.<ref name="main" /><ref>Haselbock, A.: Exploiting Interchangeabilities in Constraint Satisfaction Problems. In Proc. of the 13 th IJCAI (1993) 282–287</ref><ref>Weigel, R., Faltings, B.: Compiling constraint satisfaction problems. ~~Artiﬁcial~~ Intelligence 115 (1999) 257–289</ref><ref>Choueiry, B.Y.: Abstraction Methods for Resource Allocation. PhD thesis, EPFL PhD Thesis no 1292 (1994)</ref>		In Computer Science, the interchangeability algorithm has been extensively used in the fields of [[artificial intelligence]], [[graph coloring problem]]s, abstraction frame-works and solution adaptation.<ref name="main" /><ref>Haselbock, A.: Exploiting Interchangeabilities in Constraint Satisfaction Problems. In Proc. of the 13 th IJCAI (1993) 282–287</ref><ref>Weigel, R., Faltings, B.: Compiling constraint satisfaction problems. Artificial Intelligence 115 (1999) 257–289</ref><ref>Choueiry, B.Y.: Abstraction Methods for Resource Allocation. PhD thesis, EPFL PhD Thesis no 1292 (1994)</ref>
	<ref>Weigel, R., Faltings, B.: Interchangeability for Case Adaptation in ~~Conﬁgura~~-		<ref>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)</ref><ref>Neagu, N., Faltings, B.: Exploiting Interchangeabilities for Case Adaptation. In Proc. of the 4th ICCBR01 (2001)</ref><ref>Full Dynamic Substitutability by SAT Encoding by Steven Prestwich, Cork Constraint Computation Centre, Department of Computer Science, University College, Cork, Ireland</ref>		tion Problems. In Proceedings of the AAAI98 Spring Symposium on Multimodal Reasoning, Stanford, CA, TR SS-98-04. (1998)</ref><ref>Neagu, N., Faltings, B.: Exploiting Interchangeabilities for Case Adaptation. In Proc. of the 4th ICCBR01 (2001)</ref><ref>Full Dynamic Substitutability by SAT Encoding by Steven Prestwich, Cork Constraint Computation Centre, Department of Computer Science, University College, Cork, Ireland</ref>

Eumolpo: orthographic

2016-11-26T07:16:29Z

orthographic

← Previous revision		Revision as of 07:16, 26 November 2016
Line 5:		Line 5:
	In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.		In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.

	The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des Systmes (LSIS),Centre de ~~Mathmatiques~~ et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-Complete]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc		The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991.<ref>Belaid Benhamou and Mohamed Reda Saidi [http://www.scm.tees.ac.uk/users/p.gregory/symcon06/BenhamouSaidi.pdf "Reasoning by dominance in Not-Equals binary constraint networks"], Laboratoire des Sciences de l'Information et des Systmes (LSIS),Centre de Mathématiques et d'Informatique, France.</ref><ref name="main">Freuder, E.C.: [http://www.aaai.org/Papers/AAAI/1991/AAAI91-036.pdf Eliminating Interchangeable Values in Constraint Satisfaction Problems]. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233</ref> The interchangeability algorithm reduces the search space of [[backtracking search]] algorithms, thereby improving the efficiency of [[NP-Complete]] CSP problems.<ref>Assef Chmeiss and Lakhdar Sais [http://www.it.uu.se/research/group/astra/SymCon/SymCon03/Papers/Chmeiss.pdf "About Neighborhood Substitutability in CSP's"], University of Artrois, Franc
	In the meantime, you ce.</ref>		In the meantime, you ce.</ref>

← Previous revision		Revision as of 07:17, 30 July 2023
Line 1:		Line 1:
	{{Short description\|Technique to solve constraint satisfaction problems}}		{{Short description\|Technique to solve constraint satisfaction problems}}
	{{Orphan\|date=August 2014}}
	In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.		In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.

← Previous revision		Revision as of 06:56, 22 June 2023
Line 1:		Line 1:
			{{Short description\|Technique to solve constraint satisfaction problems}}
	{{Orphan\|date=August 2014}}		{{Orphan\|date=August 2014}}
	In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.		In [[computer science]], an '''interchangeability algorithm''' is a technique used to more efficiently solve [[constraint satisfaction problem]]s (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 ''A'' and ''B'' in a CSP may be swapped for each other (that is, ''A'' is replaced by ''B'' and ''B'' is replaced by ''A'') without changing the nature of the problem or its solutions, then ''A'' and ''B'' are ''interchangeable'' variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the [[Feasible region\|search space]] for solutions to a CSP problem may be reduced. For example, if solutions with ''A''=1 and ''B''=2 have been tried, then by interchange symmetry, solutions with ''B''=1 and ''A''=2 need not be investigated.