线性规划问题中的非凸可行域

数据挖掘 Python 优化
2022-02-20 04:52:33

问题:我正在研究一个线性规划问题,即最小化的线性目标函数:

cx,
其中c,xRN

受约束:

x0Axb 在哪里ARMxNbRM

我正在使用CyLPCOIN-OR 单纯形求解器来执行优化。

问题:我希望能够构建到问题中的一个功能是能够处理一些非典型约束:

认为xi是一个组成部分x. 我想应用以下约束:

xi=0或者lbxiub.

用几何术语,我想要xi[0][lb,ub]. 与原来的问题不同,所有xi有界在凸集内(即非分段区间)。

有没有针对上述非典型约束修改 LP 的好方法?

1个回答

抱歉,这不能用连续 LP 求解器来完成。正如您所观察到的,此构造引入了非凸性。但是,它可以由混合整数规划 (MIP) 求解器处理。

x=0或者xu是所谓的半连续变量许多高级 MIP 求解器直接支持这种变量类型。

如果 MIP 求解器不支持这一点,我们可以引入二进制变量δ{0,1}并使用约束:

δxuδ

模拟一个半连续变量。

COIN-OR 有一个功能强大的 MIP 求解器,称为 CBC(我相信它直接支持半连续变量)。