Constraints Programming

< < < <

Get flash to fully experience Pearltrees

Bartak

http://en.wikipedia.org/wiki/Combinatorial_search

Combinatorial optimization

In computer science and artificial intelligence , combinatorial search studies search algorithms for solving instances of problems that are believed to be hard in general, by efficiently exploring the usually large solution space of these instances. Combinatorial search algorithms achieve this efficiency by reducing the effective size of the search space or employing heuristics.

Constraint satisfaction problem

Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations.

Operations research

Operations research , or operational research in British usage, is a discipline that deals with the application of advanced analytical methods to help make better decisions. [ 1 ] It is often considered to be a sub-field of mathematics . [ 2 ] The terms management science and decision science are sometimes used as more modern-sounding synonyms. [ 3 ] Employing techniques from other mathematical sciences, such as mathematical modeling , statistical analysis , and mathematical optimization , operations research arrives at optimal or near-optimal solutions to complex decision-making problems. Because of its emphasis on human-technology interaction and because of its focus on practical applications, operations research has overlap with other disciplines, notably industrial engineering and operations management , and draws on psychology and organization science .

lecture06.pdf (application/pdf objekt)

lookahead lokalni vypocty - pomuzou s heuristickym prorezavanim.. by petr Oct 25

nebo primo k jadru veci - problemove zavisle heuristiky by petr Oct 25

value ordering - succeed -first - volime hodnotu, ktera nejmene omezi ostatni volne promenne (tak aby na ostatni souvisejici promenne zbyla co nejsirsi domena hodnot) apod. by petr Oct 25

variable ordering - fail-first variable - dom heuristika - najdeme tu, ktera ma nejvetsi pocet omezeni a tu se snazime vyresit prvni.. (stat s nejvetsim poctem jiz obarvenych sousedu) - deg heuristika - najdeme promennou s nejvetsim poctem volnych podminek (stat s nejvice sousedy), dom-deg avrianta... by petr Oct 25

promenne/hodnoty - vybirame spravnou strategii prohledavani S by petr Oct 25

Backmarking

In constraint satisfaction , backmarking is a variant of the backtracking algorithm.

Backjumping

In backtracking algorithms , backjumping is a technique that reduces search space , therefore increasing efficiency.

Look-ahead (backtracking)

In backtracking algorithms , look ahead is the generic term for a subprocedure that attempts to foresee the effects of choosing a branching variable to evaluate or one of its values.

Local consistency

In constraint satisfaction , local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. Several such conditions exist, the most known being node consistency , arc consistency , and path consistency .

složitost k-konzistence je exponenciální v k. by petr Oct 25

Je-li problém i-konzistentní i=1,..,n (n je počet proměnných), potom umíme řešit bez navracení) by petr Oct 25

Node/Arc/Path (k-) consistency by petr Oct 25

The AC-3 algorithm (short for Arc Consistency Algorithm #3) is one of a series of algorithms used for the solution of constraint satisfaction problems (or CSP's). It was developed by Alan Mackworth in 1977.

AC-3 algorithm

Constraint learning

In constraint satisfaction backtracking algorithms , constraint learning is a technique for improving efficiency. It works by recording new constraints whenever an inconsistency is found.

GECODE home

Distributed constraint optimization (DCOP or DisCOP) is the distributed analogue to constraint optimization . A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is either minimized or maximized. Distributed Constraint Satisfaction is a framework for describing a problem in terms of constraints that are known and enforced by distinct participants (agents).

Distributed constraint optimization

Constraint optimization

In constraint satisfaction , constrained optimization (also called constraint optimization ) seeks for a solution maximizing or minimizing a cost function . [ edit ] Definition A constraint optimization problem can be defined as a regular constraint satisfaction problem in which constraints are weighted and the goal is to find a solution maximizing the weight of satisfied constraints.