Simplical Pivoting Algorithms for a Tractable Class of Integer Programs.

摘要

The authors present a tractable class of integer feasibility problems. This class of max-closed IP problems was studied in somewhat restricted form by Glover, Pnueli, Hochbaum and Chandrasekaran and has a logic counterpart known as the class of Horn formulas. First, the authors modify the existing algorithms in order to avoid the related recognition problem. Further, the authors argue that in order to solve max-closed IP problems simplicial path following methods are flexible with respect to starting conditions, which make them more suitable than the top-down truncation algorithms that have been suggested. A new vector labeling based simplicial algorithm is developed which also runs outside this class and reveals useful information for search tree design.