Combinatorial Redundancy Detection

Authors Komei Fukuda, Bernd Gärtner, May Szedlák



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.315.pdf
  • Filesize: 465 kB
  • 14 pages

Document Identifiers

Author Details

Komei Fukuda
Bernd Gärtner
May Szedlák

Cite AsGet BibTex

Komei Fukuda, Bernd Gärtner, and May Szedlák. Combinatorial Redundancy Detection. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 315-328, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.315

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 variables, where the variables are constrained to be nonnegative. A variable x_r is called redundant, if after removing its nonnegativity constraint the LP still has the same feasible region. The time needed to solve such an LP is denoted by LP(n,d). It is easy to see that solving 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 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 one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for 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 of order 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 of order 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’s method

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler. Oriented Matroids. Cambridge University Press, 1993. Google Scholar
  2. T. M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. Discrete & Computational Geometry, 16(4):369-387, 1996. Google Scholar
  3. V. Chvatal. Linear Programming. W. H. Freeman, 1983. Google Scholar
  4. K. L. Clarkson. More output-sensitive geometric algorithms. In Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci., pages 695-702, 1994. Google Scholar
  5. G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, NJ, 1963. Google Scholar
  6. J. H. Dulá, R. V. Helgason, and N. Venugopal. An algorithm for identifying the frame of a pointed finite conical hull. INFORMS J. Comput., 10(3):323-330, 1998. Google Scholar
  7. K. Fukuda. Introduction to optimization. http://www.ifor.math.ethz.ch/teaching/Courses/Fall_2011/intro_fall_11, 2011.
  8. K. Fukuda. Walking on the arrangement, not on the feasible region. Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?, IPAM, UCLA, 2011. presentation slides available as http://helper.ipam.ucla.edu/publications/sm2011/sm2011_9630.pdf. .
  9. K. Fukuda. Lecture: Polyhedral computation. http://www-oldurls.inf.ethz.ch/personal/fukudak/lect/pclect/notes2015/, 2015.
  10. K. Fukuda, B. Gärtner, and M. Szedlák. Combinatorial redundancy removal. Preprint: arXiv:1412.1241, 2014. Google Scholar
  11. K. Fukuda and T. Terlaky. Criss-cross methods: A fresh view on pivot algorithms. Mathematical Programming, 79:369-395, 1997. Google Scholar
  12. V. Klee and G. J. Minty. How good is the simplex algorithm? In O. Shisha, editor, Inequalities III, pages 159-175. Academic Press, 1972. Google Scholar
  13. J. Matoušek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16:498-516, 1996. Google Scholar
  14. Th. Ottmann, S. Schuierer, and S. Soundaralakshmi. Enumerating extreme points in higher dimensions. In E.W. Mayer and C. Puech, editors, STACS 95: 12th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 900, pages 562-570. Springer-Verlag, 1995. Google Scholar
  15. C. Roos. An exponential example for Terlaky’s pivoting rule for the criss-cross simplex method. Mathematical Programming, 46:79-84, 1990. Google Scholar
  16. T. Terlaky. A finite criss-cross method for the oriented matroids. Journal of Combinatorial Theory Series B, 42:319-327, 1987. Google Scholar
  17. Z. Wang. A finite conformal-elimination free algorithm over oriented matroid programming. Chinese Annals of Math., 8B:120-125, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail