Simplicial pivoting algorithms for a tractable class of integer programs (Q1598876)

A tractable class of integer feasibility problems is presented in this paper, the class of ``max closed'' integer programming problems. (A set \(S\subset\mathbb{R}^n\) is called max-closed, if \(x,y\in S\) implies \(\max(x,y)\in S\), where \(\max(x,y)\) is the coordinate-wise maximum of \(x\) and \(y\).) This class of problems has a logic counterpart known as the class of Horn formulas. In the first part, existing algorithms are modified in order to avoid the related recognition problem (i.e. is a given set definable by inequalities of the desired type?) Then it is shown that simplicial path following methods (which are flexible w.r.t. starting conditions) can be used to solve these max-closed IP problems.