Report
OA Policy
English

ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems

Collection
  • Cahiers de recherche; 2005.07
Publication date2005
Abstract

This paper proposes an implementation of a constrained analytic center cutting plane method to solve nonlinear multicommodity flow problems. The new approach exploits the property that the objective of the Lagrangian dual problem has a smooth component with second order derivatives readily available in closed form. The cutting planes issued from the nonsmooth component and the epigraph set of the smooth component form a localization set that is endowed with a self-concordant augmented barrier. Our implementation uses an approximate analytic center associated with that barrier to query the oracle of the nonsmooth component. The paper also proposes an approximation scheme for the original objective. An active set strategy can be applied to the transfomed problem: it reduces the dimension of the dual space and accelerates computations. The new approach solves huge instances with high accuracy. The method is compared to alternative approaches proposed in the literature.

Keywords
  • Constrained ACCPM
  • Approximation scheme
  • Active set strategy
Citation (ISO format)
BABONNEAU, Frédéric, VIAL, Jean-Philippe. ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems. 2005
Main files (1)
Report
accessLevelPublic
Identifiers
  • PID : unige:5757
584views
723downloads

Technical informations

Creation15/04/2010 12:19:48
First validation15/04/2010 12:19:48
Update14/03/2023 15:26:27
Status update14/03/2023 15:26:27
Last indexation29/10/2024 14:22:17
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack