如何⽤整数规划求解NP完全问题
⼀、NP完全问题
NP完全问题是⼀类具有⾮常⾼难度的组合最优化问题，所有NP完全问题都是NP难问题。虽然P问题是⽐较容易的问题，NP问题却不⼀定是困难问题，必须看见NP完全或者NP难这样的字才能说这个问题求解起来很困难。
经常听砖家说，NP完全/NP难问题不能⽤整数规划求解。实际情况怎样？实事证明砖家的话只能信⼀半：）。这⾥咱就看看⽤整数规划求解⼀个NP完全问题⾏也不⾏。
这⾥有⼀个货真价实的整数规划问题——划分问题（The partition problem）。问题是：给定⼀个⼤⼩不等的整数集合，问是否可以把这些整数划分成两个集合，任何⼀个整数或者在集合S1中或者在S2中，但不能同时在两个集合中；对任意给的⼀个整数集合，请设计算法，解决是否存在⼀个划分，使得S1种整数之和恰好等于S2集合的整数之和。大卫科波菲尔论文
⼆、建⽴整数规划模型
对每个整数定义⼀个0-1变量xi, xi=1 表⽰第i个整数位于集合S1中， xi=0表⽰第i个整数位于S2中。⽤s1表⽰第⼀集合的整数之和，⽤s2表⽰第⼆个集合⾥的整数之和。即：
设d是s1和s2之间差的绝对值。于是：
我们只要极⼩化d就可以了，即：
完整模型：
三、上⾯的模型的⽂本表达
上⾯的模型不只是⽤来摆摆看的，还可以真的被求解哈。我们需要把模型写成⽂本格式（Leapms建模语⾔格式），让计算机理解。⽬标函数就写成
min d
非常e购加上其余约束部分（注意西格玛符合的写法）
subject to
s1=sum{i=1,...,n}x[i]S[i]
s2=sum{i=1,...,n}((1-x[i])S[i])
d>=s1-s2
d>=s2-s1
加上符号说明（符号必须说明，不然计算机不知道哪些是常数，哪些是变量）
where
热流道技术n is an integer
S is a set
s1,s2,d are variables of number
x[i] is a variable of binary|i=1,...,n
加上数据（注意整数个数是从集合S上⾃⼰数出来的）
data_relation
n=_$(S)
夏一松data
S={11,47,159,137,85,47,142,35,119,61,88,175,13,96,-11,176,126,15,98,46,163}
四、求解
把如下完整模型贴到记事本上，保存为 partition.leap⽂件。（注意如果是不⾏啊）。min d
subject to
s1=sum{i=1,...,n}x[i]S[i]
s2=sum{i=1,...,n}((1-x[i])S[i])
d>=s1-s2
d>=s2-s1
whereqibozi
n is an integer
S is a set
s1,s2,d are variables of number
x[i] is a variable of binary|i=1,...,n
data_relation
马赛国际公寓n=_$(S)
data
S={11,47,159,137,85,47,142,35,119,61,88,175,13,96,-11,176,126,15,98,46,163}
启动leapms，依次打⼊load, partion, mip命令，即可得到解
五、结果分析
上⾯的结果d=0, s1=s2=914。显然对给出的数据来说，有划分。
整数规划成功求解了⼀个NP完全问题。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议