Column Generation Algorithms for Nonlinear Optimization II: Numerical Investigations

García Ródenas, Ricardo; Marín Gracia, Angel y Patriksson, Michael (2011). Column Generation Algorithms for Nonlinear Optimization II: Numerical Investigations. "Computer and Operation Research", v. 38 (n. 3); pp. 591-604. ISSN 0305-0548. https://doi.org/10.1016/j.cor.2010.07.021.

Descripción

Título: Column Generation Algorithms for Nonlinear Optimization II: Numerical Investigations
Autor/es:
  • García Ródenas, Ricardo
  • Marín Gracia, Angel
  • Patriksson, Michael
Tipo de Documento: Artículo
Título de Revista/Publicación: Computer and Operation Research
Fecha: Marzo 2011
Volumen: 38
Materias:
Palabras Clave Informales: Simplicial decomposition, Nonlinear column generation, Convex minimization, Network flow problems
Escuela: E.T.S.I. Aeronáuticos (UPM) [antigua denominación]
Departamento: Matemática Aplicada y Estadística [hasta 2014]
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

Resumen

García et al. present a class of column generation (CG) algorithms for nonlinear programs. Its main motivation from a theoretical viewpoint is that under some circumstances, finite convergence can be achieved, in much the same way as for the classic simplicial decomposition method; the main practical motivation is that within the class there are certain nonlinear column generation problems that can accelerate the convergence of a solution approach which generates a sequence of feasible points. This algorithm can, for example, accelerate simplicial decomposition schemes by making the subproblems nonlinear. This paper complements the theoretical study on the asymptotic and finite convergence of these methods given in [1] with an experimental study focused on their computational efficiency. Three types of numerical experiments are conducted. The first group of test problems has been designed to study the parameters involved in these methods. The second group has been designed to investigate the role and the computation of the prolongation of the generated columns to the relative boundary. The last one has been designed to carry out a more complete investigation of the difference in computational efficiency between linear and nonlinear column generation approaches. In order to carry out this investigation, we consider two types of test problems: the first one is the nonlinear, capacitated single-commodity network flow problem of which several large-scale instances with varied degrees of nonlinearity and total capacity are constructed and investigated, and the second one is a combined traffic assignment model

Más información

ID de Registro: 15270
Identificador DC: http://oa.upm.es/15270/
Identificador OAI: oai:oa.upm.es:15270
Identificador DOI: 10.1016/j.cor.2010.07.021
Depositado por: Memoria Investigacion
Depositado el: 05 Jun 2014 18:33
Ultima Modificación: 21 Abr 2016 15:19
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM