Home  About us  Contact
 

Constraint Satisfaction Problems (constraint + satisfaction_problem)

Distribution by Scientific Domains
Mathematics and Statistics66%

Selected Abstracts

A personal perspective on problem solving by general purpose solvers

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 3 2010
Toshihide Ibaraki
Abstract To solve the problems that abound in real-world applications, we are proposing an approach of using general-purpose solvers, as we cannot afford to develop special-purpose algorithms for all individual problems. The existing general-purpose solvers such as linear programming and integer programming are very useful but not sufficient. To improve the situation, we have developed solvers for other standard problems such as the constraint satisfaction problem and the resource-constrained project scheduling problem among others. In this article, we describe why general-purpose solvers are needed, what kinds of solvers we considered, how they were developed and where they have been applied. [source]

Solving partial constraint satisfaction problems with tree decomposition

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2002
Arie M. C. A. Koster
Abstract In this paper, we describe a computational study to solve hard partial constraint satisfaction problems (PCSPs) to optimality. The PCSP is a general class of problems that contains a diversity of problems, such as generalized subgraph problems, MAX-SAT, Boolean quadratic programs, and assignment problems like coloring and frequency planning. We present a dynamic programming algorithm that solves PCSPs based on the structure (tree decomposition) of the underlying constraint graph. With the use of dominance and bounding techniques, we are able to solve small and medium-size instances of the problem to optimality and to obtain good lower bounds for large-size instances within reasonable time and memory limits. © 2002 Wiley Periodicals, Inc. [source]

Verified global optimization with GloptLab

PROCEEDINGS IN APPLIED MATHEMATICS & MECHANICS, Issue 1 2007
Ferenc Domes
GloptLab is a testing and development platform for solving quadratic constraint satisfaction problems, written in MATLAB. All applied methods are rigorous, hence it is guaranteed that no feasible point is lost. Some emphasis is given to finding a bounded initial box containing all feasible points, in cases where other complete solvers rely on non-rigorous heuristics. The algorithms implemented in GloptLab are used to reduce the search space: scaling, constraint propagation, linear relaxations, strictly convex enclosures, conic methods, and branch and bound. From the method repertoire custom made strategies can be built, with a user friendly graphical interface. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [source]

The satisfiability threshold for randomly generated binary constraint satisfaction problems,,

RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2006
Alan Frieze
We study two natural models of randomly generated constraint satisfaction problems. We determine how quickly the domain size must grow with n to ensure that these models are robust in the sense that they exhibit a non-trivial threshold of satisfiability, and we determine the asymptotic order of that threshold. We also provide resolution complexity lower bounds for these models. One of our results immediately yields a theorem regarding homomorphisms between two random graphs. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]