(Mixed) Integer Nonlinear Programming

Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization

  • Immanuel M. Bomze
  • Bo Peng
  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Semi-definite Programming Tags , , , ,

    The Standard Quadratic optimization Problem (StQP), arguably the simplest among all classes of NP-hard optimization problems, consists of extremizing a quadratic form (the simplest nonlinear polynomial) over the standard simplex (the simplest polytope/compact feasible set). As a problem class, StQPs may be nonconvex with an exponential number of inefficient local solutions. StQPs arise in a … Read more

    Optimal Sports League Realignment

  • Nathan Brixius
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , ,

    We consider approaches for optimally organizing competitive sports leagues in light of competitive and logistical considerations. A common objective is to assign teams to divisions so that intradivisional travel is minimized. We present a bilinear programming formulation based on k-way equipartitioning, and show how this formulation can be extended to account for additional constraints and … Read more

    Considering homeowner acceptance of retrofit measures within energy supply network optimization

  • carl.eggen
  • Moritz Link
  • Stefan Volkwein
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Multi-Criteria Optimization Tags , , ,

    A key factor towards a low-carbon society is energy efficient heating of private houses. The choice of heating technology as well as the decision for certain energy-efficient house renovations are made mainly by individual homeowners. In contrast, municipal energy network planning heavily depends on and strongly affects these decisions. Further, there are different conflicting objectives … Read more

    Detecting and Handling Reflection Symmetries in Mixed-Integer (Nonlinear) Programming

  • Christopher Hojny
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming

    Symmetries in mixed-integer (nonlinear) programs (MINLP), if not handled appropriately, are known to negatively impact the performance of (spatial) branch-and-bound algorithms. Usually one thus tries to remove symmetries from the problem formulation or is relying on a solver that automatically detects and handles symmetries. While modelers of a problem can handle various kinds of symmetries, … Read more

    A Clustering-based uncertainty set for Robust Optimization

  • Alireza Yazdani
  • Ahmadreza Marandi
  • Rob Basten
  • Lijia Tan
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Robust Optimization Tags , , , ,

    Robust Optimization (RO) is an approach to tackle uncertainties in the parameters of an optimization problem. Constructing an uncertainty set is crucial for RO, as it determines the quality and the conservativeness of the solutions. In this paper, we introduce an approach for constructing a data-driven uncertainty set through volume-based clustering, which we call Minimum-Volume … Read more

    A Parametric Approach for Solving Convex Quadratic Optimization with Indicators Over Trees

  • Aaresh Bhathena
  • Salar Fattahi
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Quadratic Programming Tags , , , , ,

    This paper investigates convex quadratic optimization problems involving $n$ indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix $Q$ defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this … Read more

    A Sequential Benders-based Mixed-Integer Quadratic Programming Algorithm

  • Andrea Ghezzi
  • Wim Van Roy
  • Sebastian Sager
  • Moritz Diehl
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Optimization Software Benchmark Tags , , , ,

    For continuous decision spaces, nonlinear programs (NLPs) can be efficiently solved via sequential quadratic programming (SQP) and, more generally, sequential convex programming (SCP). These algorithms linearize only the nonlinear equality constraints and keep the outer convex structure of the problem intact, such as (conic) inequality constraints or convex objective terms. The aim of the presented … Read more

    Polyhedral Analysis of Quadratic Optimization Problems with Stieltjes Matrices and Indicators

  • Peijing Liu
  • Alper Atamturk
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising … Read more

    Adjustable Robust Nonlinear Network Design under Demand Uncertainties

  • Johannes Thürauf
  • Julia Grübel
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Energy, Robust Optimization Tags , , , ,

    We study network design problems for nonlinear and nonconvex flow models under demand uncertainties. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, demand scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear … Read more

    Using Disjunctive Cuts in a Branch-and-Cut Method to Solve Convex Integer Nonlinear Bilevel Problems

  • Horländer Andreas
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    We present a branch-and-cut method for solving convex integer nonlinear bilevel problems, i.e., bilevel models with nonlinear but convex objective functions and constraints in both the upper and the lower level. To this end, we generalize the idea of using disjunctive cuts to cut off integer-feasible but bilevel-infeasible points. These cuts can be obtained by … Read more