Integer Programming

Tightening Quadratic Convex Relaxations for the AC Optimal Transmission Switching Problem

  • Cheng Guo
  • Harsha Nagarajan
  • Merve Bodur
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    The Alternating Current Optimal Transmission Switching (ACOTS) problem incorporates line switching decisions into the fundamental AC optimal power flow (ACOPF) problem. The advantages of the ACOTS problem are well-known in terms of reducing the operational cost and improving system reliability. ACOTS optimization models contain discrete variables and nonlinear, non-convex constraints, which make it difficult to … Read more

    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

    A Branch and Bound Algorithm for Biobjective Mixed Integer Quadratic Programs

  • Pubudu L.W. Jayasekara Merenchige
  • Margaret Wiecek
    • Categories (Mixed) Integer Nonlinear Programming, Integer Programming, Multi-Criteria Optimization Tags , , , , ,

    Multiobjective quadratic programs (MOQPs) are appealing since convex quadratic programs have elegant mathematical properties and model important applications. Adding mixed-integer variables extends their applicability while the resulting programs become global optimization problems. We design and implement a branch and bound (BB) algorithm for biobjective mixed-integer quadratic programs (BOMIQPs). In contrast to the existing algorithms in … Read more

    Handling Symmetries in Mixed-Integer Semidefinite Programs

  • Christopher Hojny
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , ,

    Symmetry handling is a key technique for reducing the running time of branch-and-bound methods for solving mixed-integer linear programs. In this paper, we generalize the notion of (permutation) symmetries to mixed-integer semidefinite programs (MISDPs). We first discuss how symmetries of MISDPs can be automatically detected by finding automorphisms of a suitably colored auxiliary graph. Then … Read more

    Handling Sub-symmetry in Integer Programming using Activation Handlers

  • Christopher Hojny
  • Tom Verhoeff
  • Sten Wessel
    • Categories Integer Programming Tags , ,

    Symmetry in integer programs (IPs) can be exploited in order to reduce solving times. Usually only symmetries of the original IP are handled, but new symmetries may arise at some nodes of the branch-and-bound tree. While symmetry-handling inequalities (SHIs) can easily be used to handle original symmetries, handling sub-symmetries arising later on is more intricate. … Read more

    A Voronoi-Based Mixed-Integer Gauss-Newton Algorithm for MINLP Arising in Optimal Control

  • Andrea Ghezzi
  • LeoS
  • Adrian Bürger
  • Clemens Zeile
  • Sebastian Sager
  • Moritz Diehl
    • Categories (Mixed) Integer Nonlinear Programming, Control Applications, Nonlinear Systems and Least-Squares Tags ,

    We present a new algorithm for addressing nonconvex Mixed-Integer Nonlinear Programs (MINLPs) where the cost function is of nonlinear least squares form. We exploit this structure by leveraging a Gauss-Newton quadratic approximation of the original MINLP, leading to the formulation of a Mixed-Integer Quadratic Program (MIQP), which can be solved efficiently. The integer solution of the … Read more

    Improvements for Decomposition Based Methods Utilized in the Development of Multi-Scale Energy Systems

  • R. Cory Allen
  • Efstratios N. Pistikopoulos
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Facility Planning and Design

    The optimal design of large-scale energy systems can be found by posing the problem as an integrated multi-period planning and scheduling mathematical programming problem. Due to the complexity of the accompanying mathematical programming problem decomposition techniques are often required but they to are plagued with converge issues. To address these issues we have derived a … Read more

    A polyhedral study of multivariate decision trees

  • Carla Michini
  • Zachary Zhou
    • Categories (Mixed) Integer Linear Programming, Data Science Theory, Polyhedra Tags , ,

    Decision trees are a widely used tool for interpretable machine learning. Multivariate decision trees employ hyperplanes at the branch nodes to route datapoints throughout the tree and yield more compact models than univariate trees. Recently, mixed-integer programming (MIP) has been applied to formulate the optimal decision tree problem. To strengthen MIP formulations, it is crucial … Read more

    On Constrained Mixed-Integer DR-Submodular Minimization

  • Qimeng Yu
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Polyhedra Tags , , ,

    DR-submodular functions encompass a broad class of functions which are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide … Read more