History

Please fill in your query. A complete syntax description you will find on the General Help page.
On interior-point warmstarts for linear and combinatorial optimization. (English)
SIAM J. Optim. 20, No. 4, 1828-1861 (2010).
The paper is concerned with dual linear programming problems $\min \{ c^T x: Ax=b, x \geq 0\}$ and $\max \{ b^T y: A^T y+z=c, z\geq 0 \}$ with problem data $(A,b,c) \in \Bbb R^{m \times n} \times \Bbb R^m \times \Bbb R^n$ and decision variables $(x,y,z) \in \Bbb R^n \times \Bbb R^m \times \Bbb R^n$. In practice, it often occurs that a good estimate or approximate solution to the program under consideration is available. The authors present an infeasible-interior-point approach to quickly reoptimize an initial problem instance after data perturbations, or a linear programming relaxation after adding cutting planes for discrete or combinatorial problems. Based on the detailed complexity analysis of the underlying algorithm, the authors 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 and successive linear programming relaxations of max-cut and the traveling salesman problem.
Reviewer: Mikhail Yu. Kokurin (Yoshkar-Ola)