A Greedy Randomized Adaptive Search Procedure (GRASP) is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and local search. Path-relinking is an intensification strategy that explores trajectories that connect high quality solutions. We analyze two parallel strategies for GRASP with path-relinking and propose a criterion … Read more
This work introduces a distributed branch-and-bound algorithm to be run on computational Grids. Grids are often organized in a hierarchical fashion: clusters of processors connected via high-speed links, while the clusters themselves are geographically distant and connected through slower links. Our algorithm does not employ the usual master-worker paradigm and it considers the hierarchical structure … Read more
The nearest \cm\ problem is to find a positive semidefinite matrix with unit diagonal that is nearest in the Frobenius norm to a given symmetric matrix $A$. This problem can be formulated as an optimization problem with a quadratic objective function and semidefinite programming constraints. Using such a formulation, we derive and test a primal-dual … Read more
Issues of implementation of a library for parallel interior-point methods for quadratic programming are addressed. The solver can easily exploit any special structure of the underlying optimization problem. In particular, it allows a nested embedding of structures and by this means very complicated real-life optimization problems can be modeled. The efficiency of the solver is … Read more
In this paper, we describe a methodology for the analysis of greedy randomized adaptive search procedures (GRASP). GRASP is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and a local search. Hybrid approaches of GRASP with path-relinking developed for the 3-index assignment problem (AP3) and … Read more
As part of Performance World, we describe an automation server (PAVER: http://www.gamsworld.org/performance/paver) to help facilitate reproducible performance analysis of benchmarking data for optimization software. Although PAVER does not solve optimization problems, it automates the task of performance data analysis and visualization, taking into account various performance metrics. These include not only robustness and efficiency, but … Read more
In the paper it is shown how to utilize the flexibility in native Java arrays for matrix computations. Suitable datastructures for symmetric and sparse matrices are introduced. A disadvantage of the native Java arrays is shown when used as two-dimensional array for dense matrix computation. Numerical results show that the efficiency is not lost using … Read more
The Watson Sparse Matrix Package (WSMP) is a high-performance robust direct solver for both symmetric and unsymmetric large sparse systems of linear equations. Currently, it works in serial, multi-threaded parallel, message-passing parallel, and a combination of message-passing and multi-threaded modes on IBM RS6000 with AIX and IA32 with Linux. The symmetric solver has features to … Read more
RIOTS_95 is a group of programs and utilities, written mostly in C, Fortran and M-file scripts and designed as a toolbox for MATLAB, that provides an interactive environment for solving a very broad class of optimal control problems (OCP’s). RIOTS_95 comes pre-compiled for use with the Windows 95/98/2000 or Windows NT operating systems. The user’s … Read more
This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained … Read more