Uma análise da utilização do método de eliminação de Fourier-Motzkin para encontrar um ponto interior a um poliedro

André Rodrigues Monticeli; Paulo César Mappa

doi:10.35819/remat2021v7i1id4305

Authors

André Rodrigues Monticeli Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil https://orcid.org/0000-0003-4049-5581
Paulo César Mappa Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil https://orcid.org/0000-0001-8192-8991

DOI:

https://doi.org/10.35819/remat2021v7i1id4305

Keywords:

Systems of Linear Inequalities, Polyhedron, Interior Point, Fourier-Motzkin Elimination

Abstract

The issue of finding an interior point to a polyhedron has applications in many areas, especially in linear programming. In this work we approach the issue of finding an interior point to a polyhedron using the Fourier-Motzkin Elimination Method approach. It consists of reducing a system of linear inequalities that defines the polyhedron, by eliminating variables. A matrix version of this method was employed in order to facilitate its computational implementation, and some examples were presented with the purpose of illustrating the proposed methodology. Subsequently the complexity analysis of the algorithm was carried out in order to investigate the behavior of the technique when increasing the number of variables and restrictions and, thus, presenting a field of application to the technique. By analyzing the algorithm, we concluded that it has exponential complexity, since the number of inequalities grows exponentially as the number of variables in the issue increases. The algorithm proved to be efficient for issue with a small number of inequalities for R² and R³.

Downloads

Download data is not yet available.

Author Biographies

André Rodrigues Monticeli, Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil

http://lattes.cnpq.br/0996675223199497
Paulo César Mappa, Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), Campus Varginha, Varginha, MG, Brasil

http://lattes.cnpq.br/0342332166757546

References

AJSPUR, Mai Lise; JENSEN, Rune Moller. Usubg Fourier-Motzkin-Elimination to Derive Capacity models of Container Vessels. IT University Thechnical Report Series, University of Copenhagen, Dinamarca, jan. 2017. Disponível em: https://en.itu.dk/research/technical-reports/technical-reports-archive/2017/tr-2017-197. Acesso em: 9 dez. 2020.

BARVINOK, Alexander; POMMERSHEIM, James E. An Algorithmic Theory of Lattice Points in Polyhedra. New Perspectives in Geometric Combinatorics, MSRI Publications, v. 38, 1999. Disponível em: https://www.maths.ed.ac.uk/~v1ranick/papers/barvpomm.pdf. Acesso em: 9 dez. 2020.

CARTIS, Coralia; Gould, Nicholas I. M. Finding a point in the relative interior of a polyhedron,

with applications to compressed sensing. In: SPARTS'09 – SIGNAL PROCESSING WITH ADAPTIVE SPARSE STRUCTURED REPRESENTATIONS, Saint Malo France, 2009. Disponível em: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.703.298&rep=rep1&type=pdf. Acesso em: 9 dez. 2020.

CUI, Shulin; ZHANG, Shuqing; CHEN, Xuanxi; PANG, Zhenping; FU, Xiaoyang; XU, Zhang. Point-in-polyhedra test with direct handling of degeneracies. Geo-spatial Information Science, v. 14, n. 2, p. 91-97, 2011. DOI: https://doi.org/10.1007/s11806-011-0453-8.

DAHL, Geir. Combinatorial properties of Fourier-Motzkin elimination. The Electronical Jounal of linear Algebra, v. 16, p. 334-346, out. 2007. Disponível em: https://www.elibm.org/article/10010887. Acesso em: 9 dez. 2020.

DEMMEL, James W. Applied Numerical Linear Algebra. Philadelphia: Society of Industrial and Applied Mathematics, 1997. DOI: https://doi.org/10.1137/1.9781611971446.

FOURIER, Jean-Baptiste J. Ouvress II. Paris, 1890.

LAURITZEN, Niels. Lectures on convex sets. Department Of Mathematical Sciences, University of Aarhus, Denmark, mar. 2009. Disponível em: https://www.fmf.uni-lj.si/~lavric/lauritzen.pdf. Acesso em: set. 2020.

MONTICELI, André R. Um estudo sobre sistemas de inequações lineares. Orientador: Cristiano Torezzan. 2010. 118 p. Dissertação (Mestrado em Matemática) – Instituto de Matemática, Estatística e Computação Científica (IMECC), Universidade Estadual de Campinas, Campinas, SP, 2010. Disponível em: http://repositorio.unicamp.br/bitstream/REPOSIP/306906/1/Monticeli_AndreRodrigues_M.pdf. Acesso em: 9 dez. 2020.

MONTICELI, André R.; TOREZZAN, Cristiano. Método de Eliminação de Fourier-Motzkin. In: ENCONTRO REGIONAL DE MATEMÁTICA APLICADA E COMPUTACIONAL (ERMAC 2010), 1., São João del-Rei, MG, 11 a 13 nov. 2010. Anais [...]. Universidade Federal de São João del-Rei, p. 258-264, 2010. Disponível em: https://www.ufsj.edu.br/portal2-repositorio/File/i-ermac/anais/sessoes-tecnicas/st11.pdf. Acesso em: 9 dez. 2020.

MOTZKIN, T. S. Beiträge zur Theorie der linearen Ungleichungen. Thesis, 1936. Reprinted in: Theodore S. Motzkin: selected papers (D. Cantor et al.), Birkhäuser, Boston, 1983.