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.