(Mixed) Integer Nonlinear Programming

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization

  • Hussein Hazimeh
  • Rahul Mazumder
  • Ali Saab
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Second-Order Cone Programming Tags , , , ,

    We consider the least squares regression problem, penalized with a combination of the L0 and L2 norms (a.k.a. L0 L2 regularization). Recent work presents strong evidence that the resulting L0-based estimators can outperform popular sparse learning methods, under many important high-dimensional settings. However, exact computation of L0-based estimators remains a major challenge. Indeed, state-of-the-art mixed … Read more

    Mathematical Optimization and Machine Learning for Efficient Urban Traffic

  • Johanna Bethge
  • Maximilian Merkert
  • Sebastian Sager
  • Anton Savchenko
  • Rolf Findeisen
  • Do Duc Le
  • Hannes Rewald
  • Stephan Sorgatz
    • Categories (Mixed) Integer Nonlinear Programming, Control Applications, Transportation Tags , , , , , ,

    Traffic jams cause economical damage which has been estimated between 10 and 100 billion Euros per year in Germany, also due to inefficient urban traffic. It is currently open how the situation will change with upcoming technological advances in autonomous and electric mobility. On the one hand, autonomous cars may lead to an increased number … Read more

    On monotonicity and search traversal in copositivity detection algorithms

  • Leocadio G Casado
  • Eligius M.T. Hendrix
  • Boglárka Tóth
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags , , ,

    Matrix copositivity has an important theoretical background. Over the last decades, the use of algorithms to check copositivity has made a big progress. Methods are based on spatial branch and bound, transformation to Mixed Integer Programming, implicit enumeration of KKT points or face-based search. Our research question focuses on exploiting the mathematical properties of the … Read more

    An MISOCP-Based Solution Approach to the Reactive Optimal Power Flow Problem

  • Sezen Ece Kayacık
  • Burak Kocuk
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering

    In this letter, we present an alternative mixed-integer non-liner programming formulation of the reactive optimal power flow (ROPF) problem. We utilize a mixed-integer second-order cone programming (MISOCP) based approach to find global optimal solutions of the proposed ROPF problem formulation. We strengthen the MISOCP relaxation via the addition of convex envelopes and cutting planes. Computational … Read more

    The SCIP Optimization Suite 7.0

  • Daniel Anderson
  • Ksenia Bestuzheva
  • Wei-Kun Chen
  • Leon Eifler
  • Gerald Gamrath
  • Maxime Gasse
  • Ambros Gleixner
  • Gregor Hendel
  • Christopher Hojny
  • Thorsten Koch
  • Pierre Le Bodic
  • Stephen J. Maher
  • Frederic Matter
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Dieter Weninger
  • Jakob Witzig
  • Patrick Gemander
  • Leona Gottwald
  • Katrin Halbig
  • Erik Mühmer
  • Benjamin Müller
  • Franziska Schlösser
  • Yuji Shinano
  • Christine Tawfik
  • Stefan Vigerske
  • Fabian Wegscheider
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more

    A numerical study of transformed mixed-integer optimal control problems

  • Sebastian Sager
  • Manuel Tetschke
  • Clemens Zeile
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Systems governed by Differential Equations Optimization Tags , , , ,

    Time transformation is a ubiquitous tool in theoretical sciences, especially in physics. It can also be used to transform switched optimal con trol problems into control problems with a fixed switching order and purely continuous decisions. This approach is known either as enhanced time transformation, time-scaling, or switching time optimization (STO) for mixed-integer optimal control. … Read more

    Polyhedral Approximation Strategies in Nonconvex Mixed-Integer Nonlinear Programming

  • Jan Kronqvist
  • Andreas Lundell
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software Benchmark, Optimization Software Design Principles

    Different versions of polyhedral outer approximation is used by many algorithms for mixed-integer nonlinear programming (MINLP). While it has been demonstrated that such methods work well for convex MINLP, extending them to solve also nonconvex problems has been challenging. One solver based on outer linearization of the nonlinear feasible set of MINLP problems is the … Read more

    Strong Relaxations for Continuous Nonlinear Programs Based on Decision Diagrams

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization

    Over the past decade, Decision Diagrams (DDs) have risen as a powerful modeling tool to solve discrete optimization problems. The extension of this emerging concept to continuous problems, however, has remained a challenge, posing a limitation on its applicability scope. In this paper, we introduce a novel framework that utilizes DDs to model continuous programs. … Read more

    Complexity of cutting planes and branch-and-bound in mixed-integer optimization

  • Amitabh Basu
  • Michele Conforti
  • Marco Di Summa
  • Hongyi Jiang
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , ,

    We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP … Read more

    Exact and Heuristic Algorithms for the Carrier-Vehicle Traveling Salesman Problem

  • Gunes Erdogan
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , ,

    This paper presents new structural properties for the Carrier-Vehicle Traveling Salesman Problem. The authors provide a new mixed integer second order conic optimization formulation, with associated optimality cuts based on the structural properties, and an Iterated Local Search (ILS) algorithm. Computational experiments on instances from the literature demonstrate the superiority of the new formulation to … Read more