Optimal Solution of Constraint Satisfaction Problems

Authors: Jeffrey L. Duffany

Abstract:

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).

Keywords: Algorithm, complexity, constraint, np-complete.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057197

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.