On interior-point warmstarts for linear and combinatorial optimization

Alexander Engau, Miguel F. Anjos, Anthony Vannelli

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

17 Citas (Scopus)

Resumen

Despite the many advantages of interior-point algorithms over active-set methods for linear optimization, one of the remaining practical challenges is their current limitation to efficiently solve series of related problems by an effective warmstarting strategy. As a remedy, in this paper we present a new infeasible-interior-point approach to quickly reoptimize an initial problem instance after data perturbations, or a new linear programming relaxation after adding cutting planes for discrete or combinatorial problems. Based on the detailed complexity analysis of the underlying algorithm, we perform a comparative analysis to coldstart initialization schemes and present encouraging computational results with iteration savings of around 50% on average for perturbations of the Netlib linear programs (LPs) and successive linear programming relaxations of max-cut and the traveling salesman problem.

Idioma originalEnglish
Páginas (desde-hasta)1828-1861
Número de páginas34
PublicaciónSIAM Journal on Optimization
Volumen20
N.º4
DOI
EstadoPublished - 2010
Publicado de forma externa

ASJC Scopus Subject Areas

  • Software
  • Theoretical Computer Science

Huella

Profundice en los temas de investigación de 'On interior-point warmstarts for linear and combinatorial optimization'. En conjunto forman una huella única.

Citar esto

Engau, A., Anjos, M. F., & Vannelli, A. (2010). On interior-point warmstarts for linear and combinatorial optimization. SIAM Journal on Optimization, 20(4), 1828-1861. https://doi.org/10.1137/080742786