линейных уравнений с бинарными переменными

Question

У меня есть эти уравнения, и я хочу, чтобы найти одно решение для них

0<=x1+x2+x3+x4+x5+x6<=3     
0<=x7+x8<=2 
2<=x1+x2+x3+x4<=4 
2<=x3+x4+x5<=3 
2<=x6+x7+x8<=3 

значений хх является 0 или 1 (XI в двоичной переменной)

является ли алгоритм для решения такого рода уравнений и аналогичных

Answer 1

Уверены ли вы, что ваша проблема не в binary integer programming?

Если вы просто хотите решить эту проблему с помощью такого небольшого количества переменных, поиск грубой силы может просто работать. Создайте 2^8 8*1 векторы и проверьте, удовлетворяет ли каждый вектор вашему уравнению (вы можете написать свое уравнение в матричной форме).

Если вы просто хотите одно решение .... Вы даже можете сделать это вручную: 10101011

Но общее решение не так просто. Проверьте это post. Чтобы решить двоичное целочисленное линейное уравнение в полиномиальное время, существует один paper, который может занять некоторое время.

EDIT: обновление от @Ben Voigt

branch-and-bound, как правило, эффективны для эффективного решения (большой) целочисленных (включая двоичный файл.) И смешанных целочисленных задач. Конечно, эта проблема слишком мала, чтобы стоить накладных расходов - исчерпывающий поиск вполне адекватен.

Answer 2

Независимо от алгоритма, который вы можете использовать, я бы сделал некоторую предварительную обработку, чтобы уменьшить сложность. Сумма двоичных переменных всегда> = 0:

x1+x2+x3+x4+x5+x6<=3     
x7+x8<=2 
2<=x1+x2+x3+x4<=4 
2<=x3+x4+x5<=3 
2<=x6+x7+x8<=3 

Сумма двоичных переменных всегда < = Количество переменных:

x1+x2+x3+x4+x5+x6<=3     
2<=x1+x2+x3+x4 
2<=x3+x4+x5 
2<=x6+x7+x8