mixed-integer nonlinear programming

Convex Relaxations for Quadratic On/Off Constraints and Applications to Optimal Transmission Switching

  • Ksenia Bestuzheva
  • Carleton Coffrin
  • Hassan L. Hijazi
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Convex Optimization Tags , , , ,

    This paper studies mixed-integer nonlinear programs featuring disjunctive constraints and trigonometric functions. We first characterize the convex hull of univariate quadratic on/off constraints in the space of original variables using perspective functions. We then introduce new tight quadratic relaxations for trigonometric functions featuring variables with asymmetrical bounds. These results are used to further tighten recent … Read more

    An Adaptive Discretization MINLP Algorithm for Optimal Synthesis of Decentralized Energy Supply Systems

  • Björn Bahl
  • André Bardow
  • Arie M.C.A. Koster
  • Marco E. Lübbecke
  • Sebastian Goderbauer
  • Philip Voll
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering Tags , , , ,

    Decentralized energy supply systems (DESS) are highly integrated and complex systems designed to meet time-varying energy demands, e.g., heating, cooling, and electricity. The synthesis problem of DESS addresses combining various types of energy conversion units, choosing their sizing and operations to maximize an objective function, e.g., the net present value. In practice, investment costs and … Read more

    Three ideas for a Feasibility Pump for nonconvex MINLP

  • Pietro Belotti
  • Timo Berthold
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    We describe an implementation of the Feasibility Pump heuristic for nonconvex MINLPs. Our implementation takes advantage of three novel techniques, which we discuss here: a hierarchy of procedures for obtaining an integer solution, a generalized definition of the distance function that takes into account the nonlinear character of the problem, and the insertion of linearization … Read more

    Minimization of Akaike’s Information Criterion in Linear Regression Analysis via Mixed Integer Nonlinear Program

  • Keiji Kimura
  • Hayato Waki
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    Akaike’s information criterion (AIC) is a measure of the quality of a statistical model for a given set of data. We can determine the best statistical model for a particular data set by the minimization of the AIC. Since we need to evaluate exponentially many candidates of the model by the minimization of the AIC, … Read more

    An Exact Algorithm for a Resource Allocation Problem in Mobile Wireless Communications

  • Adam N. Letchford
  • Qiang Ni
  • Zhaoyu Zhong
    • Categories (Mixed) Integer Nonlinear Programming, Telecommunications Tags ,

    We consider a challenging resource allocation problem arising in mobile wireless communications. The goal is to allocate the available channels and power in a so-called OFDMA system, in order to maximise the transmission rate, subject to quality of service (QoS) constraints. Standard MINLP software struggled to solve even small instances of this problem. Using outer … Read more

    Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps

  • Björn Geißler
  • Antonio Morsi
  • Lars Schewe
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. … Read more

    Three Enhancements for Optimization-Based Bound Tightening

  • Timo Berthold
  • Ambros Gleixner
  • Benjamin Müller
  • Stefan Weltge
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags , , , , ,

    Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper … Read more

    Column Generation based Alternating Direction Methods for solving MINLPs

  • Ivo Nowak
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Parallel Algorithms Tags , , , , , ,

    Traditional decomposition based branch-and-bound algorithms, like branch-and-price, can be very efficient if the duality gap is not too large. However, if this is not the case, the branch-and-bound tree may grow rapidly, preventing the method to find a good solution. In this paper, we present a new decompositon algorithm, called ADGO (Alternating Direction Global Optimization … Read more

    GasLib – A Library of Gas Network Instances

  • Denis Aßmann
  • Robert Burlacu
  • Imke Joormann
  • Thorsten Koch
  • Marc E. Pfetsch
  • Lars Schewe
  • Martin Schmidt
  • Mathias Sirvent
  • Jesco Humpola
  • Nikolaos Kanelakis
  • Djamal Oucherif
  • Robert Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering Tags , , , ,

    The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances … Read more

    A multiplicative weights update algorithm for MINLP

  • Leo Liberti
  • Luca Mencarelli
  • Youcef Sahraoui
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , ,

    We discuss an application of the well-known Multiplicative Weights Update (MWU) algorithm to non-convex and mixed-integer nonlinear programming. We present applications to: (a) the distance geometry problem, which arises in the positioning of mobile sensors and in protein conformation; (b) a hydro unit commitment problem arising in the energy industry, and (c) a class of … Read more