Binary constraint
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A binary constraint, in mathematical optimization, is a constraint that involves exactly two variables. For example, consider the n-queens problem, where the goal is to place n chess queens on an n-by-n chessboard such that none of the queens can attack each other (horizontally, vertically, or diagonally). The formal set of constraints are therefore "Queen 1 can't attack Queen 2", "Queen 1 can't attack Queen 3", and so on between all pairs of queens. Each constraint in this problem is binary, in that it only considers the placement of two individual queens. Linear programs in which all constraints are binary can be solved in strongly polynomial time, a result that is not known to be true for more general linear programs.
A binary constraint, in mathematical optimization, is a constraint that involves exactly two variables. For example, consider the n-queens problem, where the goal is to place n chess queens on an n-by-n chessboard such that none of the queens can attack each other (horizontally, vertically, or diagonally). The formal set of constraints are therefore "Queen 1 can't attack Queen 2", "Queen 1 can't attack Queen 3", and so on between all pairs of queens. Each constraint in this problem is binary, in that it only considers the placement of two individual queens. Linear programs in which all constraints are binary can be solved in strongly polynomial time, a result that is not known to be true for more general linear programs. ==References==
Text derived from https://en.wikipedia.org/w/index.php?oldid=1179535362 under CC BY-SA 4.0; modifications have been made.