The quadratic Graver cone, quadratic integer minimization, and extensions
The paper addresses quadratic integer programming problems. The authors first observe that it is NP-hard to determine the optimal value of a quadratic integer programme \[ \min \{x^TVx + w^Tx + a: x \in \mathbb{Z}^n, ~Ax =b,~ l \leq x \leq u\} \] even if the Graver basis of \(A\) is given and even if the objective function is convex and \(V= vv^T\). They use this as a motivtaion to study special cases of quadratic functions for which this problem can be solved in polynomial time. Their main results show that this is the case for matrices \(V\) lying in the dual quadratic Graver cone (defined in the paper). As a special case, the result also holds for separable quadratic programming with the objective \(\sum_{i=1}^n (v_ix_i^2 + w_ix_i +a_i)\), where \(v\) belongs to the dual diagonal Graver cone. The results are extended later to show that for more general polynomials. It is shown that for every fixed \(d\) there is an algorithm that, given the Graver basis, solves \[ \min\{f(x): x \in \mathbb{Z}^n, ~Ax=b,~ x \geq 0\} \] in polynomial time for every degree \(d\) integer homogeneous polynomial \(f\) in a cone of certain tensors defined by \(A\).
- 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
- \(N\)-fold integer programming
- \(N\)-fold integer programming and nonlinear multi-transshipment
- 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.
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- Nonlinear discrete optimization. An algorithmic theory
- On the foundations of linear and integer linear programming I
- The Graver complexity of integer programming
- Convex integer maximization via Graver bases
- Solving MIPs via scaling-based augmentation
- Integer programming in parameterized complexity: five miniatures
- Minimizing cubic and homogeneous polynomials over integers in the plane
- The efficient minimization of quadratic polynomials depending on integer variables, with quadratic monomials \(b^2_{i,j}(x_i - x_j)^2\)
- Subdeterminants and concave integer quadratic programming
- An approximation algorithm for indefinite mixed integer quadratic programming
- Augmentation search for integer programming over a polyhedron
- Optimality criterion for a class of nonlinear integer programs.
- Parallel Graver basis extraction for nonlinear integer optimization
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)
