如何用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]))

结果是：

^{pr2}$

我读过cvxopt文档，但是我没有发现任何关于二进制线性问题的东西。在

Answer 1

cvxopt不能求解二进制线性规划。考虑到问题的大小，您可以尝试编写自己的小分支定界算法：

1）求解线性规划

2）选择一个分数解变量x_f并创建两个新问题“leaf”

2a）问题1）附加约束x_f<；=0

2b）问题1）附加约束x\u f>；=1

重复。。。在

（或使用Excel解算器）