Study and implementation of variants of the primal-dual simplex method

• Grant number: 17/12579-4
• Support Opportunities: Scholarships abroad - Research Internship - Scientific Initiation
• Start date: October 01, 2017
• End date: December 31, 2017
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Pedro Augusto Munari Junior
• Grantee: Carlos Guedes Filho
• Supervisor: Jacek Gondzio
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
• Institution abroad: University of Edinburgh, Scotland
• Associated to the scholarship: 15/23110-1 - Primal-dual methods for solving optimization problems applied to industrial an logistic contexts, BP.IC

Abstract

Linear programming is the dominant paradigm in optimization. It offers powerful solution algorithms capable of solving very large-scale problems with high reliability and within reasonable computational time. The two most important methods for solving linear programming problems are the simplex method and the interior point method. For the latter, the primal-dual variants have shown clear advantage in practice, as they achieve a better control of the progress of the algorithm by relying on solutions of the primal and dual problems simultaneously. Primal-dual variants of the simplex method have been much less exploited in the literature and they typically rely on a different perspective. In this project, we propose a primal-dual simplex algorithm that similarly to primal-dual interior point methods gathers information from primal and dual solutions at each iteration of the algorithm. We address other variants of the primal-dual simplex method and compare their algorithms and practical performance against the proposed method. In the computational experiments, we rely on benchmark instances from the public repository Netlib. The comparisons are likely to highlight advantages and disadvantages of each primal-dual method and show their potential benefits for solving different classes of linear programming problems. This research project will be supervised by Professor Jacek Gondzio at the University of Edinburgh, in Scotland - United Kingdom. (AU)