Month: October 2005

On the Implementation of Interior Point Decomposition Algorithms for Two-Stage Stochastic Conic

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Finance and Economics, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    In this paper we develop a practical primal interior decomposition algorithm for two-stage stochastic programming problems. The framework of this algorithm is similar to the framework in Mehrotra and \”{Ozevin} \cite{MO04a,MO04b} and Zhao \cite{GZ01}, however their algorithm is altered in a simple yet fundamental way to achieve practical performance. In particular, this new algorithm weighs … Read more

    A novel integer programming formulation for the K-SONET ring assignment problem

  • Elder M. Macambira
  • Claudio N. Meneses
  • Panos M. Pardalos
  • Mauricio G.C. Resende
    • Categories 0-1 Programming, Graphs and Matroids, Telecommunications Tags , , ,

    We consider the problem of interconnecting a set of customer sites using SONET rings of equal capacity, which can be defined as follows: Given an undirected graph G=(V,E) with nonnegative edge weight d(u,v), (u,v) in E, and two integers K and B, find a partition of the nodes of G into K subsets so that … Read more

    Sequential Subspace Optimization Method for Large-Scale Unconstrained Problems

  • Guy Narkiss
  • Michael Zibulevsky
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    We present the Sequential Subspace Optimization (SESOP) method for large scale smooth unconstrained problems. At each iteration we search for a minimum of the objective function over a subspace spanned by the current gradient and by directions of few previous steps. We also include into this subspace the direction from the starting point to the … Read more

    Low Order-Value Optimization and Applications

  • Roberto Andreani
  • Leandro Martínez
  • José Mario Martínez
  • Flavio Yano
    • Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Nonlinear Optimization Tags , , ,

    Given r real functions F1 (x), . . . , Fr (x) and an integer p between 1 and r, the Low Order- Value Optimization problem (LOVO) consists of minimizing the sum of the functions that take the p smaller values. If (y1 , . . . , yr ) is a vector of data … Read more

    Further Development of Multiple Centrality Correctors for Interior Point Methods

  • Marco Colombo
  • Jacek Gondzio
    • Categories Linear Programming Tags , , ,

    This paper addresses the role of centrality in the implementation of interior point methods. Theoretical arguments are provided to justify the use of a symmetric neighbourhood. These are translated into computational practice leading to a new insight into the role of re-centering in the implementation of interior point methods. Arguments are provided to show that … Read more

    On Time-Invariant Purified-Output-Based Discrete Time Control

  • Aharon Ben-Tal
  • Stephen Boyd
  • Arkadi Nemirovski
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , ,

    In http://www.optimizationonline.org/DB_HTML/2005/05/1136.html 05/25/05, we have demonstrated that the family of all affine non-anticipative output-based control laws in a discrete time linear dynamical system affected by uncertain disturbances is equivalent, as far as state-control trajectories are concerned, to the family of all affine non-anticipative “purified-output-based” control laws. The advantage of the latter representation of affine controls … Read more

    A special ordered set approach to discontinuous piecewise linear optimization

  • Ismael de Farias
  • Ming Zhao
  • Hongxia Zhao
    • Categories Integer Programming Tags , , ,

    Piecewise linear functions (PLFs) are commonly used to approximate nonlinear functions. They are also of interest in their own, arising for example in problems with economies of scale. Early approaches to piecewise linear optimization (PLO) assumed continuous PLFs. They include the incremental cost MIP model of Markowitz and Manne and the convex combination MIP model … Read more

    Combinatorial relaxations of the k-traveling salesman problem

  • Andrei Horbach
    • Categories Combinatorial Optimization, Graphs and Matroids Tags , , , ,

    The k-traveling salesman problem, or k-TSP is: given a graph with edge weights and an integer k, find a simple cycle of minimum weight visiting exactly k nodes. To obtain lower bounds for the traveling salesman problem the 2-matching relaxation and the 1-tree relaxation can be used. We generalize these two relaxations for the k-TSP. … Read more

    Disk Packing in a Square: A New Global Optimization Approach

  • Bernardetta Addis
  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization, Stochastic Approaches Tags , , , , ,

    We present a new computational approach to the problem of placing $n$ identical non overlapping disks in the unit square in such a way that their radius is maximized. The problem has been studied in a large number of papers, both from a theoretical and from a computational point of view. In this paper we … Read more

    Computational acceleration of projection algorithms for the linear best approximation problem

  • Yair Censor
    • Categories Convex Optimization

    This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra’s algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches … Read more