[SQN18] Non-convex Quadratic Integer Programming: a piecewise linearization

Conférences Internationales sans actes : ISMP - International Symposium on Mathematical Programming, Bordeaux, France,

Auteurs: E. Soutil , D. Quadri , D. Nizard

Mots clés: Quadratic Programming, Integer variables, Piecewise Linearization

Résumé: We address in this talk Non-convex Quadratic Integer Programming (NCQIP). More precisely we consider a problem in which the objective function is a quadratic non-convex one with pure general integer variables and linear constraints. The method proposed here generalizes a previous work addressing Convex QIP. We propose a general method to solve such problems that first transforms the problem into a mixed separable one, still non-convex. The quadratic part of the objective function becomes a weighted sum of squared variables, with no more products of two variables. This first transformation is done by diagonalizing the Hessian matrix of the initial objective function and requires new real variables and linear number of added constraints. Then we propose to use a parametric piecewise linearization of the equivalent problem. This linearization allows us to find the optimum of the initial problem when the number of line segments asymptotically grows. Experimentations are presented, in both convex and non-convex context, and extensions to quadratic constraints are discussed.

Collaboration: LIA

BibTeX

@conference {
	SQN18,
	title	=	"{Non-convex Quadratic Integer Programming: a piecewise linearization}",
	author	=	" E. Soutil and D. Quadri and D. Nizard ",
	year	=	2018,
}