Кіріспе
Бранч және кесіп алу – бүтін сандық сызықтық бағдарламаларды (ILP) шешуге арналған комбинаторлық оңтайландыру әдісі, яғни кейбір немесе барлық белгісіздері бүтін сандық мәндермен шектелген сызықтық бағдарламалау (LP) мәселелері. Бранч және кесіп алу алгоритмі тармақтау және шектеу әдісін іске қосуды және сызықтық бағдарламалаудың жақындауын күшейту үшін кесу жазықтықтарын пайдалануды қамтиды. Егер кесулер тек бастапқы LP жақындауын күшейту үшін қолданылса, онда алгоритм кесу және тармақтау деп аталады.
Салалық стратегиялар
Тармақталу және кесу алгоритмінің маңызды қадамы – тармақталу кезеңі. Бұл кезеңде қолдануға болатын әртүрлі тармақталу эвристикалары бар. Төменде сипатталған тармақталу стратегияларының барлығы айнымалы бойынша тармақталу деп аталатын нәрсені қамтиды. Айынымалы бойынша тармақталу – қазіргі LP релаксациясының ең жақсы шешімінде бөлшектік мәні бар , айнымалын таңдау және содан кейін және шектеулерін қосу. Ең мүмкін емес тармақталу стратегиясы 0,5-ке ең жақын бөлшектік бөлігі бар айнымалыны таңдайды. Псевдо-құнмен тармақталу. Бұл стратегияның негізгі идеясы – әрбір айнымалы үшін осы айнымалы тармақталу айнымалы ретінде бұрын таңдалған кездегі мақсатты функциядағы өзгерісті қадағалау. Содан кейін стратегия бұрынғы өзгерістерге негізделген мақсатты функцияда ең көп өзгеріс болатыны болжанған айнымалыны таңдайды. Псевдо-құнмен тармақталу іздеудің бастапқы кезеңінде ақпараттық болмайды, өйткені аз ғана айнымалылар тармақталған. Күшті тармақталу. Күшті тармақталу нақты тармақталу алдында кандидат айнымалылардың қайсысы мақсатты функцияны ең жақсы жақсартатынын тексеруді қамтиды. Толық күшті тармақталу барлық кандидат айнымалыларды тексереді және есептеу жағынан қымбат болуы мүмкін. Есептеу шығындарын кандидат айнымалылардың кіші жиынтығын қарастыру және тиісті LP релаксацияларын толық шешпеу арқылы азайтуға болады. Бұл тармақталу стратегияларының көптеген нұсқалары бар, мысалы, псевдо-құнмен тармақталу салыстырмалы түрде ақпаратсыз болған кезде ертерек күшті тармақталуды қолдану, содан кейін псевдо-құнмен тармақталуға ауысу, псевдо-құн ақпараттық болу үшін жеткілікті тармақталу тарихы жиналған кезде.
Most infeasible branching This branching strategy chooses the variable with the fractional part closest to 0.5. Pseudo cost branching The basic idea of this strategy is to keep track for each variable the change in the objective function when this variable was previously chosen as the variable to branch on. The strategy then chooses the variable that is predicted to have the most change on the objective function based on past changes when it was chosen as the branching variable. Note that pseudo cost branching is initially uninformative in the search since few variables have been branched on. Strong branching Strong branching involves testing which of the candidate variable gives the best improvement to the objective function before actually branching on them. Full strong branching tests all candidate variables and can be computationally expensive. The computational cost can be reduced by only considering a subset of the candidate variables and not solving each of the corresponding LP relaxations to completion. There are also a large number of variations of these branching strategies, such as using strong branching early on when pseudo cost branching is relatively uninformative and then switching to pseudo cost branching later when there is enough branching history for pseudo cost to be informative.