The equivalence class subset algorithm is a powerful
tool for solving a wide variety of constraint satisfaction problems and
is based on the use of a decision function which has a very high but
not perfect accuracy. Perfect accuracy is not required in the decision
function as even a suboptimal solution contains valuable information
that can be used to help find an optimal solution. In the hardest
problems, the decision function can break down leading to a
suboptimal solution where there are more equivalence classes than
are necessary and which can be viewed as a mixture of good decision
and bad decisions. By choosing a subset of the decisions made in
reaching a suboptimal solution an iterative technique can lead to an
optimal solution, using series of steadily improved suboptimal
solutions. The goal is to reach an optimal solution as quickly as
possible. Various techniques for choosing the decision subset are
evaluated.
[1] S. Cook and D. Mitchell. (1997). "Finding Hard Instances of the
Satisfiability Problem: A Survey", Satisfiability Problems: Theory and
Applications. American Mathematical Society, Providence, Rhode
Island.
[2] C.H. Papadimitrou and K. Steiglitz, "Combinatorial Optimization:
Algorithms and Complexity", Dover, ISBM 0-486-40258-4, pp. 344.
[3] Duffany, J.L., "Statistical Characterization of NP-Complete Problems",
Foundations of Computer Science Conference, World Computer
Congress, Las Vegas, Nevada, July 14-17, 2008.
[4] Duffany, J.L. "Systems of Inequations", 4th LACCEI Conference,
Mayaguez, PR, June 21-23, 2006.
[5] Duffany, J.L. "Generalized Decision Function and Gradient Search
Technique for NP-Complete Problems", XXXII CLEI Conference,
Santiago Chile, August 20-23, 2006.
[6] E. Horowitz, S. Sahni, "Fundamentals of Computer Algorithms",
Computer Science Press, Maryland, 1978.
[7] R. M. Karp, "Reducibility Among Combinatorial Problems", In
Complexity of Computer Computation, pages 85-104. Plenum Press,
New York, 1972.
[8] Weisstein, E. W., "NP-Hard Problem." From MathWorld--A Wolfram
Web Resource. http://mathworld.wolfram.com/NP-HardProblem.html.
[9] Weisstein, E. W., "NP-Complete Problem." From MathWorld--A
Wolfram Web Resource: http:// mathworld.wolfram.com/NPCompleteProblem.
html.
[10] Weisstein, E. W., "Inequation." From MathWorld--A Wolfram Web
Resource. http:// mathworld.wolfram.com /Inequation.html.
[11] Wikipedia - Inequation page: http://en.wikipedia.org /wiki/Inequation.
[12] Duffany, J.L., "Optimal Solution of Constraint Satisfaction Problems",
International Conference on Applied Computer Science, Sharm el Sheik,
Egypt, January, 2009.
[13] http://mat.gsia.cmu.edu/COLOR/instances.html
[14] http://www.r-project.org
[1] S. Cook and D. Mitchell. (1997). "Finding Hard Instances of the
Satisfiability Problem: A Survey", Satisfiability Problems: Theory and
Applications. American Mathematical Society, Providence, Rhode
Island.
[2] C.H. Papadimitrou and K. Steiglitz, "Combinatorial Optimization:
Algorithms and Complexity", Dover, ISBM 0-486-40258-4, pp. 344.
[3] Duffany, J.L., "Statistical Characterization of NP-Complete Problems",
Foundations of Computer Science Conference, World Computer
Congress, Las Vegas, Nevada, July 14-17, 2008.
[4] Duffany, J.L. "Systems of Inequations", 4th LACCEI Conference,
Mayaguez, PR, June 21-23, 2006.
[5] Duffany, J.L. "Generalized Decision Function and Gradient Search
Technique for NP-Complete Problems", XXXII CLEI Conference,
Santiago Chile, August 20-23, 2006.
[6] E. Horowitz, S. Sahni, "Fundamentals of Computer Algorithms",
Computer Science Press, Maryland, 1978.
[7] R. M. Karp, "Reducibility Among Combinatorial Problems", In
Complexity of Computer Computation, pages 85-104. Plenum Press,
New York, 1972.
[8] Weisstein, E. W., "NP-Hard Problem." From MathWorld--A Wolfram
Web Resource. http://mathworld.wolfram.com/NP-HardProblem.html.
[9] Weisstein, E. W., "NP-Complete Problem." From MathWorld--A
Wolfram Web Resource: http:// mathworld.wolfram.com/NPCompleteProblem.
html.
[10] Weisstein, E. W., "Inequation." From MathWorld--A Wolfram Web
Resource. http:// mathworld.wolfram.com /Inequation.html.
[11] Wikipedia - Inequation page: http://en.wikipedia.org /wiki/Inequation.
[12] Duffany, J.L., "Optimal Solution of Constraint Satisfaction Problems",
International Conference on Applied Computer Science, Sharm el Sheik,
Egypt, January, 2009.
[13] http://mat.gsia.cmu.edu/COLOR/instances.html
[14] http://www.r-project.org
@article{"International Journal of Information, Control and Computer Sciences:60442", author = "Jeffrey L. Duffany", title = "Equivalence Class Subset Algorithm", abstract = "The equivalence class subset algorithm is a powerful
tool for solving a wide variety of constraint satisfaction problems and
is based on the use of a decision function which has a very high but
not perfect accuracy. Perfect accuracy is not required in the decision
function as even a suboptimal solution contains valuable information
that can be used to help find an optimal solution. In the hardest
problems, the decision function can break down leading to a
suboptimal solution where there are more equivalence classes than
are necessary and which can be viewed as a mixture of good decision
and bad decisions. By choosing a subset of the decisions made in
reaching a suboptimal solution an iterative technique can lead to an
optimal solution, using series of steadily improved suboptimal
solutions. The goal is to reach an optimal solution as quickly as
possible. Various techniques for choosing the decision subset are
evaluated.", keywords = "np-complete, complexity, algorithm.", volume = "3", number = "5", pages = "1425-6", }