『运筹OR帷幄』温故
本文于XXXX年XX月XX日重新整理并发布于知乎及【运筹OR帷幄】微信公众号，以飨读者。
编者按
打开这篇文章的朋友们大多已是运筹学的中级玩家，或至少学过线性规划和整数规划。本文将系统介绍整数规划及其相关算法，包括Branch-and-Cut以及Cutting Plane Method在整数规划中的重要作用。
文章提纲
- 整数规划问题回顾
- 精确算法——分支定界法
- 割平面法——UserCut与LazyCut详解
- 行生成方法(Row Generation)介绍
- 整数规划在计算机视觉的应用实例——Multicuts在图像分割中的运用
1、整数规划问题回顾
整数规划，或称离散优化（Discrete Optimization），是数学规划问题中自变量存在整数的一类问题。这类问题，目标方程和约束方程都是线性的，自变量既有连续变量又有整数变量。
与线性规划连续的可行域不同，整数规划的可行域是离散的。在整数规划的所有可行解中，我们寻找一个能使目标函数达到最优的解，这个解即为整数规划的解。
2、精确算法——分支定界法
分支定界法是求解整数规划的一种精确算法。该方法先将问题分解成多个子问题，然后对子问题逐个求解，最后将子问题的解有机结合，希望能找到原问题的全局最优解或近似解。
每一个子问题是多项式时间可解的线性规划问题，但最坏情况下需要求解2^n个线性规划问题（这里假设整数变量是0，1变量，n是整数变量的个数）。寻找更“聪明”的分解方法成为数学家们的研究方向。
3、割平面法——UserCut与LazyCut详解
割平面法是整数规划中的一种重要方法。该方法通过不断添加线性不等式（割平面），缩小搜索空间，以求得整数解。
UserCut主要是针对实数解的割平面，而LazyCut则是针对整数解的割平面。两者在应用范围和具体实现上有所不同，但都是为了减少搜索空间，提高求解效率。
4、行生成方法(Row Generation)
行生成方法从更宏观的角度看待割平面法，可以把“行”（即线性不等式）看作是一种生成的对象。通过逐步增加重要约束条件，来形成极值（最优解）所需要的约束条件。
行生成方法在求解实际问题时，往往只需要很少的约束条件就能找到原问题的最优解。
5、整数规划在计算机视觉的应用实例——Multicuts在图像分割中的运用
Multicuts是整数规划在计算机视觉领域的一个应用实例。它被用于图像分割问题，通过数学建模成一个基于图G(V，E)的能量函数最小值优化问题。
在该问题中，割平面法的使用是为了添加on-the-fly的多割约束（multicut constraints），这些约束的个数是指数级的。只能采用割平面方法逐步添加约束条件。
本文旨在系统介绍整数规划及其相关算法，希望对读者在该领域的研究有所帮助。后续还将有更多关于运筹学的知识分享，敬请期待。
参考资料：
[1] 运筹学相关课程讲义及教材
[2] Benders Decomposition with GAMS等学术论文
[3] The Traveling Salesman - Computational Solutions for TSP等运筹学经典书籍及论文