时间戳

首页 > 解决方案 > 整数问题是无界的，但它的线性松弛不在 CVXPY 中

python - 整数问题是无界的，但它的线性松弛不在 CVXPY 中

问题描述

亲爱的，

我正在尝试 CVXPY 并生成了一个简单的整数程序。为了比较，我还生成了它的线性松弛。但是，在求解时，我得到了松弛问题的值（1.429）。然而，对于整数问题，我得到 -inf。我错过了什么？

谢谢！

遵循代码：

import cvxpy as cp
import numpy as np

def make_problem(m, n, integer, name = 'Not named', solve = True, seed = 0):
    np.random.seed(seed)

    # Generating problem parameters
    A = np.random.randn(m, n)
    b = np.dot(A, np.ones(n))/2
    c = -np.random.randn(n)

    # Generation problem variables
    x = cp.Variable(n, integer = integer)

    # Generating problem objective
    obj = cp.Minimize(c.T @ x)

    # Generating problem constraints
    cstr = [
        A @ x <= b,
        x >= 0,
        x <= 1,
    ]

    # Generating problem
    prob = cp.Problem(obj, cstr)

    if solve:
        prob.solve()
        print(f'PROBLEM {name}: STATUS: {prob.status} | VALUE: {prob.value}')    
        return x

    else:
        return prob

m = 300
n = 100

x_rlx = make_problem(m, n, integer = False, name = 'Relaxed')
x = make_problem(m, n, integer = True, name = 'Integer')

输出：

问题放松：状态：最佳 | 值：1.4295841445033348

问题整数：状态：无界 | 值：-inf

标签： pythonmathematical-optimizationcvxpyinteger-programming

解决方案

通常，松弛是可行的，而原始问题则不是。想象一个简单的问题：

min(x)

x == 0.5

对于 x = 0.5 的最佳 0.5，这是可行的，而当我们强制 x 为二进制时，这是不可行的。

您观察到的可能性很高（如评论中所示：我们并不完全了解您的问题）。

重要提示：查询求解器状态！

为了：

np.random.seed(0)
m = 20
n = 10
...
print(prob_rlx.status)
print(prob_rlx.value)
...
print(prob.status)
print(prob.value)

我观察到：

optimal
0.0822089776045708

infeasible
inf

这意味着：求解器证明了非松弛问题的不可行性，并在这种情况下使用了无穷大的默认值！

这是模棱两可的 -> 放松也可能是无限的；因此：读取状态！

参见示例幻灯片：第 13/14 页

推荐阅读