寻求适用于大规模凸整数非线性规划的高效开源求解器

一、针对纯整数凸非线性规划的开源求解器 #

以下开源求解器可适配纯整数凸非线性规划场景，避免MINLP求解器中不必要的实变量处理开销：

• Bonmin：C++实现的开源MINLP求解器，支持纯整数变量模式，针对凸问题优化了分支定界策略，底层依托IPOPT处理凸NLP子问题，可通过Pyomo等建模工具调用，能有效减少连续变量相关的冗余计算。
• Couenne：专注全局优化的开源MINLP求解器，可识别纯整数凸问题并利用凸性进行剪枝，大幅压缩搜索空间，适合大规模问题的求解。
• SCIP：开源的整数规划与全局优化框架，支持纯整数凸非线性规划，可通过配置禁用连续变量相关模块，分支定界算法针对凸问题做了特殊优化，提供Python接口（pyscipopt）便于快速调用。
• GLPK（结合非线性扩展）：经典开源线性整数规划求解器，搭配AMPL或Pyomo的非线性扩展模块后，可处理凸纯整数问题，其线性子问题求解效率极高，适合大规模场景下的快速迭代。

二、针对你的特定问题的专属优化方案 #

你的问题属于可分离凸整数规划，结构特殊，无需依赖通用求解器，可通过解析方法快速求解，计算复杂度仅为O(N)，远优于通用求解器的指数级增长：

1. 先求解连续松弛问题：
   连续松弛下的最优解满足 ( x_i^* = \frac{\beta_i^{{2/3}}{\lambda}{2/3}} )，其中拉格朗日乘子 ( \lambda ) 由约束 ( \sum_{i=1}^N x_i^* = K ) 确定，推导可得 ( \lambda = \left( \frac{\sum_{i=1}^N \beta_i^{2/3}}{K} \right)^{3/2} )。
2. 将连续解调整为整数解：
   先对 ( x_i^* ) 取整（floor），再将剩余的 ( K - \sum \text{floor}(x_i^*) ) 个“小数部分最大”的变量各加1，确保满足约束且尽可能接近最优解。

实现代码 #

import numpy as np

N = 50000
K = N * 2
beta = np.absolute(np.random.randn(N) * 1000)

# 计算连续松弛最优解对应的拉格朗日乘子
beta_pow = beta ** (2/3)
sum_beta_pow = beta_pow.sum()
lambda_opt = (sum_beta_pow / K) ** (3/2)
x_cont = beta_pow / (lambda_opt ** (2/3))

# 调整为满足约束的正整数解
x_int = np.floor(x_cont).astype(int)
remaining = K - x_int.sum()
# 选取小数部分最大的变量补全剩余值
idx = np.argsort(x_cont - x_int)[-remaining:]
x_int[idx] += 1

# 验证结果
assert x_int.sum() == K
assert (x_int >= 1).all()

内容的提问来源于stack exchange，提问作者LucG