mixed-integer nonlinear programming

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

    Quantifying Double McCormick

  • Jon Lee
  • Emily Speakman
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , , , , ,

    When using the standard McCormick inequalities twice to convexify trilinear monomials, as is often the practice in modeling and software, there is a choice of which variables to group first. For the important case in which the domain is a nonnegative box, we calculate the volume of the resulting relaxation, as a function of the … Read more

    Convex Relaxations for Gas Expansion Planning

  • Scott Backhaus
  • Conrado Borraz-Sanchez
  • Hassan L. Hijazi
  • Pascal Van Hentenryck
  • Russell Bent
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Applications Tags , , ,

    Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the non-convex nature of gas transmission constraints, global optimality and infeasibility guarantees can only be offered by global optimisation approaches. Unfortunately, state-of-the-art global optimisation solvers are unable to scale up to real-world size instances. In this study, … Read more

    Transmission and Generation Investment in Electricity Markets: The Effects of Market Splitting and Network Fee Regimes

  • Veronika Grimm
  • Martin Schmidt
  • Alexander Martin
  • Weibelzahl Martin
  • Gregor Zöttl
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Network Optimization Tags , , , , ,

    We propose an equilibrium model that allows to analyze the long-run impact of the regulatory environment on transmission line expansion by the regulator and investment in generation capacity by private firms in liberalized electricity markets. The model incorporates investment decisions of the transmission operator and private firms in expectation of an energy-only market and cost-based … Read more

    An Overview on Mathematical Programming Approaches for the Deterministic Unit Commitment Problem in Hydro Valleys

  • Claudia D'Ambrosio
  • Raouia Taktak
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , , ,

    With the fast-growing demand in the electricity market of the last decades, attention has been focused on alternative and flexible sources of energy such as hydro valleys. Managing the hydroelectricity produced by the plants in hydro valleys is called the hydro unit commitment problem. This problem consists in finding the optimal power production schedule of … Read more

    LP formulations for mixed-integer polynomial optimization problems

  • Daniel Bienstock
  • Gonzalo Muñoz
    • Categories (Mixed) Integer Nonlinear Programming, Nonsmooth Optimization Tags

    We present polynomial-time algorithms for constrained optimization problems overwhere the intersection graph of the constraint set has bounded tree-width. In the case of binary variables we obtain exact, polynomial-size linear programming formulations for the problem. In the mixed-integer case with bounded variables we obtain polynomial-size linear programming representations that attain guaranteed optimality and feasibility bounds. … Read more