**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Constraint satisfaction

Summary

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through
a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region.
The techniques used in constraint satisfaction depend on the kind of constraints being considered. Often used are constraints on a finite domain, to the point that constraint satisfaction problems are typically identified with problems based on constraints on a finite domain. Such problems are usually solved via search, in particular a form of backtracking or local search. Constraint propagation are other methods used on such problems; most of them are incomplete in general, that is, they may solve the problem or prove it unsatisfiable, but not always. Constraint propagation methods are also used in conjunction with search to make a given problem simpler to solve. Other considered kinds of constraints are on real or rational numbers; solving problems on these constraints is done via variable elimination or the simplex algorithm.
Constraint satisfaction as a general problem originated in the field of artificial intelligence in the 1970s (see for example ). However, when the constraints are expressed as multivariate linear equations defining (in)equalities, the field goes back to Joseph Fourier in the 19th century: George Dantzig's invention of the Simplex Algorithm for Linear Programming (a special case of mathematical optimization) in 1946 has allowed determining feasible solutions to problems containing hundreds of variables.
During the 1980s and 1990s, embedding of constraints into a programming language were developed. The first languages devised expressly with intrinsic support for constraint programming was Prolog. Since then, constraint-programming libraries have become available in other languages, such as C++ or Java (e.g., Choco for Java).

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related MOOCs

Loading

Related courses (47)

Related people (11)

Related publications (29)

Related concepts (15)

Related lectures (371)

ME-104: Introduction to structural mechanics

The student will acquire the basis for the analysis of static structures and deformation of simple structural elements. The focus is given to problem-solving skills in the context of engineering desig

MATH-212: Analyse numérique et optimisation

L'étudiant apprendra à résoudre numériquement divers problèmes mathématiques. Les propriétés théoriques de ces
méthodes seront discutées.

PHYS-101(g): General physics : mechanics

Le but du cours de physique générale est de donner à l'étudiant les notions de base nécessaires à la compréhension des phénomènes physiques. L'objectif est atteint lorsque l'étudiant est capable de pr

Related MOOCs (2)

Related units (1)

Local consistency

In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier to solve. Various kinds of local consistency conditions are leveraged, including node consistency, arc consistency, and path consistency. Every local consistency condition can be enforced by a transformation that changes the problem without changing its solutions.

Constraint satisfaction problem

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families.

Constraint satisfaction

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered.

Loading

Loading

Loading

Optimisation with Constraints: Interior Point Algorithm

Explores optimization with constraints using KKT conditions and interior point algorithm on two examples of quadratic programming.

Calculus of Variations and Euler's Elastica

Covers variational methods, equilibrium shapes, Euler's Elastica, and numerical and analytical methods for solving Euler's Elastica.

Constraints and Lagrange

Covers constraints, Lagrange equations, generalized coordinates, cyclic coordinates, conservation laws, and Hamilton formalism.

The Art of Structures I - Cables and arcs

L'art des structures propose une découverte du fonctionnement des structures porteuses, telles que les bâtiments, les toitures ou les ponts. Ce cours présente les principes du dimensionnement et les s

The Art of Structures II - Lattice structures, beams and frames

Les structures en treillis, en poutre, en dalles et en cadre sont essentielles pour une grande partie des constructions modernes : immeubles pour l'habitation ou de bureaux, halles et usines, ponts, o

We consider high-dimensional random optimization problems where the dynamical variables are subjected to nonconvex excluded volume constraints. We focus on the case in which the cost function is a sim

,

Substitutability and interchangeability in constraint satisfaction problems (CSPs) have been used as a basis for search heuristics, solution adaptation and abstraction techniques. In this paper, we co

Mario Paolone, Rahul Kumar Gupta, Fabrizio Sossan, Vladimir Sovljanski

The paper contributes to improving the computational performance of controls of distributed energy resources (DERs) in distribution grids for efficient real-time control and short-term scheduling. The