Comparative Analysis of Capacitated Arc Routing Formulations for Branch-Cut-and-Price Algorithms

  • Diego Pecin
  • Eduardo Uchoa
    • Categories Combinatorial Optimization, Integer Programming, Transportation

    The current best exact algorithms for the Capacitated Arc Routing Problem are based on the combination of cut and column generation. This work presents a deep theoretical investigation of the formulations behind those algorithms, classifying them and pointing similarities and differences, advantages and disadvantages. In particular, we discuss which families of cuts and branching strategies … Read more

    Planar Maximum Coverage Location Problem with Partial Coverage and General Spatial Representation of Demand and Service Zones

  • Manish Bansal
    • Categories Approximation Algorithms, Nonlinear Optimization, Production and Logistics

    We introduce a new generalization of the classical planar maximum coverage location problem (PMCLP) in which demand zones and service zone of each facility are represented by spatial objects such as circles, polygons, etc., and are allowed to be located anywhere in a continuous plane. In addition, we allow partial coverage in its true sense, … Read more

    Exploiting sparsity for the min k-partition problem

  • Hassan L. Hijazi
  • Guanglei Wang
    • Categories 0-1 Programming, Semi-definite Programming Tags , , ,

    The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a prohibitive number of valid inequalities and integer variables. In this … Read more

    On the effectiveness of primal and dual heuristics for the transportation problem

  • Jonas Schwinn
  • Ralf Werner
    • Categories Linear Programming, Optimization Software Benchmark

    The transportation problem is one of the most popular problems in linear programming. Over the course of time a multitude of exact solution methods and heuristics have been proposed. Due to substantial progress of exact solvers since the mid of the last century, the interest in heuristics for the transportation problem over the last few … Read more

    Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

  • David de Laat
  • Monique Laurent
  • Sander Gribling
    • Categories Semi-definite Programming Tags ,

    We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogues: the completely positive rank and the completely positive semidefinite rank. We study the convergence properties of our hierarchies, compare them … Read more

    Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

  • David de Laat
  • Monique Laurent
  • Sander Gribling
    • Categories Semi-definite Programming Tags , ,

    In this paper we study bipartite quantum correlations using techniques from tracial polynomial optimization. We construct a hierarchy of semidefinite programming lower bounds on the minimal entanglement dimension of a bipartite correlation. This hierarchy converges to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum … Read more

    On Affine Invariant Descent Directions

  • Yu-Hong Dai
  • Florian Jarre
  • Felix Lieder
    • Categories Nonlinear Optimization Tags , ,

    This paper explores the existence of affine invariant descent directions for unconstrained minimization. While there may exist several affine invariant descent directions for smooth functions $f$ at a given point, it is shown that for quadratic functions there exists exactly one invariant descent direction in the strictly convex case and generally none in the nondegenerate … Read more

    Optimized Assignment Patterns in Mobile Edge Cloud Networks

  • Alberto Ceselli
  • Marco Fiore
  • Marco Premoli
  • Stefano Secci
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Telecommunications Tags , , ,

    Given an existing Mobile Edge Cloud (MEC) network including virtualization facilities of limited capacity, and a set of mobile Access Points (AP) whose data traffic demand changes over time, we aim at finding plans for assigning APs traffic to MEC facilities so that the demand of each AP is satisfied and MEC facility capacities are … Read more

    The Adaptive Robust Multi-Period Alternating Current Optimal Power Flow Problem

  • Alvaro Lorca
  • Xu Andy Sun
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags , , ,

    This paper jointly addresses two major challenges in power system operations: i) dealing with non-convexity in the power flow equations, and ii) systematically capturing uncertainty in renewable power availability and in active and reactive power consumption at load buses. To overcome these challenges, this paper proposes a two-stage adaptive robust optimization model for the multi-period … Read more