Combinando o método de Pontos Interiores com o método Simplex para a solução de problemas de programação linear

Cecilia Orellana Castro, Manolo Rodriguez Heredia, Aurelio R. L. Oliveira

Resumo


Quando a matriz A de restrições de um problema de programação linear apresenta posto completo, no método Simplex é usada uma submatriznão singular de A para determinar uma solução básica. Neste contexto, no método de Pontos Interiores, quando são usados métodos iterativos precondicionados, também usa-se uma submatriz não singular de A para calcular o precondicionador Separador. O processo que calcula uma solução
básica factível para o método Simplex, a partir de um ponto do método de Pontos Interiores é chamado crossover. Neste trabalho combinam-se ambos os métodos para a solução de problemas de programação linear canalizados, mais precisamente usa-se uma base do precondicionador Separador para determinar se a solução básica associada a ela é factível primai, dual ou infactível no sentido do método Simplex. Resultados numéricos mostram que alguns problemas que não eram resolvidos usando apenas o método de Pontos Interiores, são resolvidos usando a estratégia do crossover. Também observam-se problemas que reduzem consideravelmente o número de iterações do método Simplex quando inicialmente usam o método de Pontos Interiores, isto é, combinam ambos os métodos.


Texto completo:

PDF

Referências


L. Casacio, C. Lyra, A. R. L. Oliveira e C. O. Castro. Improving the preconditioningof linear systems from interior point methods,Computers & Operations Research.85:129-138, 2017.

M. R. Heredia, C. O. Castro e A. R. L. Oliveira. A New Hybrid Precon-ditioner for the Interior Point Method,TEMA, 20:359-379, 2019. DOI:10.5540/tema.2019.020.02.0359.

M.R. Heredia e A.R.L. Oliveira, A new proposal to improve the early iterations inthe interior point method. Ann Oper Res 287, 185–208, 2020. DOI; 10.1007/s10479-019-03254-7

F. S. Hillier e G. J. Lieberman.Introdu ̧c ̃ao `a Pesquisa Operacional, McGraw HillBrasil, 2013.

R. Monteiro, J. O’Neal e T. Tsuchiya, Uniform Boundedness of a Normal MatrixUsed in Interior-Point Methods.SIAM Journal on Optimization, 15: 96-100, 2004.DOI: 10.1137/S1052623403426398

A. R. L. Oliveira e D. C. Sorensen, A New Class of Preconditioners for Large-ScaleLinear Systems from Interior Point Methods for Linear Programming.Linear Algebraand Its Applications, 394:1-24, 2005

R. Saigal.Linear Programming: A Modern Integrated Analysis. International Seriesin Operations Research & Management Science, Springer US, 2012

L. Schork e J. Gondzio. Implementation of an interior point method with basis pre-conditioning. Mathematical Programming Computation. 2020. DOI:10.1007/s12532-020-00181-8.

M. I. Velazco e A. R. L. Oliveira. Computing the Splitting Preconditioner for Inte-rior Point Method Using an Incomplete Factorization Approach.Operations ResearchProceedings 2017. Springer International Publishing, pages 97-103, 2018.




DOI: https://doi.org/10.5540/03.2021.008.01.0384

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato