Бинарное ограничение
Бинарное ограничение в математической оптимизации — это ограничение, которое включает ровно две переменные .
Например, рассмотрим задачу n -ферзей , цель которой состоит в том, чтобы разместить n шахматных ферзей на nxn доске размером шахматной так, чтобы ни один из ферзей не мог атаковать друг друга (по горизонтали, вертикали или диагонали). Таким образом, формальный набор ограничений таков: «Ферзь 1 не может атаковать ферзя 2», «Ферзь 1 не может атаковать ферзя 3» и так далее между всеми парами ферзей. Каждое ограничение в этой задаче является двоичным, поскольку оно учитывает размещение только двух отдельных ферзей. [1]
Линейные программы , в которых все ограничения являются двоичными, могут быть решены за строго полиномиальное время , но этот результат, как известно, неверен для более общих линейных программ. [2]
Ссылки
[ редактировать ]- ^ Марриотт, Ким; Стаки, Питер Дж. (1998), Программирование с ограничениями: введение , MIT Press, стр. 282, ISBN 9780262133418 .
- ^ Мегиддо, Нимрод (1983), «На пути к подлинно полиномиальному алгоритму для линейного программирования», SIAM Journal on Computing , 12 (2): 347–353, CiteSeerX 10.1.1.76.5 , doi : 10.1137/0212022 , MR 0697165 .
 | Эта прикладной математике, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее . |