Network Optimization

A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems

  • Richard Krug
  • Günter Leugering
  • Alexander Martin
  • Martin Schmidt
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Optimization of Systems modeled by PDEs Tags , , , ,

    We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel … Read more

    An Exact Method for Nonlinear Network Flow Interdiction Problems

  • Martin Schmidt
  • Johannes Thürauf
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Network Optimization Tags , , ,

    We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower’s problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal to maximize the load shed and the follower aims at minimizing … Read more

    Water Finds its Level: A Localized Method for Multicommodity Flow Problem

  • Pengfei Liu
    • Categories Network Optimization Tags , , , ,

    This paper describes a local-control method for multicommodity flow problem. Both the capacity constraints and the flow conservation constraints are relaxed. If the flow exceeds the capacity on an edge, the edge would have a congestion cost. If the flow into a vertex is not equal to that out of the vertex, the vertex would … Read more

    On the first order optimization methods in Deep Image Prior

  • Giorgia Franchini
  • Federica Porta
  • Andrea Sebastiani
    • Categories Network Optimization, Nonsmooth Optimization, Stochastic Approaches

    Deep learning methods have state-of-the-art performances in many image restoration tasks. Their effectiveness is mostly related to the size of the dataset used for the training. Deep Image Prior (DIP) is an energy function framework which eliminates the dependency on the training set, by considering the structure of a neural network as an handcrafted prior … Read more

    Linear-size formulations for connected planar graph partitioning and political districting

  • Jack Zhang
  • Hamidreza Validi
  • Austin Buchanan
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization

    Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, … Read more

    On Aligning Non-Order-Associated Binary Decision Diagrams.

  • Alexey Bochkarev
  • Cole Smith
    • Categories Combinatorial Optimization, Network Optimization Tags , , ,

    Recent studies employ collections of binary decision diagrams (BDDs) to solve combinatorial optimization problems. This paper focuses on the problem of optimally aligning two BDDs, i.e., transforming them to enforce a common order of variables while keeping the total size of the diagrams as small as possible. We address this problem, which is known to … Read more

    Source Detection on Graphs

  • Tobias Weber
  • Volker Kaibel
  • Sebastian Sager
    • Categories Graphs and Matroids, Network Optimization Tags , , , ,

    Spreading processes on networks (graphs) have become ubiquitous in modern society with prominent examples such as infections, rumors, excitations, contaminations, or disturbances. Finding the source of such processes based on observations is important and difficult. We abstract the problem mathematically as an optimization problem on graphs. For the deterministic setting we make connections to the … Read more

    Maximizing resilience in large-scale social networks

  • Samuel Kroger
  • Hamidreza Validi
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

    Motivated by the importance of social resilience as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph G=(V,E) and integers k and b, the maximum anchored k-core problem seeks to find a largest … Read more

    On optimally solving sub-tree scheduling for wireless sensor networks with partial coverage

  • Nicola Bianchessi
    • Categories Branch and Cut Algorithms, Network Optimization, Telecommunications Tags , , , , ,

    Energy efficiency and balancing are very important issues from the perspective of increasing the lifetime of a wireless sensor network (WSN). In this study, we concentrate on energy balancing. Given a WSN, we consider the problem to minimize its total power consumption over consecutive time slots with respect to communication activities. Disjoint subsets of nodes … Read more