CVXPY求解整数混合问题时莫名返回无界状态求助

我正在求解整数版本的混合问题，目标是最大化线性目标函数，并设置了多个线性约束，对应的代码如下：

# we'll need both cvxpy and numpy
import cvxpy as cp
import numpy as np

N = 5  # the number of products
M = 5 # the number of materials

# material availability of each item
material_bounds = np.random.uniform(50, 80, size=M)
# value of each product
v = cp.Constant(np.random.uniform(1, 15, size=N))
# material needed for each item
materials_needed = np.random.uniform(5, 10, size=(M,N))
# define the x vector this time it is integer
x = cp.Variable(N, integer=True)
# define the constraint
constraints = []

for i in range(M):
    constraints.append(
        cp.Constant(materials_needed[i]) @ x <= cp.Constant(material_bounds[i]))

# define the target function
target = v @ x

# define the problem
mix_problem = cp.Problem(cp.Maximize(target), constraints)
print(mix_problem)
# solve the problem.
mix_problem.solve(verbose=True)


print("Solution:", x.value)
print("Total value:", v @ x.value)
print("Total weight:", materials_needed @ x.value)

打印问题时形式符合预期，但求解器输出显示问题无界：

===============================================================================
                                     CVXPY                                     
                                     v1.2.2                                    
===============================================================================
(CVXPY) Nov 22 08:51:07 AM: Your problem has 5 variables, 5 constraints, and 0 parameters.
(CVXPY) Nov 22 08:51:07 AM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Nov 22 08:51:07 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Nov 22 08:51:07 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
-------------------------------------------------------------------------------
                                  Compilation                                  
-------------------------------------------------------------------------------
(CVXPY) Nov 22 08:51:07 AM: Compiling problem (target solver=GLPK_MI).
(CVXPY) Nov 22 08:51:07 AM: Reduction chain: FlipObjective -> Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> GLPK_MI
(CVXPY) Nov 22 08:51:07 AM: Applying reduction FlipObjective
(CVXPY) Nov 22 08:51:07 AM: Applying reduction Dcp2Cone
(CVXPY) Nov 22 08:51:07 AM: Applying reduction CvxAttr2Constr
(CVXPY) Nov 22 08:51:07 AM: Applying reduction ConeMatrixStuffing
(CVXPY) Nov 22 08:51:07 AM: Applying reduction GLPK_MI
(CVXPY) Nov 22 08:51:07 AM: Finished problem compilation (took 1.960e-02 seconds).
-------------------------------------------------------------------------------
                                Numerical solver                               
-------------------------------------------------------------------------------
(CVXPY) Nov 22 08:51:07 AM: Invoking solver GLPK_MI  to obtain a solution.
*     0: obj =   0.000000000e+00 inf =   0.000e+00 (5)
*     1: obj =  -7.818018602e+01 inf =   0.000e+00 (4)
-------------------------------------------------------------------------------
                                    Summary                                    
-------------------------------------------------------------------------------
(CVXPY) Nov 22 08:51:07 AM: Problem status: unbounded
(CVXPY) Nov 22 08:51:07 AM: Optimal value: inf
(CVXPY) Nov 22 08:51:07 AM: Compilation took 1.960e-02 seconds
(CVXPY) Nov 22 08:51:07 AM: Solver (including time spent in interface) took 3.681e-04 seconds
Solution: None

无法理解为何在已有<=约束的情况下问题仍会无界，寻求帮助。

使用环境：

• CVXPY版本：1.2.2
• Python版本：3.8

已尝试修改约束构建方式（从materials_needed @ x <= material_bounds改为逐个添加约束），查阅CVXPY文档未得到有效帮助。

原因分析 #

问题的核心是未给变量x添加非负约束。

x代表产品的生产数量，逻辑上必须是非负整数（不能生产负数数量的产品），但当前代码仅定义了x = cp.Variable(N, integer=True)，未限制x的取值下限。

由于materials_needed和v的取值均为正数，求解器可以构造出无限增大目标函数的可行解：比如通过“销毁”某些低价值产品（取负的x值）来释放材料，再用这些材料生产更多高价值产品，循环此操作可让目标函数无限增长，同时始终满足材料约束条件。这种情况下，问题的可行域无界，导致求解器返回“unbounded”状态。

解决方法 #

添加x的非负约束，有两种方式：

1. 定义变量时直接指定非负属性：

x = cp.Variable(N, integer=True, nonneg=True)

2. 手动添加非负约束到约束列表：

constraints.append(x >= 0)

添加非负约束后，x的所有分量被限制为非负整数，可行域变为有界集合，求解器即可找到最优解。

内容的提问来源于stack exchange，提问作者Jose Jorge Rodriguez Salgado