在数学优化中,切割平面法是通过线性不等式对可行集或目标函数进行迭代性优化(即切割)的优化方法的涵盖性术语。该过程通常用来发现混合整数线性规划(MILP)问题的整数解,也可以用来解决常规的、未必可微的凸优化问题。利用切割平面法求解 MILP 由 Ralph E. Gomory 引入。MILP 的切割平面法通过将整数问题线性松弛为非整数线性问题,并对其进行求解,来求解 MILP 问题。线性规划理论说明,在温和的假定下(如果线性规划存在最优解,并且可行域不包含一条线),总存在一个极值点或顶点是最优的。 检验所获的最优解是否为整数解。如否,则必然存在一线性不等式将最优点和真可行集的凸包分离。找到这样的不等式是分离问题,而这样的不等式就是切割。 切割可以被加入到被松弛的线性规划中,使得当前的非整数解对松弛不再可行。该过程不断重复,直到找到最优整数解。