An Improved Implicit Enumeration Approach for Integer Programming

摘要: This paper synthesizes the Balasian implicit enumeration approach to integer linear programming with typified by Land and Doig Roy, Bertier, Nghiem. The synthesis results from use of an imbedded program compute surrogate constraints that are as "strong" possible in a sense slightly different originally used Glover. A simple algorithm fitted optional machinery was implemented tested extensively on IBM 7044. Use greatly reduced solution times virtually every case, seemed render superior five other algorithms for which comparable published experience available. crucial issue sensitivity time number variables given special attention. Sequences were run set-covering, optimal-routing, knapsack problems multiple varying sizes up 90 variables. suggest prescribed way may mitigate solution-time dependence exponential low-order polynomial increase. appeared be approximately first two problem classes, 90-variable typically being solved about 15 seconds; cubic third class, 80-variable less than 2 minutes. In 35-variable range all three factor 100.