Vi diskuterar formuleringar av heltalsprogram med ett stort antal variabler och deras lösning genom kolonngenereringsmetoder, dvs implicit prissättning av icke-basiska variabler för att generera nya kolumner eller för att bevisa LP optimalitet på en nod av grenen och-bundet träd. Vi presenterar klasser av modeller för vilka detta tillvägagångssätt sönderdela problemet, ger hårdare LP avkopplingar, och eliminerar symmetri. W e sedan diskutera beräkningsfrågor och genomförande av kolumngenerering, gren-och bundna algoritmer, inklusive särskilda förgrenings regler och e cient w ays för att lösa LP avslappning. Vi diskuterar också förhållandet till Lagrangian dualitet.
För att lösa heltalsprogram med ett stort antal variabler, använder det nuvarande arbetet en Branch-and-Price (BnP) REF algoritm som kombinerar Branch-and-bound med Column Generation.
Branch-and-price: Column generation for solving huge integer programs
{'venue': 'Oper. Res', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}