設(shè)有最大化的整數(shù)規(guī)劃問題A,與它對應(yīng)的線性規(guī)劃為問題B,從解問題B開始,若其最優(yōu)解不符合A 的整數(shù)條件,那么B的最優(yōu)目標(biāo)函數(shù)必是A 的最優(yōu)目標(biāo)函數(shù) 的上界,記作Z1;而A 的任意可行解的目標(biāo)函數(shù)值將是 一個下界Z2。分支定界法就是將B的可行域分成子區(qū)域(稱為分支),逐步減小Z1和增大Z2,最終求到 .