Combinatorial redundancy detection

Komei Fukuda (), Bernd Gärtner () and May Szedlák ()
Additional contact information
Komei Fukuda: ETH Zürich
Bernd Gärtner: ETH Zürich
May Szedlák: ETH Zürich

Annals of Operations Research, 2018, vol. 265, issue 1, No 4, 47-65

Abstract: Abstract The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by n equality constraints in $$n+d$$ n + d variables, where the variables are constrained to be nonnegative. A variable $$x_r$$ x r is called redundant, if after removing $$x_r \ge 0$$ x r ≥ 0 the LP still has the same feasible region. The time needed to solve such an LP is denoted by $$\textit{LP}(n,d)$$ LP ( n , d ) . It is easy to see that solving $$n+d$$ n + d LPs of the above size is sufficient to detect all redundancies. The currently fastest practical method is the one by Clarkson: it solves $$n+d$$ n + d linear programs, but each of them has at most s variables, where s is the number of nonredundant constraints. In the first part we show that knowing all of the finitely many dictionaries of the LP is sufficient for the purpose of redundancy detection. A dictionary is a matrix that can be thought of as an enriched encoding of a vertex in the LP. Moreover—and this is the combinatorial aspect—it is enough to know only the signs of the entries, the actual values do not matter. Concretely we show that for any variable $$x_r$$ x r one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for $$x_r$$ x r . In the second part we show that considering only the sign patterns of the dictionary, there is an output sensitive algorithm of running time $$\mathcal {O}(d \cdot (n+d) \cdot s^{d-1} \cdot \textit{LP}(s,d) + d \cdot s^{d} \cdot \textit{LP}(n,d))$$ O ( d · ( n + d ) · s d - 1 · LP ( s , d ) + d · s d · LP ( n , d ) ) to detect all redundancies. In the case where all constraints are in general position, the running time is $$\mathcal {O}(s \cdot \textit{LP}(n,d) + (n+d) \cdot \textit{LP}(s,d))$$ O ( s · LP ( n , d ) + ( n + d ) · LP ( s , d ) ) , which is essentially the running time of the Clarkson method. Our algorithm extends naturally to a more general setting of arrangements of oriented topological hyperplane arrangements.

Keywords: System of linear inequalities; Redundancy removal; Linear programming; Output sensitive algorithm; Clarkson method (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-016-2385-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:265:y:2018:i:1:d:10.1007_s10479-016-2385-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-016-2385-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().