Back to Search Start Over

ON INTERIOR-POINT WARMSTARTS FOR LINEAR AND COMBINATORIAL OPTIMIZATION.

Authors :
ENGAU, ALEXANDER
ANJOS, MIGUEL F.
VANNELLI, ANTHONY
Source :
SIAM Journal on Optimization; 2010, Vol. 20 Issue 4, p1828-1861, 34p, 6 Charts, 4 Graphs
Publication Year :
2010

Abstract

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
10526234
Volume :
20
Issue :
4
Database :
Complementary Index
Journal :
SIAM Journal on Optimization
Publication Type :
Academic Journal
Accession number :
51886621
Full Text :
https://doi.org/10.1137/080742786