Sven Mallach

A Family of Spanning-Tree Formulations for the Maximum Cut Problem

  • Sven Mallach
    • Categories Combinatorial Optimization, Integer Programming, Quadratic Programming

    We present a family of integer programming formulations for the maximum cut problem. These formulations encode the incidence vectors of the cuts of a connected graph by employing a subset of the odd-cycle inequalities that relate to a spanning tree, and they require only the corresponding edge variables to be integral explicitly. They so describe … Read more

    Inductive Linearization for Binary Quadratic Programs with Linear Constraints: A Computational Study

  • Sven Mallach
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Quadratic Programming Tags , , ,

    The computational performance of inductive linearizations for binary quadratic programs in combination with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances. Apparently, a few of these are solved to optimality for the first time. Citation preprint (no internal series / number): University of Bonn, Germany June 11, 2021 … Read more