(Mixed) Integer Nonlinear Programming

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

    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

    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

    A Unified Framework for Symmetry Handling

  • Jasper van Doornmalen
  • Christopher Hojny
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Integer Programming Tags , , , , ,

    Handling symmetries in optimization problems is essential for devising efficient solution methods. In this article, we present a general framework that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other, our framework allows to apply different methods simultaneously and thus outperforming their individual effect. Moreover, … Read more

    Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming: Part I

  • Ben Beach
  • Robert Burlacu
  • Andreas Bärmann
  • Lukas Hager
  • Robert Hildebrand
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , , ,

    We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present MIP relaxation methods for non-convex continuous variable products. In Part I, we consider MIP relaxations based on separable reformulation. The main focus is the introduction of the enhanced separable MIP relaxation for non-convex quadratic products … Read more

    A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems

  • Richard Krug
  • Günter Leugering
  • Alexander Martin
  • Martin Schmidt
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Optimization of Systems modeled by PDEs Tags , , , ,

    We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel … Read more

    An Exact Method for Nonlinear Network Flow Interdiction Problems

  • Martin Schmidt
  • Johannes Thürauf
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Network Optimization Tags , , ,

    We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower’s problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal to maximize the load shed and the follower aims at minimizing … Read more

    On the strength of recursive McCormick relaxations for binary polynomial optimization

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Integer Programming Tags , , , ,

    Recursive McCormick relaxations have been among the most popular convexification techniques for binary polynomial optimization problems. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal recursive sequence amounts to solving a difficult combinatorial optimization problem. In this paper, we prove that any … Read more