Binary constraint: Difference between revisions

Revision as of 06:41, 15 November 2014

Latest revision as of 19:27, 10 October 2023

(3 intermediate revisions by 3 users not shown)

Line 1:

A '''binary constraint''', in [[mathematical optimization]], is a constraint that involves exactly two variables[[Variable (mathematics)|variable]]s.

For example, consider the [[n-queens problem|''n''-queens problem]], where the goal is to place ''n'' [[Queen (chess)|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.<ref>{{citation|title=Programming with Constraints: An Introduction|first1=Kim|last1=Marriott|first2=Peter J.|last2=Stuckey|publisher=MIT Press|year=1998|isbn=9780262133418|page=282|url=httphttps://books.google.com/books?id=jBYAleHTldsC&pg=PA282}}.</ref>

[[Linear program]]s 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.<ref>{{citation

Line 12:

| title = Towards a genuinely polynomial algorithm for linear programming

| volume = 12

| year = 1983| citeseerx = 10.1.1.76.5}}.</ref>

==References==

Line 19:

[[Category:Mathematical optimization]]

[[Category:Constraint programming]]

{{Mathapplied-stub}}