On an optimal constraint aggregation method for integer programming and on an analytic expression of the number of integer points in a polytope

2016/05/27 by Pierre‐Louis Poirion, Vu Khac Ky, Poirion, Pierre-Louis +3
Mathematics · Computer Science · #Commutative Algebra and Its Applications #Advanced Graph Theory Research #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1605.08742

Abstract

In this paper we give a new aggregation framework for linear Diophantine equations. In particular, we prove that an aggregated system of minimum size can be built in polynomial time. We also derive an analytic formula that gives the number of solutions of the system when it is possible to aggregate the system into one equation.

Related

• Small systems of Diophantine equations which have only very large integer solutions
• Revisiting some classical linearizations of the quadratic binary optimization problem
• Embedding Formulations and Complexity for Unions of Polyhedra
• Integer Algorithms to Solver Diophantine Linear Equations and Systems
• Boole's probability bounding problem, linear programming aggregations, and nonnegative quadratic pseudo-Boolean functions