benders decomposition

Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems

  • Stefano Coniglio
  • Fabio Furini
  • Ivana Ljubić
    • Categories Cutting Plane Approaches, Integer Programming, Nonlinear Optimization Tags , ,

    We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function … Read more

    An Exact Solution Method for the TSP with Drone Based on Decomposition

  • Gustavo Angulo
  • Mathias A. Klapp
  • Sebastián A. Vásquez
    • Categories (Mixed) Integer Linear Programming, Production and Logistics Tags , , ,

    The Traveling Salesperson Problem with Drone (TSP–D) is a routing model in which a given set of customer locations must be visited in the least amount of time, either by a truck route starting and ending at a depot or by a drone dispatched from the truck en route. We study the TSP–D model and … 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

    The Star Degree Centrality Problem: A Decomposition Approach

  • Mustafa Can Camur
  • Thomas C. Sharkey
  • Chrysafis Vogiatzis
    • Categories 0-1 Programming, Cutting Plane Approaches, Network Optimization Tags , ,

    We consider the problem of identifying the induced star with the largest cardinality open neighborhood in a graph. This problem, also known as the star degree centrality (SDC) problem, has been shown to be 𝒩𝒫-complete. In this work, we first propose a new integer programming (IP) formulation, which has a fewer number of constraints and … Read more

    Learning Optimal Classification Trees: Strong Max-Flow Formulations

  • Sina Aghaei
  • Andrés Gómez
  • Phebe Vayanos
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Statistics Tags , , ,

    We consider the problem of learning optimal binary classification trees. Literature on the topic has burgeoned in recent years, motivated both by the empirical suboptimality of heuristic approaches and the tremendous improvements in mixed-integer programming (MIP) technology. Yet, existing approaches from the literature do not leverage the power of MIP to its full extent. Indeed, … Read more

    The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment

  • Jonas Egerer
  • Veronika Grimm
  • Thomas Kleinert
  • Martin Schmidt
  • Gregor Zöttl
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , ,

    Many long-term investment planning models for liberalized electricity markets either optimize for the entire electricity system or focus on confined jurisdictions, abstracting from adjacent markets. In this paper, we provide models for analyzing the impact of the interdependencies between a core electricity market and its neighboring markets on key long-run decisions. This we do both … Read more

    Single Allocation Hub Location with Heterogeneous Economies of Scale

  • Okan Arslan
  • Masoud Chitsaz
  • Gilbert Laporte
  • Andrea Lodi
  • Borzou Rostami
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , , ,

    We study the single allocation hub location problem with heterogeneous economies of scale (SAHLP-h). The SAHLP-h is a generalization of the classical single allocation hub location problem (SAHLP), in which the hub-hub connection costs are piecewise linear functions of the amounts of flow. We model the problem as an integer non-linear program, which we then … Read more

    Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework

  • Stephen J. Maher
    • Categories Integer Programming, Optimization Software and Modeling Systems Tags , , , ,

    Benders’ decomposition is a popular mathematical and constraint programming algorithm that is widely applied to exploit problem structure arising from real-world applications. While useful for exploiting structure in mathematical and constraint programs, the use of Benders’ decomposition typically requires significant implementation effort to achieve an effective solution algorithm. Traditionally, Benders’ decomposition has been viewed as … Read more

    A Computationally Efficient Algorithm for Computing Convex Hull Prices

  • Anya Castillo
  • Bernard Knueven
  • James Ostrowski
  • Jean-Paul Watson
    • Categories Applications - OR and Management Sciences Tags , , , ,

    Electricity markets worldwide allow participants to bid non-convex production offers. While non-convex offers can more accurately reflect a resource’s capabilities, they create challenges for market clearing processes. For example, system operators may be required to execute side payments to participants whose costs are not covered through energy sales as determined via traditional locational marginal pricing … Read more

    Benders Decomposition with Adaptive Oracles for Large Scale Optimization

  • Andreas Grothey
  • Kenneth McKinnon
  • Nicolò Mazzi
  • Nagisa Sugishita
    • Categories Applications - OR and Management Sciences Tags , , ,

    This paper proposes an algorithm to efficiently solve large optimization problems which exhibit a column bounded block-diagonal structure, where subproblems differ in right-hand side and cost coefficients. Similar problems are often tackled using cutting-plane algorithms, which allow for an iterative and decomposed solution of the problem. When solving subproblems is computationally expensive and the set … Read more