Istituto di Analisi dei Sistemi ed Informatica

Categoria: Uncategorized

  • 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.

  • Optimization and Decision Science 2018 in Taormina: two contributions by IASI-CNR and MINOA partners

    Perspective Cuts for the ACOPF with generators by Esteban Salgado (CNRS-LIX), Claudio Gentile (IASI-CNR) and Leo Liberti (CNRS-LIX).

    Perspective Reformulation-based Strengthening for the sequential convex MINLP technique by Claudio D’Ambrosio (CNRS-LIX), Antonio Frangioni (University of Pisa), and Claudio Gentile (IASI-CNR).

  • Distance Geometry in data science: A tutorial in two parts

    Speaker: Leo Liberti CNRS & LIX, Ecole Polytechnique, France

    Abstract:
    Many problems in data science are addressed by mapping entities of various kind to vectors in a Euclidean space of some dimension. Most of these methods (e.g. Multidimensional Scaling, Principal Component Analysis, K-means clustering, random projections) are based on the proximity of pairs of vectors. In order for the results of these methods to make sense when mapped back, the proximity of entities in the original problem must be well approximated in the Euclidean space setting. If proximity were known for each pair of original entities, this mapping would be a good example of isometric embedding. Usually, however, this is not the case, as data are partial, wrong and noisy. I shall survey some of the methods above from the point of view of Distance Geometry. Time permitting, I will also showcase some code examples.
    Location: Aula “Piano Terra”, via dei Taurini 19, Roma
    First lecture:  September 3, 2018  time 11.30
    Second lecture:  September 4, 2018 time 11.30
    Slides available upon request to Claudio Gentile

  • 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