Advanced search
Start date

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

Grant number: 17/12579-4
Support type:Scholarships abroad - Research Internship - Scientific Initiation
Effective date (Start): October 01, 2017
Effective date (End): December 31, 2017
Field of knowledge:Engineering - Production Engineering - Operational Research
Principal researcher:Pedro Augusto Munari Junior
Grantee:Carlos Guedes Filho
Supervisor abroad: Jacek Gondzio
Home Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
Research place: 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


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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list by writing to: