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.{{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=https://books.google.com/books?id=jBYAleHTldsC&pg=PA282}}.

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.{{citation

| last = Megiddo | first = Nimrod | authorlink = Nimrod Megiddo

| doi = 10.1137/0212022

| issue = 2

| journal = SIAM Journal on Computing

| mr = 697165

| pages = 347–353

| title = Towards a genuinely polynomial algorithm for linear programming

| volume = 12

| year = 1983| citeseerx = 10.1.1.76.5}}.