與二元變量

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 

xi的值的一個溶液線性方程是0或1（xi是二元變量）

在那裏的任何算法用於解決這種方程式和類似問題

Answer 1

你確定你的問題不是binary integer programming？

如果你只是想用這麼小的變量來求解這個方程式，那麼蠻力搜索就可能正常工作......構造2^8 8*1向量，並驗證每個向量是否滿足你的方程你肯定可以用矩陣形式寫出你的方程）。

如果你只是想一個解決方案....你甚至可以自己動手完成它：10101011

但一般的解決方案是不容易的。檢查這post。要解決多項式時間內的二進制整數線性方程，有一個paper，您可能需要一些時間挖掘。

編輯：從@Ben福格特更新

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 

二元變量的總和始終是變量< = NUM​​：

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