Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2604.06726 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914533192237056 |
|---|---|
| author | Truffet, Laurent |
| author_facet | Truffet, Laurent |
| contents | In this paper we develop a very special substitution method for solving
a general linear programming problem (LPP). Of course the substitution is a kind of elimination
of variable but this method must not be confused
with the so-called Fourier-Motzkin elimination. The susbtitution developed in this
paper only differs by the set of criteria that a variable must verify to be
substitued. Most of the criteria are associated with the cost function of the
LPP. We prove that the research of the criteria is strongly polynomial.
Thus, the special substitution inehrits of the strong polynomiality which characterizes
the classical substitution for linear systems. Moreover, as for the classical substitution the
backward substitution for finding a vertex associated with the optimum is still valid and
does not require to inverse a matrix. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06726 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Linear Programming Problem Solved By a Special Substitution Method Truffet, Laurent Optimization and Control 90C05, 03D15 In this paper we develop a very special substitution method for solving a general linear programming problem (LPP). Of course the substitution is a kind of elimination of variable but this method must not be confused with the so-called Fourier-Motzkin elimination. The susbtitution developed in this paper only differs by the set of criteria that a variable must verify to be substitued. Most of the criteria are associated with the cost function of the LPP. We prove that the research of the criteria is strongly polynomial. Thus, the special substitution inehrits of the strong polynomiality which characterizes the classical substitution for linear systems. Moreover, as for the classical substitution the backward substitution for finding a vertex associated with the optimum is still valid and does not require to inverse a matrix. |
| title | Linear Programming Problem Solved By a Special Substitution Method |
| topic | Optimization and Control 90C05, 03D15 |
| url | https://arxiv.org/abs/2604.06726 |