^-^
Benders' Algorithm

解决混合整数规划问题 , 可以人为地规定变量优化的顺序, 将其写成类似于 bilevel optimization 的形式: 上面是先把 作为参数求解一个线性规划问题, 再求解剩下的子问题.

如何证明这两种写法的等价性?

感觉好像不太对, 更像是一种启发式规则.

好吧不算很简单，需要好好看一下怎么搞。

假设 是有界的, 那么由 Farkas 引理可知 是 feasible 的 , 其中 是凸集 的极方向(extreme ray).

若求解 的线性规划是 feasible 的, 那么 其中 是 的极点, 这可以改写为 将离散问题转化为了一个连续的线性规划问题, 那么就可以将 写成 这个问题约束的个数是指数级别的, 解决该问题最好的方法是 branch-and-cut.

2023-08-06

以上
©
Too Young Too Naive 本站由Hexo驱动｜使用Hexo-theme-A4主题