如何使用cvxopt解决二进制线性规划？ Python

Question

我知道怎么用cvxopt来解决线性规划问题，但我不知道当变量只能是0或1的时候（也就是二进制问题）该怎么做。这里是我尝试写的代码：

#/usr/bin/env python3
# -*- coding: utf-8 -*-


from cvxopt.modeling import variable, op, solvers
import matplotlib.pyplot as plt
import numpy as np

x1 = variable()
x2 = variable()
x3 = variable()
x4 = variable()

c1 = (x1+x2+x3+x4 <= 2)
c2 = (-x1-x2+x3 <= 0)
c3 = (55*x1+40*x2+76*x3+68*x4 <= 200)
c4 = (x3+x4 <= 1)
#here is the problem.
c5 = (x1 == 0 or x1 == 1)
c6 = (x2 == 0 or x2 == 1)
c7 = (x3 == 0 or x3 == 1)
c8 = (x4 == 0 or x4 == 1)

lp1 = op(70*x1-60*x2-90*x3-80*x4, [c1, c2, c3, c4, c5, c6, c7, c8])
lp1.solve()
print('\nEstado: {}'.format(lp1.status))
print('Valor óptimo: {}'.format(-round(lp1.objective.value()[0])))
print('Óptimo x1: {}'.format(round(x1.value[0])))
print('Óptimo x2: {}'.format(round(x2.value[0])))
print('Óptimo x3: {}'.format(round(x3.value[0])))
print('Óptimo x4: {}'.format(round(x4.value[0])))
print('Mult óptimo primera restricción: {}'.format(c1.multiplier.value[0]))
print('Mult óptimo segunda restricción: {}'.format(c2.multiplier.value[0]))
print('Mult óptimo tercera restricción: {}'.format(c3.multiplier.value[0]))
print('Mult óptimo cuarta restricción: {}\n'.format(c4.multiplier.value[0]))

结果是：

     pcost       dcost       gap    pres   dres   k/t
 0: -3.0102e-09 -2.0300e+02  2e+02  1e-02  8e-01  1e+00
 1: -3.5175e-11 -2.4529e+00  2e+00  1e-04  1e-02  1e-02
 2:  1.9739e-12 -2.4513e-02  2e-02  1e-06  1e-04  1e-04
 3:  5.0716e-13 -2.4512e-04  2e-04  1e-08  1e-06  1e-06
 4: -7.9906e-13 -2.4512e-06  2e-06  1e-10  1e-08  1e-08
Terminated (singular KKT matrix).

Estado: unknown
Valor óptimo: 0
Óptimo x1: 0
Óptimo x2: 0
Óptimo x3: 0
Óptimo x4: 0
Mult óptimo primera restricción: 1.1431670510974203e-07
Mult óptimo segunda restricción: 0.9855547161745738
Mult óptimo tercera restricción: 9.855074750509187e-09
Mult óptimo cuarta restricción: 2.5159510552878724e-07

我看过cvxopt的文档，但没有找到关于二进制线性问题的任何信息。

Answer 1

cvxopt 这个工具不能解决二进制线性规划问题。根据你问题的大小，你可以尝试自己写一个简单的分支限界算法：

1) 先解决线性规划问题

2) 选择一个分数解变量 x_f，然后创建两个新的问题“分支”：

2a) 第一个问题加上额外的限制条件 x_f <= 0

2b) 第二个问题加上额外的限制条件 x_f >= 1

然后继续这个过程...

(或者你也可以使用 Excel 的求解器)