Istituto di Analisi dei Sistemi ed Informatica

Categoria: Publications

  • Strengthening the Sequential Convex MINLP Technique by Perspective Reformulations

    A new paper in collaboration among MINOA partners: CNRS-LIX, University of Pisa, and CNR-IASI.

    Abstract: The Sequential Convex MINLP (SC-MINLP) technique is a solution method for nonconvex Mixed-Integer NonLinear Problems where the nonconvexities are separable. It is based on solving a sequence of convex MINLPs which trade a better and better relaxation of the nonconvex part of the problem with the introduction of more and more piecewise-linear nonconvex terms, and therefore binary variables. The convex MINLPs are obtained by partitioning the domain of each separable nonconvex term in the intervals in which it is convex and those in which it is concave. In the former, the term is left in its original form, while in the latter it is piecewise-linearized. Since each interval corresponds to a semi-continuous variable, we propose to modify the convex terms using the Perspective Reformulation technique to strengthen the bounds. We show by means of experimental results on different classes of instances that doing so significantly decreases the solution time of the convex MINLPs, which is the most time consuming part of the approach, and has therefore the potential to improving the overall effectiveness of the SC-MINLP.

    Keywords: Global Optimization, NonConvex Separable Functions, Sequential Convex MINLP Technique, Perspective Reformulation.

    Cite as: C. D’Ambrosio, A. Frangioni, C. Gentile, Strengthening the Sequential Convex MINLP Technique by Perspective Reformulations, Optimization Letters, to appear, 2018.

  • Decompositions of Semidefinite Matrices and the Perspective Reformulation of Nonseparable Quadratic Programs

    A new paper among MINOA Partners: University of Pisa, CNR-IASI, and MAIOR.

    Abstract. We study the problem of decomposing the Hessian matrix of a Mixed-Integer Convex Quadratic Program into the sum of positive semidefinite 2×2 matrices. Solving this problem enables the use of Perspective Reformulation techniques for obtaining strong lower bounds for MICQPs with semi-continuous variables but a nonseparable objective function. An explicit formula is derived for constructing 2×2 decompositions when the underlying matrix is Weakly Scaled Diagonally Dominant, and necessary and sufficient conditions are given for the decomposition to be unique. For matrices lying outside this class, two exact SDP approaches and an efficient heuristic are developed for finding approximate decompositions. We present preliminary results on the bound strength of a 2×2 Perspective Reformulation for the Portfolio Optimization Problem, showing that for some classes of instances the use of 2×2 matrices can significantly improve the quality of the bound w.r.t. the best previously known approach, although at a possibly high computational cost.

    Keywords. Mixed-Integer Quadratic Programming, Matrix Decomposition, Scaled Diagonal Dominance, Semicontinuous variables, Portfolio Optimization.

    Cite as: A. Frangioni, C. Gentile, J. Hungerford, Decompositions of Semidefinite Matrices and the Perspective Reformulation of Nonseparable Quadratic Programs, Mathematics of Operations Research, to appear, 2018.

  • An algorithm for computing lower bounds for the Microaggregation problema

    CNR-IASI participated to an event organized by partner CNRS-LIX: the 16th Cologne-Twente Workshop in Paris

    Abstract. Public use of microdata files requires preprocessing to protect privacy. Microaggregation consists in aggregating data into clusters of size at least k such that the spread between individuals’ and centroid cluster values is minimized. This paper proposes an algorithm based on Column Generation to compute lower bounds on the spread.

    Keywords. Microaggregation, Statistical Disclosure Control, Column Generation.

    Cite as: Castro, Jordi, Claudio Gentile, and Enrique Spagnolo. “An algorithm for computing lower bounds for the Microaggregation problem.” 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. 2018.

    download