Month: September 2003

A Comparative Study of New Barrier Functions for Primal-Dual Interior-Point Algorithms in Linear Optimization

  • Y.Q. Bai
  • Cornelis Roos
  • M. Elghami
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    Recently, so-called self-regular barrier functions for primal-dual interior-point methods (IPMs) for linear optimization were introduced. Each such barrier function is determined by its (univariate) self-regular kernel function. We introduce a new class of kernel functions. The class is defined by some simple conditions on the kernel function and its derivatives. These properties enable us to … Read more

    The structured distance to ill-posedness for conic systems

  • Adrian Lewis
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    An important measure of conditioning of a conic linear system is the size of the smallest structured perturbation making the system ill-posed. We show that this measure is unchanged if we restrict to perturbations of low rank. We thereby derive a broad generalization of the classical Eckart-Young result characterizing the distance to ill-posedness for a … Read more

    A Fast Swap-based Local Search Procedure for Location Problems

  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Combinatorial Optimization, Facility Planning and Design Tags , ,

    We present a new implementation of a widely used swap-based local search procedure for the P-median problem, proposed in 1968 by Teitz and Bart. Our method produces the same output as the best alternatives described in the literature and, even though it does not have a better worst-case complexity, it can be significantly faster in … Read more

    On the block-structured distance to non-surjectivity of sublinear mappings

  • Javier F. Peña
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , ,

    We show that the block-structured distance to non-surjectivity of a set-valued sublinear mapping equals the reciprocal of a suitable block-structured norm of its inverse. This gives a natural generalization of the classical Eckart and Young identity for square invertible matrices. CitationMathematical Programming 103 (2005) pp. 561–573.

    A Branch-and-Cut Algorithm for Graph Coloring

  • Isabel Méndez-Díaz
  • Paula Zabala
    • Categories Branch and Cut Algorithms, Polyhedra

    In a previous work, we proposed a new integer programming formulation for the graph coloring problem which, to a certain extent, avoids symmetry. We studied the facet structure of the 0/1-polytope associated with it. Based on these theoretical results, we present now a Branch-and-Cut algorithm for the graph coloring problem. Our computational experiences compare favorably … Read more

    The Quadratic Selective Travelling Saleman Problem

  • Thomas R. Stidsen
  • Tommy Thomadsen
    • Categories 0-1 Programming, Branch and Cut Algorithms, Network Optimization Tags , , ,

    A well-known extension of the Travelling Salesman Problem (TSP) is the Selective TSP (STSP): Each node has an associated profit and instead of visiting all nodes, the most profitable set of nodes, taking into account the tour cost, is visited. The Quadratic STSP (QSTSP) adds the additional complication that each pair of nodes have an … Read more