The quadratic Graver cone, quadratic integer minimization, and extensions
From MaRDI portal
Publication:1925790
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.
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
Cites work
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- A polynomial oracle-time algorithm for convex integer minimization
- Algebraic statistics and contingency table problems: log-linear models, likelihood estimatio, and disclosure limitation
- All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
- An Extension of Gauss' Transformation for Improving the Condition of Systems of Linear Equations
- Convex integer maximization via Graver bases
- Higher Lawrence configurations.
- Nonlinear discrete optimization. An algorithmic theory
- On the foundations of linear and integer linear programming I
- The Graver complexity of integer programming
- \(N\)-fold integer programming
- \(N\)-fold integer programming and nonlinear multi-transshipment
Cited in
(8)- Subdeterminants and concave integer quadratic programming
- Optimality criterion for a class of nonlinear integer programs.
- 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\)
- Minimizing cubic and homogeneous polynomials over integers in the plane
- Convex integer maximization via Graver bases
- An approximation algorithm for indefinite mixed integer quadratic programming
- Integer programming in parameterized complexity: five miniatures
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)
