Optimal Solution of Constraint Satisfaction Problems

An optimal solution for a large number of constraint satisfaction problems can be found using the technique of substitution and elimination of variables analogous to the technique that is used to solve systems of equations. A decision function f(A)=max(A2) is used to determine which variables to eliminate. The algorithm can be expressed in six lines and is remarkable in both its simplicity and its ability to find an optimal solution. However it is inefficient in that it needs to square the updated A matrix after each variable elimination. To overcome this inefficiency the algorithm is analyzed and it is shown that the A matrix only needs to be squared once at the first step of the algorithm and then incrementally updated for subsequent steps, resulting in significant improvement and an algorithm complexity of O(n3).

Authors:

• Jeffrey L. Duffany

Keywords:

• Algorithm
• complexity
• constraint
• np-complete.

References:

[1] C.H. Papadimitrou and K. Steiglitz, "Combinatorial Optimization:
Algorithms and Complexity", Dover, ISBM 0-486-40258-4, pp. 344.
[2] Duffany, J.L., "Statistical Characterization of NP-Complete Problems",
Foundations of Computer Science Conference, World Computer
Congress, Las Vegas, Nevada, July 14-17, 2008.
[3] Duffany, J.L. "Systems of Inequations", 4th LACCEI Conference,
Mayaguez, PR, June 21-23, 2006.
[4] Duffany, J.L. "Generalized Decision Function and Gradient Search
Technique for NP-Complete Problems", XXXII CLEI Conference,
Santiago Chile, August 20-23, 2006.
[5] E. Horowitz, S. Sahni, "Fundamentals of Computer Algorithms",
Computer Science Press, Maryland, 1978.
[6] R. M. Karp, "Reducibility among Combinatorial Problems", In
Complexity of Computer Computation, pages 85-104. Plenum Press,
New York, 1972.
[7] Weisstein, E. W., "NP-Hard Problem." From MathWorld--A Wolfram
Web Resource. http://mathworld.wolfram.com/NP-HardProblem.html
[8] Weisstein, E. W., "NP-Complete Problem." From MathWorld--A
Wolfram Web Resource: http:// mathworld.wolfram.com/NPCompleteProblem.
html
[9] Weisstein, E. W., "Inequation." From MathWorld--A Wolfram Web
Resource. http:// mathworld.wolfram.com /Inequation.html
[10] Wikipedia - Inequation page: http://en.wikipedia.org /wiki/Inequation
[11] J. Manuch, D.R. Gaur, "Fitting protein chains to cubic lattice is NPcomplete",
Journal of Bioinformatics and Computational Biology, Vol.
6, No. 1. (February 2008), pp. 93-106.
[12] S. Russell and P. Norvig, Ärtificial Intelligence, A Modern Approach",
Chapter 5, Second Edition, 2003, Prentice Hall, ISBN 0-13-790395-2.