Abstract:

A classic branch and bound (B&B) method for mixed integer linear programming requires the solution of a series of problems which differ only in the bound constraint of a variable from a previously solved problem.  This feature can be easily exploited by the Simplex method.  Interior Point Methods (IPM) on the other hand, which are the methods of choice for certain linear programs, are not able to exploit this similarity between successive problems.

In this ongoing work we investigate methods for effective warm starting IPM from previous solutions when the problem changes by a single perturbation to the righthand side vector, which represents the changes of problems in a B&B method.  We propose a penalty approach to ensure feasibility of the modified problem.  In this talk I will review some basic principles of IPMs, introduce our penalization approach and its theoretical guarantees, describe the heuristic method this developed, and present preliminary computational results.

Fernando Ordoñez, Académico Depto. de Ingeniería Industrial Universidad de Chile y miembro del Instituto Sistemas Complejos de Ingeniería.

12:00 hrs.
Títuilo: "IPM warmstarts for single coefficient perturbation on the right hand side".
Expone: Fernando Ordoñez, Académico Depto de Ingeniería Industrial