Dimensioning multicast-enabled communications networks
Networks 39 (2002), 216-231. CitationNetworks 39 (2002), 216-231.
Feasible Interior Methods Using Slacks for Nonlinear Optimization
A slack-based feasible interior point method is described which can be derived as a modification of infeasible methods. The modification is minor for most line search methods, but trust region methods require special attention. It is shown how the Cauchy point, which is often computed in trust region methods, must be modified so that the … Read more
Strengthened Semidefinite Relaxations via a Second Lifting for the Max-Cut Problem
In this paper we study two strengthened semidefinite programming relaxations for the Max-Cut problem. Our results hold for every instance of Max-Cut; in particular, we make no assumptions about the edge weights. We prove that the first relaxation provides a strengthening of the Goemans-Williamson relaxation. The second relaxation is a further tightening of the first … Read more
A practical general approximation criterion for methods of multipliers based on Bregman distances
This paper demonstrates that for generalized methods of multipliers for convex programming based on Bregman distance kernels — including the classical quadratic method of multipliers — the minimization of the augmented Lagrangian can be truncated using a simple, generally implementable stopping criterion based only on the norms of the primal iterate and the gradient (or … Read more
On the min-cut max-flow ratio for multicommodity flows
In this paper we present a new bound on the min-cut max-flow ratio for multicommodity flow problems. We use a so-called aggregated commodity formulation and an optimal solution to its dual to show our main result. Currently, the best known bound for this ratio is proportional to log(k) where k is the number of origin-destination … Read more
Near-optimal solutions to large scale facility location problems
We investigate the solution of large scale instances of the capacitated and uncapacitated facility location problems. Let n be the number of customers and m the number of potential facility sites. For the uncapacitated case we solved instances of size m x n=3000 x 3000; for the capacitated case the largest instances were 1000 x … Read more
A Multi-stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty
This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation … Read more
WASP: a Wavelet Adaptive Solver for boundary value Problems – Short Reference Manual
This is a short guide to use the Matlab package WASP designed for the numerical solution of two-point linear boundary value problems that arise typically in linear quadratic optimal control. The method relies upon an adaptive computation of discretization based on a wavelet analysis. On a given refined grid, finite differences of various order are … Read more
A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach
This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of … Read more
Solving Steiner tree problems in graphs with Lagrangian relaxation
This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lowe r bounds and to estimate primal solutions. Due … Read more