Orbit-finite linear programming
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910695989182464 |
|---|---|
| author | Ghosh, Arka Hofman, Piotr Lasota, Sławomir |
| author_facet | Ghosh, Arka Hofman, Piotr Lasota, Sławomir |
| contents | An infinite set is orbit-finite if, up to permutations of the underlying structure of atoms, it has only finitely many elements. We study a generalisation of linear programming where constraints are expressed by an orbit-finite system of linear inequalities. As our principal contribution we provide a decision procedure for checking if such a system has a real solution, and for computing the minimal/maximal value of a linear objective function over the solution set. We also show undecidability of these problems in case when only integer solutions are considered. Therefore orbit-finite linear programming is decidable, while orbit-finite integer linear programming is not. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_00802 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Orbit-finite linear programming Ghosh, Arka Hofman, Piotr Lasota, Sławomir Logic in Computer Science Formal Languages and Automata Theory F.1.1; F.4.1; F.4.3 An infinite set is orbit-finite if, up to permutations of the underlying structure of atoms, it has only finitely many elements. We study a generalisation of linear programming where constraints are expressed by an orbit-finite system of linear inequalities. As our principal contribution we provide a decision procedure for checking if such a system has a real solution, and for computing the minimal/maximal value of a linear objective function over the solution set. We also show undecidability of these problems in case when only integer solutions are considered. Therefore orbit-finite linear programming is decidable, while orbit-finite integer linear programming is not. |
| title | Orbit-finite linear programming |
| topic | Logic in Computer Science Formal Languages and Automata Theory F.1.1; F.4.1; F.4.3 |
| url | https://arxiv.org/abs/2302.00802 |