scip

Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0

  • Ksenia Bestuzheva
  • Antonia Chmiela
  • Benjamin Müller
  • Felipe Serrano
  • Stefan Vigerske
  • Fabian Wegscheider
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Optimization Software and Modeling Systems Tags , , ,

    For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version 8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that … Read more

    The Mcf-Separator – Detecting and Exploiting Multi-Commodity Flow Structures in MIPs

  • Tobias Achterberg
  • Christian Raack
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Network Optimization Tags , , , , ,

    Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of Scip … Read more