Proximity in concave integer quadratic programming

DOI10.1007/S10107-021-01655-WMaRDI QIDQ2149572zbMATH OpenOpenAlexFDO

Authors Alberto Del Pia, Mingchen Ma

Publication date 29 June 2022

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

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

zbMATH Keywords

concave minimizationinteger quadratic programmingproximityquadratic programmingsensitivitysubdeterminants

Mathematics Subject Classification ID

Integer programming (90C10) Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Sensitivity, stability, parametric optimization (90C31)

Abstract: A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of $nDelta$ on the proximity of optimal solutions of an Integer Linear Programming problem and its standard linear relaxation. In this bound, $n$ is the number of variables and $Delta$ denotes the maximum of the absolute values of the subdeterminants of the constraint matrix. Hochbaum and Shanthikumar, and Werman and Magagnosc showed that the same upper bound is valid if a more general convex function is minimized, instead of a linear function. No proximity result of this type is known when the objective function is nonconvex. In fact, if we minimize a concave quadratic, no upper bound can be given as a function of $n$ and $Delta$. Our key observation is that, in this setting, proximity phenomena still occur, but only if we consider also approximate solutions instead of optimal solutions only. In our main result we provide upper bounds on the distance between approximate (resp., optimal) solutions to a Concave Integer Quadratic Programming problem and optimal (resp., approximate) solutions of its continuous relaxation. Our bounds are functions of $n,Delta$, and a parameter $epsilon$ that controls the quality of the approximation. Furthermore, we discuss how far from optimal are our proximity bounds.

Recommendations

• Some proximity and sensitivity results in quadratic integer programming
• On the relationship between the integer and continuous solutions of convex programs
• Subdeterminants and concave integer quadratic programming
• Improving proximity bounds using sparsity
• Tightness of sensitivity and proximity bounds for integer linear programs

Cites work

• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Convex separable optimization is not much harder than linear optimization
• Distances between optimal solutions of mixed-integer programs
• Distances to lattice points in knapsack polyhedra
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3790207 (Why is no real title available?)
• scientific article; zbMATH DE number 6850361 (Why is no real title available?)
• Integer Programming
• Integer quadratic programming in the plane
• Mixed-integer quadratic programming is in NP
• On approximation algorithms for concave mixed-integer quadratic programming
• On approximation algorithms for concave mixed-integer quadratic programming
• On Proximity for k-Regular Mixed-Integer Linear Optimization
• Sensitivity theorems in integer linear programming
• Some proximity and sensitivity results in quadratic integer programming
• Subdeterminants and concave integer quadratic programming
• The complexity of approximating a nonlinear program
• The relationship between integer and real solutions of constrained convex programming

Cited in

(15)

• Refined proximity and sensitivity results in linearly constrained convex separable integer programming
• Improving the Cook et al. proximity bound given integral valued constraints
• Improving proximity bounds using sparsity
• Distances between optimal solutions of mixed-integer programs
• scientific article; zbMATH DE number 6850361 (Why is no real title available?)
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Subdeterminants and concave integer quadratic programming
• On Proximity for k-Regular Mixed-Integer Linear Optimization
• Proximity search for 0--1 mixed-integer convex programming
• Proximity bounds for random integer programs
• Proximity bounds for random integer programs
• Sensitivity analysis for mixed binary quadratic programming
• Sensitivity analysis for mixed binary quadratic programming
• Some proximity and sensitivity results in quadratic integer programming
• Tightness of sensitivity and proximity bounds for integer linear programs

This page was built for publication: Proximity in concave integer quadratic programming

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