Una restricción binaria , en optimización matemática , es una restricción que involucra exactamente dos variables .
Por ejemplo, considere el problema de las n reinas , donde el objetivo es colocar n reinas de ajedrez en un tablero de ajedrez de n por n de modo que ninguna de las reinas pueda atacarse entre sí (horizontal, vertical o diagonalmente). Por lo tanto, el conjunto formal de restricciones es "La Reina 1 no puede atacar a la Reina 2", "La Reina 1 no puede atacar a la Reina 3", y así sucesivamente entre todos los pares de reinas. Cada restricción en este problema es binaria, ya que solo considera la ubicación de dos reinas individuales. [1]
Los programas lineales en los que todas las restricciones son binarias se pueden resolver en tiempo fuertemente polinomial , un resultado que no se sabe que sea cierto para programas lineales más generales. [2]