Lucas Létocart

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

    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

    Exact Solution Methods for the hBcitem Quadratic Knapsack Problem

  • Lucas Létocart
  • Angelika Wiegele
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    The purpose of this paper is to solve the 0-1 k-item quadratic knapsack problem (kQKP), a problem of maximizing a quadratic function subject to two linear constraints.We propose an exact method based on semide nite optimization. The semide nite relaxation used in our approach includes simple rank one constraints, which can be handled efficiently by interior point … Read more