割平面法是1958年由美國學(xué)者高莫利(R.E.GoMory)提出的求解全整數(shù)規(guī)劃的一種比較簡單的方法。其基本思想和分枝定界法大致相同，即先不考慮變量的取整約束，用單純形法求解相應(yīng)的線性規(guī)劃。如果所得的最優(yōu)解為整數(shù)解，那么它也是原整數(shù)規(guī)劃問題的最優(yōu)解3如果最優(yōu)解不是整數(shù)解，那么分枝定界法是任取一個(gè)取分?jǐn)?shù)值的變量X_k = b_k將原整數(shù)規(guī)劃分成兩枝，其實(shí)質(zhì)是用兩個(gè)垂直于坐標(biāo)軸的平行平面X_k = [b_k]和X_k = [b_k] + 1將原可行域R分成兩個(gè)可行域R₁和R₂，并將兩個(gè)平行平面之間的不合有整數(shù)解的那一部分可行域去掉，以縮小可行域。而割平面法是用一張平面(不一定垂直于某個(gè)坐標(biāo)軸)，將含有最優(yōu)解的點(diǎn)但不含任何整數(shù)可行解的那一部分可行域切割掉，這只要在原整數(shù)規(guī)劃基礎(chǔ)上增加適當(dāng)?shù)木€性不等式約束(我們稱之為切割不等式；當(dāng)切割不等式取等號時(shí)，叫做割平面)。然后繼續(xù)解這個(gè)新的整數(shù)規(guī)劃，再在這個(gè)新的整數(shù)規(guī)劃的基礎(chǔ)上增加適當(dāng)?shù)木€性不等式約束，直至求得最優(yōu)整數(shù)解為止。也就是說，通過構(gòu)造一系列平面來切割掉不含有任何整數(shù)可行解的部分，最終獲得一個(gè)具有整數(shù)坐標(biāo)的頂點(diǎn)的可行域，而該頂點(diǎn)恰好是原整數(shù)規(guī)劃的最優(yōu)解。

割平面法的關(guān)鍵在于，如何構(gòu)造切割不等式，使增加該約束后能達(dá)到真正的切割而且沒有切割掉任何整數(shù)可行解。

(1)先不考慮變量的取整約束，用單純形法求解相應(yīng)的線性規(guī)劃問題，如果該問題沒有可行解或最優(yōu)解已是整數(shù)則停止，否則轉(zhuǎn)下步。

在求解相應(yīng)的線性規(guī)劃時(shí)，首先要將原問題的數(shù)學(xué)模型進(jìn)行標(biāo)準(zhǔn)化。這里的“標(biāo)準(zhǔn)化”有兩個(gè)含義：第一是將所有的不等式約束全部轉(zhuǎn)化成等式約束，這是因?yàn)橐捎脝渭冃伪磉M(jìn)行計(jì)算的緣故。第二是將整數(shù)規(guī)劃中所有非整數(shù)系數(shù)全部轉(zhuǎn)換成整數(shù)，這是出于構(gòu)造“切割不等式”的需要。

(2)求一個(gè)“切割不等式”及添加到整數(shù)規(guī)劃的約束條件中去，即對上述線性規(guī)劃問題的可行域進(jìn)行“切割”，然后返回步驟1。

用割平面法求解整數(shù)規(guī)劃的基本思路是：先不考慮整數(shù)約束條件，求松弛問題的最優(yōu)解，如果獲得整數(shù)最優(yōu)解，即為所求，運(yùn)算停止．如果所得到最優(yōu)解不滿足整數(shù)約束條件，則在此非整數(shù)解的基礎(chǔ)上增加新的約束條件重新求解．這個(gè)新增加的約束條件的作用就是去切割相應(yīng)松弛問題的可行域，即割去松弛問題的部分非整數(shù)解(包括原已得到的非整數(shù)最優(yōu)解)．而把所有的整數(shù)解都保留下來，故稱新增加的約束條件為割平面．當(dāng)經(jīng)過多次切割后，就會(huì)使被切割后保留下來的可行域上有一個(gè)坐標(biāo)均為整數(shù)的頂點(diǎn)，它恰好就是所求問題的整數(shù)最優(yōu)解．即切割后所對應(yīng)的松弛問題，與原整數(shù)規(guī)劃問題具有相同的最優(yōu)解。