Network Optimization

A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints

  • Ion Necoara
  • Andrei Patrascu
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Network Optimization Tags , , , ,

    In this paper we present a variant of random coordinate descent method for solving linearly constrained convex optimization problems with composite objective function. If the smooth part has Lipschitz continuous gradient, then the method terminates with an ϵ-optimal solution in O(N2/ϵ) iterations, where N is the number of blocks. For the class of problems with … Read more

    Optimizing Placement of Stationary Monitors

  • Guanghui Lan
  • Andrew Romich
  • J. Cole Smith
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization

    We examine the problem of placing stationary monitors in a continuous space, with the goal of minimizing an adversary’s maximum probability of traversing an origin-destination route without being detected. The problem arises, for instance, in defending against the transport of illicit material through some area of interest. In particular, we consider the deployment of monitors … Read more

    Minimum Concave Cost Flow Over a Grid Network

  • Shabbir Ahmed
  • Qie He
  • George L. Nemhauser
    • Categories Combinatorial Optimization, Network Optimization, Production and Logistics Tags , ,

    The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases such as the uncapacitated lot-sizing problem and many of its variants. We study the MCCNFP over a grid network with a general nonnegative separable concave cost function. We show that this problem is polynomially solvable when … Read more

    Semi-continuous network flow problems

  • Shabbir Ahmed
  • Gustavo Angulo
  • Santanu S. Dey
    • Categories (Mixed) Integer Linear Programming, Network Optimization Tags , ,

    We consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are restricted to be semi-continuous. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present … Read more

    On the hop-constrained survivable network design problem with reliable edges

  • Quentin Botton
  • Bernard Fortz
  • Luís Gouveia
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Network Optimization Tags , , , ,

    In this paper, we study the hop-constrained survivable network design problem with reliable edges. Given a graph with non-negative edge weights and node pairs Q, the hop-constrained survivable network design problem consists of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L … Read more

    An aggressive reduction scheme for the simple plant location problem

  • Adam N. Letchford
  • Sebastian J. Miller
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags ,

    Pisinger et al. introduced the concept of `aggressive reduction’ for large-scale combinatorial optimisation problems. The idea is to spend much time and effort in reducing the size of the instance, in the hope that the reduced instance will then be small enough to be solved by an exact algorithm. We present an aggressive reduction scheme … Read more

    Branch-and-Price Guided Search for Integer Programs with an Application to the Multicommodity Fixed Charge Network Flow Problem

  • Mike Hewitt
  • George L. Nemhauser
  • Martin Savelsbergh
    • Categories (Mixed) Integer Linear Programming, Network Optimization

    We develop an exact algorithm for integer programs that uses restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for generating these problem restrictions and for producing bounds on the value of the optimal solution. The performance of the algorithm is greatly enhanced by using structure, such as arises in … Read more

    D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization

  • Pedro Aguiar
  • João Mota
  • Markus Püschel
  • João Xavier
    • Categories Convex Optimization, Network Optimization Tags , , , , ,

    We propose a distributed algorithm, named D-ADMM, for solving separable optimization problems in networks of interconnected nodes or agents. In a separable optimization problem, the cost function is the sum of all the agents’ private cost functions, and the constraint set is the intersection of all the agents’ private constraint sets. We require the private … Read more

    Reformulation of a model for hierarchical divisive graph modularity maximization

  • Sonia Cafieri
  • Alberto Costa
  • Pierre Hansen
    • Categories Convex Optimization, Network Optimization, Quadratic Programming Tags , , ,

    Finding clusters, or communities, in a graph, or network is a very important problem which arises in many domains. Several models were proposed for its solution. One of the most studied and exploited is the maximization of the so called modularity, which represents the sum over all communities of the fraction of edges within these … Read more

    Optimal Response to Epidemics and Cyber Attacks in Networks

  • Noam Goldberg
  • Sven Leyffer
  • Ilya Safro
    • Categories 0-1 Programming, Cutting Plane Approaches, Network Optimization Tags , , , , ,

    This paper introduces novel formulations for optimally responding to epidemics and cyber attacks in networks. In our models, at a given time period, network nodes (e.g., users or computing resources) are associated with probabilities of being infected, and each network edge is associated with some probability of propagating the infection. A decision maker would like … Read more