Binary constraint

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.[1]

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.[2]

References

Marriott, Kim; Stuckey, Peter J. (1998), Programming with Constraints: An Introduction, MIT Press, p. 282, ISBN 9780262133418.
Megiddo, Nimrod (1983), "Towards a genuinely polynomial algorithm for linear programming", SIAM Journal on Computing, 12 (2): 347–353, CiteSeerX 10.1.1.76.5, doi:10.1137/0212022, MR 0697165.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Marriott, Kim; Stuckey, Peter J. (1998), Programming with Constraints: An Introduction, MIT Press, p. 282, ISBN 9780262133418.

[2] Megiddo, Nimrod (1983), "Towards a genuinely polynomial algorithm for linear programming", SIAM Journal on Computing, 12 (2): 347–353, CiteSeerX 10.1.1.76.5, doi:10.1137/0212022, MR 0697165.