How to find the convex hull of all integer points in a polyhedron?

1. Baldoni, V., Berline, N., De Loera, J.A., Dutra, B., Köppe, M., Moreinis, S., Pinto, G., Vergne, M. and Wu, J.: A User’s Guide for LattE integrale v1. 7.2 (2013) Software package LattE is available at http://www.math.ucdavis.edu/~latte

2. Barvinok, A.I.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19(4), 769–779 (1994)

   Article  MathSciNet  Google Scholar 

3. Bastrakov, S.I., Churkin, A.V., Zolotykh, N.Y.: Accelerating Fourier-Motzkin elimination using bit pattern trees. Optim. Methods Softw. (2020). https://doi.org/10.1080/10556788.2020.1712600

4. Bastrakov, S.I., Zolotykh, N.Y.: Fast method for verifying Chernikov rules in Fourier–Motzkin elimination. Comput. Math. Math. Phys. 55(1), 160–167 (2015)

   Article  MathSciNet  Google Scholar 

5. Ben-Amram, A.M., Genaim, S.: On the linear ranking problem for integer linear-constraint loops. ACM SIGPLAN Not. 48(1), 51–62 (2013)

   Article  Google Scholar 

6. Ben-Amram, A.M., Genaim, S.: Ranking functions for linear-constraint loops. J. ACM (JACM) 61(4), 1–55 (2014)

   Article  MathSciNet  Google Scholar 

7. Bruns, W., Ichim, B.: Normaliz: Algorithms for affine monoids and rational cones. J. Algebra 324(5), 1098–1113 (2010)

   Article  MathSciNet  Google Scholar 

8. Bruns, W., Ichim, B., Römer, T., Sieg, R. and Söger, C.: Normaliz. Algorithms for rational cones and affine monoids. Available at https://www.normaliz.uni-osnabrueck.de

9. Chernikov, S.: Linear inequalities. Nauka, Moscow (1968). (in Russian)

10. Chernikova, N.: Algorithm for finding a general formula for the non-negative solutions of system of linear inequalities. U.S.S.R. Comput. Math. Math. Phys. 5(2), 228–233 (1965)

    Article  MathSciNet  Google Scholar 

11. Cook, W., Hartmann, M., Kannan, R., McDiarmid, C.: On integer points in polyhedra. Combinatorica 12(1), 27–37 (1992)

    Article  MathSciNet  Google Scholar 

12. De Loera, J.A., Hemmecke, R., Tauzer, J., Yoshida, R.: Effective lattice point counting in rational convex polytopes. J. Symb. Comput. 38(4), 1273–1302 (2004)

    Article  MathSciNet  Google Scholar 

13. Hartmann, M.: Cutting planes and the complexity of the integer hull. Technical Report No. 819. Cornell University, School of Operations Research and Industrial Engineering (1988)

14. Hu, T.C.: Integer Programming and Network Flows. Department of Computer Science, Wisconsin University, Madison (1969)

    MATH  Google Scholar 

15. Köppe, M., Verdoolaege, S, Woods, K. M.: An implementation of the Barvinok–Woods integer projection algorithm. In: The 2008 International Conference on Information Theory and Statistical Learning, pp. 53–59 (2008)

16. Motzkin, T., Raiffa, H., Thompson, G., Thrall, R.: The double description method. In: Kuhn, H., Tucker, A.W. (eds.) Contributions to Theory of Games, vol. 2. Princeton University Press, Princeton, RI (1953)

    Google Scholar 

17. Schaefer, A.J.: Inverse integer programming. Optim. Lett. 3(4), 483–489 (2009)

    Article  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

19. Semenov, S., Zolotykh N. Yu.: A dynamic algorithm for constructing the dual representation of a polyhedral cone. In: International Conference on Mathematical Optimization Theory and Operations Research. Lecture Notes in Computer Science 11548. Springer, Cham. pp. 59–69 (2019)

20. Shevchenko, V.N.: Qualitative Topics in Integer Linear Programming. American Mathematical Society, USA (1996)

    Book  Google Scholar 

21. Zolotykh, N.: New modification of the double description method for constructing the skeleton of a polyhedral cone. Comput. Math. Math. Phys. 52(1), 146–156 (2012)

    Article  MathSciNet  Google Scholar 

Download references