Strong semismoothness of eigenvalues of symmetric matrices and its application to inverse eigenvalue problems

It is well known that the eigenvalues of a real symmetric matrix are not everywhere differentiable. A classical result of Ky Fan states that each eigenvalue of a symmetric matrix is the difference of two convex functions. This directly implies that the eigenvalues of a symmetric matrix are semismooth everywhere. Based on a very recent … Read more

An Efficient Exact Algorithm for the Vertex p-Center Problem

Inspired by an algorithm due to Minieka, we develop a simple and yet very efficient exact algorithm for the problem of locating p facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility it is assigned to. After a lower bounding phase, the algorithm iteratively sets … Read more

New Benchmark Instances for the Steiner Problem in Graphs

We propose in this work 50 new test instances for the Steiner problem in graphs. These instances are characterized by large integrality gaps and symmetry aspects which make them harder to both exact methods and heuristics than the test problems currently in use for the evaluation and comparison of existing and newly developed algorithms. Our … Read more

Continuous trajectories for primal-dual potential-reduction methods

This article considers continuous trajectories of the vector fields induced by two different primal-dual potential-reduction algorithms for solving linear programming problems. For both algorithms, it is shown that the associated continuous trajectories include the central path and the duality gap converges to zero along all these trajectories. For the algorithm of Kojima, Mizuno, and Yoshise, … Read more

Greedy randomized adaptive search procedures

GRASP is a multi-start metaheuristic for combinatorial problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase. The best overall solution is kept as the result. In this chapter, … Read more

Simple Efficient Solutions for Semidefinite Programming

This paper provides a simple approach for solving a semidefinite program, SDP\@. As is common with many other approaches, we apply a primal-dual method that uses the perturbed optimality equations for SDP, $F_\mu(X,y,Z)=0$, where $X,Z$ are $n \times n$ symmetric matrices and $y \in \Re^n$. However, we look at this as an overdetermined system of … Read more

The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. … Read more