Emiliano Traversi

Mining for diamonds – matrix generation algorithms for binary quadratically constrained quadratic problems

  • Enrico Bettiol
  • Immanuel M. Bomze
  • Lucas Létocart
  • Francesco Rinaldi
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper, we consider binary quadratically constrained quadratic problems and propose a new approach to generate stronger bounds than the ones obtained using the Semidefinite Programming relaxation. The new relaxation is based on the Boolean Quadric Polytope and is solved via a Dantzig-Wolfe Reformulation in matrix space. For block-decomposable problems, we extend the relaxation … Read more

    An exact algorithm for robust influence maximization

  • Giacomo Nannicini
  • Roberto Wolfler Calvo
  • Giorgio Sartor
  • Emiliano Traversi
    • Categories Branch and Cut Algorithms, Robust Optimization Tags , ,

    We propose a Branch-and-Cut algorithm for the robust influence maximization problem. The influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with … Read more

    Convex optimization under combinatorial sparsity constraints

  • Christoph Buchheim
  • Emiliano Traversi
    • Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , ,

    We present a heuristic approach for convex optimization problems containing sparsity constraints. The latter can be cardinality constraints, but our approach also covers more complex constraints on the support of the solution. For the special case that the support is required to belong to a matroid, we propose an exchange heuristic adapting the support in … Read more

    A Benders squared (B2) framework for infinite-horizon stochastic linear programs

  • Giacomo Nannicini
  • Roberto Wolfler Calvo
  • Emiliano Traversi
    • Categories Cutting Plane Approaches, Linear Programming, Stochastic Programming

    We propose a nested decomposition scheme for infinite-horizon stochastic linear programs. Our approach can be seen as a provably convergent extension of stochastic dual dynamic programming to the infinite-horizon setting: we explore a sequence of finite-horizon problems of increasing length until we can prove convergence with a given confidence level. The methodology alternates between a … Read more

    A simplicial decomposition framework for large scale convex quadratic programming

  • Enrico Bettiol
  • Lucas Létocart
  • Francesco Rinaldi
  • Emiliano Traversi
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    In this paper, we analyze in depth a simplicial decomposition like algorithmic framework for large scale convex quadratic programming. In particular, we first propose two tailored strategies for handling the master problem. Then, we describe a few techniques for speeding up the solution of the pricing problem. We report extensive numerical experiments on both real … Read more

    Dantzig Wolfe decomposition and objective function convexification for binary quadratic problems: the cardinality constrained quadratic knapsack case

  • Alberto Ceselli
  • Lucas Létocart
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Quadratic Programming Tags , , ,

    The purpose of this paper is to provide strong reformulations for binary quadratic problems. We propose a first methodological analysis on a family of reformulations combining Dantzig-Wolfe decomposition and Quadratic Convex Reformulation principles. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We show that … Read more

    QPLIB: A Library of Quadratic Programming Instances

  • Pietro Belotti
  • Antonio Frangioni
  • Fabio Furini
  • Ambros Gleixner
  • Nicholas I. M. Gould
  • Leo Liberti
  • Andrea Lodi
  • Hans D Mittelmann
  • Ruth Misener
  • Nikolaos Sahinidis
  • Emiliano Traversi
  • Stefan Vigerske
  • Angelika Wiegele
    • Categories Quadratic Programming

    This paper describes a new instance library for Quadratic Programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function, the constrains, or both are quadratic. QP is a very “varied” class of problems, comprising sub-classes of problems ranging from trivial to undecidable. Solution methods for QP are very diverse, ranging … Read more

    Exact Approaches for the Knapsack Problem with Setups

  • Fabio Furini
  • Michele Monaci
  • Emiliano Traversi
    • Categories 0-1 Programming, Integer Programming Tags , , , ,

    We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We … Read more

    On the Separation of Split Inequalities for Non-Convex Quadratic Integer Programming

  • Christoph Buchheim
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming

    We investigate the computational potential of split inequalities for non-convex quadratic integer programming, first introduced by Letchford and further examined by Burer and Letchford. These inequalities can be separated by solving convex quadratic integer minimization problems. For small instances with box-constraints, we show that the resulting dual bounds are very tight; they can close a … Read more

    Extended Linear Formulation for Binary Quadratic Problems

  • Fabio Furini
  • Emiliano Traversi
    • Categories 0-1 Programming, Quadratic Programming

    In this work we propose and test a new linearisation technique for Binary Quadratic Problems (BQP). We computationally prove that the new formulation, called Extended Linear Formulation, performs much better than the standard one in practice, despite not being stronger in terms of Linear Programming relaxation (LP). We empirically prove that this behaviour is due … Read more