Optimization Online Digest — September 2003

Applications — OR and Management Sciences

Continuous Line Drawings via the Traveling Salesman Problem
Robert Bosch, Adrianne Herman

Constructing Domino Portraits
Robert Bosch

Applications — Science and Engineering

A Fast Swap-based Local Search Procedure for Location Problems
Mauricio G. C. Resende, Renato F. Werneck

A hybrid multistart heuristic for the uncapacitated facility location problem
Mauricio G. C. Resende, Renato F. Werneck

A masked spectral bound for maximum-entropy sampling
Kurt Anstreicher, Jon Lee

Combinatorial Optimization

The Quadratic Selective Travelling Saleman Problem
Tommy Thomadsen, Thomas Stidsen

A Branch-and-Cut Algorithm for Graph Coloring
Isabel Méndez-Díaz, Paula Zabala

The Generalized Subgraph Problem: Complexity, Approximability and Polyhedra
Corinne Feremans, Martine Labbé, Adam Letchford, Juan José Salazar

The Bundle Method in Combinatorial Optimization
Ilse Fischer , Gerald Gruber, Franz Rendl, Renata Sotirov

Network Reinforcement
Francisco Barahona

Complementarity and Variational Inequalities

A robust SQP method for mathematical programs with linear complementarity constraints
Xinwei Liu, Georgia Perakis, Jie Sun

A Homogeneous Model for $P_0$ and $P_*$ Nonlinear Complementarity Problems
Akiko Yoshise

Convex and Nonsmooth Optimization

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

The structured distance to ill-posedness for conic systems
Adrian Lewis

Global Optimization

Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems
Sunyoung Kim, Masakazu Kojima, Hayato Waki

Integer Programming

An Exact Algorithm for the Capacitated Vertex p-Center Problem
F.A. Ozsoy, M.C. Pinar

Decomposition and Dynamic Cut Generation in Integer Linear Programming
T.K. Ralphs, M.V. Galati

Valid inequalities based on simple mixed-integer sets
Sanjeeb Dash, Oktay Gunluk

Linear, Cone and Semidefinite Programming

A Comparative Study of New Barrier Functions for Primal-Dual Interior-Point Algorithms in Linear Optimization
Y.Q. Bai, M. Elghami, C. Roos

A Semidefinite Programming Approach for the Nearest Correlation Matrix Problem
Miguel F. Anjos, Nicholas J. Higham, Pawoumodom L. Takouda, Henry Wolkowicz

On Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
Dennis Cheung, Felipe Cucker, Raphael Hauser

A Pivotting Procedure for a Class of Second-Order Cone Programming
Masakazu Muramatsu

Sparsity in Sums of Squares of Polynomials
Masakazu Kojima, Sunyoung Kim, Hayato Waki

Local Minima and Convergence in Low-Rank Semidefinite Programming
Samuel Burer, Renato Monteiro

Network Optimization

Speeding up dynamic shortest path algorithms
Luciana S. Buriol, Mauricio G.C. Resende, Mikkel Thorup

Nonlinear Optimization

An Algorithm for Degenerate Nonlinear Programming with Rapid Local Convergence
Stephen Wright