知识点：整数规划

知识点概述

整数规划（Integer Programming, IP）是一类要求部分或全部决策变量必须取整数值的优化问题。由于整数约束的非凸和离散性质，整数规划问题通常是NP难的，比连续优化问题要难解得多。

类型:
- 纯整数规划 (Pure IP): 所有变量都必须是整数。
- 混合整数规划 (Mixed IP, MIP): 部分变量是整数，部分是连续变量。
- 0-1整数规划 (Binary IP): 变量只能取0或1，常用于表示“是/否”决策。
挑战: 整数约束破坏了可行域的凸性，使得基于导数的连续优化方法失效。解空间是离散的，不能保证一个点的邻域内有更好的解。
求解方法:
- LP松弛 (LP Relaxation): 暂时忽略整数约束，求解对应的线性规划问题。这提供了一个目标值的下界（对于最小化问题），并可能得到一个整数解。
- 分支定界法 (Branch and Bound): 一种精确求解算法。它通过系统地将问题分解为子问题（分支），并利用LP松弛得到的界限来剪除不可能包含最优解的子空间（定界），从而在解空间中进行智能搜索。
- 割平面法 (Cutting Plane Method): 通过向LP松弛中添加新的约束（割平面），逐步切掉不包含任何整数可行解的区域，从而收紧可行域，使其更接近整数可行解的凸包。