Certificates and relaxations for integer programming and the semi-group membership problem

2009/05/11 by Jean Lasserre, Lasserre, Jean, S. Zeron +1
Computer Science · Mathematics · #90 #C10 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DM #math.OC #msc:90 #msc:C10

paper · pdf · doi:10.48550/arxiv.0905.1608

21 pages

arxiv created 2009/05/11 · arxiv updated 2009/12/01

Abstract

We consider integer programming and the semi-group membership problem. We provide the following theorem of the alternative: the system Ax=b has no nonnegative integral solution x if and only if p(b) <0 for some given polynomial p whose vector of coefficients lies in a convex cone that we characterize. We also provide a hierarchy of linear programming relaxations, where the continuous case Ax=b with x real and nonnegative, describes the first relaxation in the hierarchy.

Related

• An Algebraic Perspective of Group Relaxations
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Asymptotic behavior of Integer Programming and the stability of the Castelnuovo-Mumford regularity
• Instance-specific linear relaxations of semidefinite optimization problems
• Parametric Integer Programming in Fixed Dimension