Improving the efficiency of the predictor-corrector interior point method

• Grant number: 15/02184-7
• Support Opportunities: Regular Research Grants
• Start date: June 01, 2015
• End date: May 31, 2017
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Carla Taviane Lucke da Silva Ghidini
• Grantee: Carla Taviane Lucke da Silva Ghidini
• Host Institution: Faculdade de Ciências Aplicadas (FCA). Universidade Estadual de Campinas (UNICAMP). Limeira , SP, Brazil

Abstract

The interior point methods have been extensively studied and used to solve large linear programming problems in recent decades. Among all its variations, the Predictor-Corrector method is more prominet due to its efficiency and fast convergence. In this method, two linear systems are solved in each iteration to determine the direction of search, called predictor-corrector direction. Solving these linear systems corresponds to the step that requires more processing time and therefore should be solved efficiently. The main objectives of this project are to improve the performance of the Predictor-Corrector method, reducing the computational time and/or the total number of iterations and also to solve linear programming problems, which have not been resolved by other approaches. Therefore, it is essential to optimize the time resolution of linear systems and increase the robustness of the method. For this, some techniques will be studied, developed and refined such as elimination of redundant lines, continuous iterations, optimal adjustment algorithm, alternative iterative methods for solving linear systems, hybrid approach of preconditioning linear systems. All implementations will be incorporated into PCx software, which is an implementation of Predictor-Corrector interior point method with multiple corrections. The code PCx is open and was developed in the Optimization Technology Center at Argonne National Laboratory and Northwestern University. Most of his routines are implemented in the C language. Computational experiments will be made using several linear programming problems in free access on the internet from different collections. (AU)

Scientific publications

(4)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

CAMPELLO, B. S. C.; GHIDINI, C. T. L. S.; AYRES, A. O. C.; OLIVEIRA, W. A.. A residual recombination heuristic for one-dimensional cutting stock problems. Top, JUN 2021. (15/02184-7)

CAMPELLO, B. S. C.; GHIDINI, C. T. L. S.; AYRES, A. O. C.; OLIVEIRA, W. A.. A multiobjective integrated model for lot sizing and cutting stock problems. Journal of the Operational Research Society, v. 71, n. 9, JUN 2019. (15/02184-7)

CAMPELLO, B. S. C.; GHIDINI, C. T. L. S.; AYRES, A. O. C.; OLIVEIRA, W. A.. A residual recombination heuristic for one-dimensional cutting stock problems. Top, v. 30, n. 1, p. 27-pg., 2021-06-14. (15/02184-7)

AYRES, AMANDA O. C.; CAMPELLO, BETANIA S. C.; OLIVEIRA, WASHINGTON A.; GHIDINI, CARLA T. L. S.. A Bi-Integrated Model for coupling lot-sizing and cutting-stock problems. OR SPECTRUM, JUL 2021. (15/02184-7)