Binární omezení - Binary constraint
A binární omezení, v matematická optimalizace, je omezení, které zahrnuje přesně dvě proměnné.
Zvažte například n-královny problém, kde je cílem umístit n šachové královny na n-podle-n šachovnice tak, aby žádná z královen nemohla na sebe útočit (vodorovně, svisle nebo úhlopříčně). Formální sada omezení je tedy „Královna 1 nemůže zaútočit na Královnu 2“, „Královna 1 nemůže zaútočit na Královnu 3“ atd. Mezi všemi páry královen. Každé omezení v tomto problému je binární, protože bere v úvahu pouze umístění dvou jednotlivých královen.[1]
Lineární programy ve kterém jsou všechna omezení binární lze vyřešit v silně polynomiální čas Výsledek, o kterém není známo, že je pravdivý pro obecnější lineární programy.[2]
Reference
- ^ Marriott, Kim; Stuckey, Peter J. (1998), Programování s omezeními: Úvod, MIT Stiskněte, str. 282, ISBN 9780262133418.
- ^ Megiddo, Nimrod (1983), „Směrem ke skutečně polynomickému algoritmu pro lineární programování“, SIAM Journal on Computing, 12 (2): 347–353, CiteSeerX 10.1.1.76.5, doi:10.1137/0212022, PAN 0697165.
 | Tento aplikovaná matematika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |