An Approximation Algorithm for Indefinite Mixed Integer Quadratic Programming

Alberto Del Pia(delpiawisc.edu)

Abstract: In this paper we give an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the number of integer variables are fixed. The running time of the algorithm is expected unless P=NP. In order to design this algorithm we introduce the novel concepts of spherical form MIQP and of aligned vectors, and we provide a number of results of independent interest. In particular, we give a strongly polynomial algorithm to find a symmetric decomposition of a matrix, and show a related result on simultaneous diagonalization of matrices.

Keywords: mixed integer quadratic programming; approximation algorithm; polynomial time; symmetric decomposition; simultaneous diagonalization

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Global Optimization (Theory )

Citation: submitted manuscript

Download: [PDF]

Entry Submitted: 03/01/2021
Entry Accepted: 03/01/2021
Entry Last Modified: 03/01/2021

Modify/Update this entry