A primal (all-integer) integer programming algorithm

Abstract

The algorithm is mos t close ly re la ted to three e xi s ting procedures: th e s impl ex m e th od o f G. B. Dantzi g for lin ea r p rogramming probl e m s, th e Gu mor y all -int ege r int ege r progra mmin g a lgu rithm , and th e direc t a lgo rithm for int ege r prugramming uf Be n-Is rael a nd C h a rn es.Th e a lgorithm is s imilar to th e Gomory a ll •int ege r a lgorithm in th ese res pec ts: (i) it is an a ll -int egc r a lgorithm ; (ii ) it uses t h e sa m e c ut genera ti on proccdure; (i ii) it uses the c ut row as th e pivo t row; and (iv ) th e pivot coeffic ie nt always h as unit va lu e. Whil e th e dual me tho d provid es th e ve hi c le for mo ving from tableau to tabl ea u in th e Go mory a ll -int ege r a lgori thm .th e s impl ex method has t h e ana lag()u s rol e in th e primal a lgori thm .Thu s in a ge ne ral se nse thi s a lgori thm is a primal ana log t() th e (dual) Comory a ll -int ege r a lgo rithm.The direc t al go rith m of Be n-I s rae l a nd C harnes also has th e a bove s imilariti es to th e Gomory a ll -int eger a l ~o rithm , but has one s ig nifi ca nt differe nce : an it era ti on or cyc le of th e direc t algo rithm mu st fr e que ntl y inc lude th e so luti on of a n "a uxiliary pro bl e m " (whi c h is it se lf an int ege r prugramm in g probl e m ) or a determina ti o n t h a t no so luti on to th e "a uxiliary pro bl e m " ex is ts.In co ntra s l. th e cyc les of th e prim a l algori th m in c lud e o nly th e adjoin in g of a ComUl'y c ut and th e execu tiun of th e c h ange of ba s is pro ced ure of th e s impl ex m e thod .Th e proce dure uf th e a lgorithm and th e proof of finit e ness are fo unde d on a class ifi ca tion of cyc les of the algori thm and on two theo re m s.Two t ypes of prorf' dural restric ti on s are imposed as a bas is for prov in g fin it e ness: (a) se lec ti o n o f th e in co min g variab le is s ubj ec te d to regula ti on (beyo nd that req uired by t he s impl ex met hod).a nd t he rul es applied a re a function uf th e t ype of cyc le be in g execu ted; (b) se lec ti on of th e row Ll sed as th e so urce of th e dat a fo r the Go m o r y c ut is r es tri c te d (in addi ti on to th e res tri c ti on impli ed by (ii), (iii) .a nd (iv) above) in cer tai n cyc les o f th e a lgo rithm.Part 1.A Primal Algorithm: Arttecedents