The quadratic Graver cone, quadratic integer minimization, and extensions

DOI10.1007/S10107-012-0605-0zbMATH Open1280.90088arXiv1006.0773OpenAlexW1770886307MaRDI QIDQ1925790FDOQ1925790

Robert Weismantel, Jon Lee, Shmuel Onn, Lyubov Romanchuk

Publication date: 19 December 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We consider the nonlinear integer programming problem of minimizing a quadratic function over the integer points in variable dimension satisfying a system of linear inequalities. We show that when the Graver basis of the matrix defining the system is given, and the quadratic function lies in a suitable {em dual Graver cone}, the problem can be solved in polynomial time. We discuss the relation between this cone and the cone of positive semidefinite matrices, and show that none contains the other. So we can minimize in polynomial time some non-convex and some (including all separable) convex quadrics. We conclude by extending our results to efficient integer minimization of multivariate polynomial functions of arbitrary degree lying in suitable cones.

Full work available at URL: https://arxiv.org/abs/1006.0773

Recommendations

• Integer quadratic programming in the plane
• Minimizing cubic and homogeneous polynomials over integers in the plane
• Subdeterminants and concave integer quadratic programming
• The efficient minimization of quadratic polynomials depending on integer variables, with quadratic monomials \(b^2_{i,j}(x_i - x_j)^2\)
• A polynomial case of convex integer quadratic programming problems with box integer constraints

zbMATH Keywords

integer programmingGraver basisquadartic optimization

Mathematics Subject Classification ID

Integer programming (90C10)

Cites Work

• Title not available (Why is that?)
• Higher Lawrence configurations.
• On the foundations of linear and integer linear programming I
• A polynomial oracle-time algorithm for convex integer minimization
• The Graver complexity of integer programming
• \(N\)-fold integer programming
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Nonlinear discrete optimization. An algorithmic theory
• Algebraic statistics and contingency table problems: log-linear models, likelihood estimatio, and disclosure limitation
• Convex integer maximization via Graver bases
• \(N\)-fold integer programming and nonlinear multi-transshipment
• An Extension of Gauss' Transformation for Improving the Condition of Systems of Linear Equations

Cited In (6)

• Optimality criterion for a class of nonlinear integer programs.
• An approximation algorithm for indefinite mixed integer quadratic programming
• Solving MIPs via scaling-based augmentation
• The efficient minimization of quadratic polynomials depending on integer variables, with quadratic monomials \(b^2_{i,j}(x_i - x_j)^2\)
• Integer programming in parameterized complexity: five miniatures
• Convex integer maximization via Graver bases

This page was built for publication: The quadratic Graver cone, quadratic integer minimization, and extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1925790)