Simplicial pivoting algorithms for a tractable class of integer programs
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.
- An arbitrary starting homotopy-like simplicial algorithm for computing an integer point in a class of polytopes
- Computing an integer point of a class of convex sets.
- On the integer max-linear programming problem
- A combinatorial algorithm for Horn programs
- A generalized simplex method for integer problems given by verification oracles
- A note on the Edmonds-Fukuda pivoting rule for simplex algorithms
- Feasibility checking in Horn constraint systems through a reduction based approach
- Pivot and shift -- a mixed integer programming heuristic
- On Simplex Pivoting Rules and Complexity Theory
- Projection methods for finding the greatest element of the intersection of max-closed convex sets
- A combinatorial certifying algorithm for linear programming problems with gainfree Leontief substitution systems
- A combinatorial certifying algorithm for linear programming problems with gainfree Leontief substitution systems
- Trichotomy for integer linear systems based on their sign patterns
This page was built for publication: Simplicial pivoting algorithms for a tractable class of integer programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1598876)
