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 original | English |
---|---|
Páginas (desde-hasta) | 1828-1861 |
Número de páginas | 34 |
Publicación | SIAM Journal on Optimization |
Volumen | 20 |
N.º | 4 |
DOI | |
Estado | Published - 2010 |
Publicado de forma externa | Sí |
ASJC Scopus Subject Areas
- Software
- Theoretical Computer Science