Branch-and-Cut Technique Chapter 9 割平面技术 Integer Programming 整数规划 首先放弃变量的整数要求,求线性规划最优解 如果最优解恰是一整数解,则最优解就是整数规划的最优解 如果最优解不是整数解,则要求构造一个新的约束,对线性 规划问题的可行域进行切割,切除已得到的规划的最优解, 但保留原可行域中所有的整数解,求解新的线性规划问题, 如果最优解仍不是整数解,再增加附加的约束将其切除,但 仍保持最初可行域中所有的整数解,如此一直进行,直至得 到一个整数的最优解为止 RuC Information School, Ye Xiang 2007Chapter 9 Integer Programming 整数规划 RUC Information School ,Ye Xiang ,2007 Branch-and-Cut Technique 割平面技术 首先放弃变量的整数要求，求线性规划最优解 如果最优解恰是一整数解，则最优解就是整数规划的最优解 如果最优解不是整数解，则要求构造一个新的约束，对线性 规划问题的可行域进行切割，切除已得到的规划的最优解， 但保留原可行域中所有的整数解，求解新的线性规划问题， 如果最优解仍不是整数解，再增加附加的约束将其切除，但 仍保持最初可行域中所有的整数解，如此一直进行，直至得 到一个整数的最优解为止