Alternatives for testing total dual integrality | Mathematical Programming
Skip to main content
Springer Nature Link
Log in

Alternatives for testing total dual integrality

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper we provide characterizing properties of totally dual integral (TDI) systems, among others the following: a system of linear inequalities is TDI if and only if its coefficient vectors form a Hilbert basis, and there exists a test-set for the system’s dual integer programs where all test vectors have positive entries equal to 1. Reformulations of this provide relations between computational algebra and integer programming and they contain Applegate, Cook and McCormick’s sufficient condition for the TDI property and Sturmfels’ theorem relating toric initial ideals generated by square-free monomials to unimodular triangulations. We also study the theoretical and practical efficiency and limits of the characterizations of the TDI property presented here. In the particular case of set packing polyhedra our results correspond to endowing the weak perfect graph theorem with an additional, computationally interesting, geometric feature: the normal fan of the stable set polytope of a perfect graph can be refined into a regular triangulation consisting only of unimodular cones.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Applegate D., Cook W., McCormick T.: Integral feasibility and testing total dual integrality. Oper. Res. Lett. 10, 37–41 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  2. Barvinok A., Woods K.: Short rational generating functions for lattice point problems. J. Am. Math. Soc. 16, 957–979 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bruns W., Gubeladze J., Henk M., Martin A., Weismantel R.: A counterexample to an integer analogue of Carathéodory theorem. J. Reine Angew. Math. 510, 179–185 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Chandrasekaran R., Tamir A.: On the integrality of an extreme solution to pluperfect graph and balanced systems. Oper. Res. Lett. 3, 215–218 (1984)

    Article  MathSciNet  Google Scholar 

  5. Conti, P., Traverso, C.: Buchberger algorithm and integer programming. In: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Lecture Notes in Computer Science, vol. 539. Springer, Berlin (1991)

  6. Cook W., Fonlupt J., Schrijver A.: An integer analogue of Carathéodory’s theorem. J. Comb. Theory (B) 40, 63–70 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cook W., Lovász L., Schrijver A.: A polynomial-time test for total dual integrality in fixed dimension. Math. Progr. Study 22, 64–69 (1984)

    Article  MATH  Google Scholar 

  8. Cornuéjols, G.: Combinatorial optimization: packing and covering. In: CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74. SIAM (2001)

  9. Chudnovsky M., Cornuéjols G., Liu X., Seymour P., Vušković K.: Recognizing Berge graphs. Combinatorica 25(2), 143–186 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chudnovsky M., Robertson N., Seymour P., Thomas R.: The strong perfect graph theorem. Ann. Math. 164(1), 51–229 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  11. Cox D., Little J., O’Shea D.: Ideals, Varieties and Algorithms, 2nd edn. Springer-Verlag, New York (1996)

    MATH  Google Scholar 

  12. De Loera, J.A., Lee, J., Malkin, P., Margulies, S.: Hilbert’s Nullstellensatz and an algorithm for proving combinatorial infeasibility. In: ISSAC 21: Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation, pp. 197–206. ACM, New York (2008)

  13. Ding G., Feng L., Zang W.: The complexity of recognizing linear systems with certain integrality properties. Math. Progr. 114, 321–334 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Dueck P., Hoşten S., Sturmfels B.: Normal Toric ideals of low codimension. J. Pure Appl. Algebra 213, 1636–1641 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  15. Eisenbrand F., Shmonin G.: Parametric integer programming in fixed dimension. Math. Oper. Res. 33, 839–850 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  16. Eisenbrand, F., Sebő, A., Shmonin, G.: Testing Hilbert bases. August 2007 (manuscript)

  17. Fukuda, K.: cdd+ reference manual. Institute for Operations Research, Swiss Federal Institute of Technology, Zurich, Switzerland. http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html (1995)

  18. Fulkerson D.R.: Anti-blocking polyhedra. J. Comb. Theory (B) 12, 50–71 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  19. Gawrilow, E., Joswig, M.: Polymake: a framework for analyzing convex polytopes. In: Polytopes—Combinatorics and Computation (Oberwolfach, 1997), pp. 43–73. DMV Sem. 29. Birkhäuser, Basel (2000)

  20. Gerards A., Sebő A.: Total dual integrality implies local strong unimodularity. Math. Progr. 38, 69–73 (1987)

    Article  MATH  Google Scholar 

  21. Golumbic M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)

    MATH  Google Scholar 

  22. Graver J.: On the foundations of linear and integer programming I. Math. Progr. 8, 207–226 (1975)

    Article  MathSciNet  Google Scholar 

  23. Grayson, D., Stillman, M.: Macaulay 2, a software system for research in algebraic geometry. http://www.math.uiuc.edu/Macaulay2/

  24. Grötschel M., Lovász L., Schrijver A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1984)

    Google Scholar 

  25. Hemmecke, R., Onn, S., Weismantel, R.: A polynomial oracle-time algorithm for convex integer minimization. Math. Progr. A. doi:10.1007/s10107-009-0276-7

  26. Hoşten S., Sturmfels B.: Computing the integer programming gap. Combinatorica 27, 367–382 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  27. Lee C.W.: Regular triangulations of convex polytopes. DIMACS Series Discrete Math. Theor. Comput. Sci. 4, 443–456 (1991)

    Google Scholar 

  28. Lenstra H.W. Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  29. Lovász L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253–267 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  30. Lueker, G.S.: Structured Breadth First Search and Chordal Graphs. Princeton Univ. Tech. Rep. TR-158

  31. Mayr E.W., Meyer A.: The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. Math. 46, 305–329 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  32. Ohsugi H., Hibi T.: Convex polytopes all of whose reverse lexicographic initial ideals are squarefree. Proc. A.M.S. 129, 2541–2546 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  33. O’Shea, E.: Toric algebra and the weak perfect graph theorem. Ph.D. dissertation, University of Washington (2006)

  34. O’Shea, E., Sebő, A.: Characterizations of total dual integrality. In: Fischetti, M., Williamson, D. (eds.) Integer Programming and Combinatorial Optimization, vol. 12. LNCS (2007)

  35. Padberg M.: Perfect zero-one matrices. Math. Progr. 6, 180–196 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  36. Pap, J.: Recognizing conic TDI systems is hard. EGRES Technical Report TR-2008-15. Mathematical Programming. doi:10.1007/s10107-009-0294-5

  37. Rambau, J.: TOPCOM (Triangulations of Point Configurations and Oriented Matroids). http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM/

  38. Rose, D.J., Tarjan, R.E.: Algorithmic aspects of vertex elimination. In: Proc. 7. Ann. ACM Symp., Theory Comput, pp. 245–254 (1975)

  39. Saito, M., Sturmfels, B., Takayama, N.: Gröbner deformations of hypergeometric differential equations. In: Algorithms and Computation in Mathematics, vol. 6. Springer-Verlag, Berlin (2000)

  40. Schrijver A.: Theory of Linear and Integer Programming. Wiley, New York (1986)

    MATH  Google Scholar 

  41. Sebő A.: Hilbert bases, Caratheodory’s theorem and combinatorial optimization. In: Kannan, R., Pulleyblank, W. (eds) Integer Programming and Combinatorial Optimization, Mathematical Programming Society, University of Waterloo Press, Waterloo (1990)

    Google Scholar 

  42. Sebő, A.: Problem A.6, “TDI Matrices”. In: Open Problems Workshop on “The Perfect Graph Conjecture”. http://www.aimath.org/pastworkshops/perfectgraph.html (2002)

  43. Sturmfels B.: Gröbner bases of toric varieties. Tohoku Math. J. 43, 249–261 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  44. Sturmfels B., Weismantel R., Ziegler G.M.: Gröbner bases of lattices, corner polyhedra, and integer programming. Beiträge Algebra Geom. 36, 281–298 (1995)

    MathSciNet  MATH  Google Scholar 

  45. Sturmfels, B.: Gröbner bases and convex polytopes. University Lecture Series, vol. 8. American Mathematical Society, Providence (1996)

  46. Sturmfels, B.: Algebraic recipes for integer programming. AMS Shortcourse: Trends in Optimization. In: Hoşten, S., Lee, J., Thomas, R.R. (eds.) Proceedings of Symposia in Applied Mathematics, vol. 61. American Mathematical Society, Providence (2004)

  47. Sturmfels B., Thomas R.R.: Variations of cost functions in integer programming. Math. Progr. 77, 357–387 (1997)

    MathSciNet  MATH  Google Scholar 

  48. Thomas R.R.: Algebraic methods in integer programming. In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization, Kluwer Academic Publishers, Dordrecht (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, University College, Cork, Ireland

    Edwin O’Shea

  2. Laboratoire G-SCOP, CNRS, 46, Avenue Félix Viallet, 38031, Grenoble Cedex 1, France

    András Sebö

Authors
  1. Edwin O’Shea
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. András Sebö
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Edwin O’Shea.

Additional information

E. O’Shea was supported by a Fulbright grant and by NSF grants DMS-9983797 and DMS-0401047. A. Sebö was supported by the “Marie Curie Training Network” ADONET of the European Community.

Rights and permissions

Reprints and permissions

About this article

Cite this article

O’Shea, E., Sebö, A. Alternatives for testing total dual integrality. Math. Program. 132, 57–78 (2012). https://doi.org/10.1007/s10107-010-0383-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-010-0383-5

Keywords

Mathematics Subject Classification (2000)

Search

Navigation