DOTTORATO DI RICERCA IN INFORMATICA

Università di Pisa-Genova-Udine

Ph.D. Thesis - TD 5/97

Dual-Ascent Methods and Multicommodity Flow Problems

Antonio Frangioni

Abstract. Lagrangean Duality provides an attractive way for exploiting the "easy part" of structured problems with "complicating" constraints: however, it calls for the (approximate) solution of large-scale, difficult NonDifferentiable Optimization problems. In the first part of the thesis, we study the theoretical and practical issues arising in the application of Bundle methods to the solution of Lagrangean Duals, showing how these methods are related with other approaches and giving some new contributions, such as: a new convergence proof where, rather than proving the correctness of any single implementation, we give general convergence conditions; a new algorithm for the solution of the Quadratic Programming (tentative ascent direction finding) subproblem that is solved at each step, whose effectiveness is demonstrated by a computational study; a new class of Bundle algorithms using (LP) subproblems; the extension to this new class of the convergence proof and the treatment of constrained and/or "separable" maximization; two new "Long Term" rules for on-line management of the trust region parameter, that seem to avoid the "stalling" on difficult problems. In the second part of the thesis, these methods are used for the solution of Multicommodity Flow problems: a (QP)-based Bundle code is tested against several other codes and on many classes of problems, proving to be competitive especially on instances with "many" commodities; the code is then parallelized, obtaining good efficiencies on the classes of instances where it is more effective in sequential. However, three other new Dual-Ascent approaches are also proposed for the problem, and preliminary computational reults are reported for one of them; on the other side, codes based on the Bundle technology are shown to be competitive w.r.t. standard Subgradient algorithms for rapidly obtaining lower bounds for two network-structured, difficult integer problems.

March 1997


Contents

Each link corresponds to a .pdf file: there is a separate file for each chapter, but there are also two big files for all Part I and Part II of the thesis, that only need the initial and final small files to form the complete thesis. The files have been produced for a two-side print (on A4 paper), i.e., they will produce a few blank pages if printed one-side.