dantzig-wolfe reformulation

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

    Avoiding redundant columns by adding classical Benders cuts to column generation subproblems

  • Marco E. Lübbecke
  • Stephen J. Maher
  • Jonas T. Witt
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    When solving the linear programming (LP) relaxation of a mixed-integer program (MIP) with column generation, columns might be generated that are not needed to express any integer optimal solution of the MIP. Such columns are called strongly redundant and the dual bound obtained by solving the LP relaxation is potentially stronger if these columns are … Read more