We develop an iterative algorithm based on right-hand side decomposition for the solution of multicommodity network flow problems. At each step of the proposed iterative procedure the coupling constraints are eliminated by subdividing the shared capacity resource among the different commodities and a master problem is constructed which attempts to improve sharing of resources at each iteration. As the objective function of the master problem is nonsmooth, we apply to it a new optimization technique wich does not require the exact solutions of the single commodity flow subproblems. This technique is based on the notion of epsilon-subgradients instead of subgradients and is suitable for parallel implementation. Extensions to the nonlinear, convex separable case are also discussed.

Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems

GAUDIOSO, Manlio;MONACO, Maria Flavia
1993

Abstract

We develop an iterative algorithm based on right-hand side decomposition for the solution of multicommodity network flow problems. At each step of the proposed iterative procedure the coupling constraints are eliminated by subdividing the shared capacity resource among the different commodities and a master problem is constructed which attempts to improve sharing of resources at each iteration. As the objective function of the master problem is nonsmooth, we apply to it a new optimization technique wich does not require the exact solutions of the single commodity flow subproblems. This technique is based on the notion of epsilon-subgradients instead of subgradients and is suitable for parallel implementation. Extensions to the nonlinear, convex separable case are also discussed.
Nonsmooth optimization; Parallel decomposition; Multicommodity network flow problems
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/147733
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact