# Orbit-finite linear programming

arXiv: https://arxiv.org/abs/2302.00802 · HTML: https://mlsanity.com/paper/2302.00802/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2023.

## Built on by (most cited first, 1 of 1)

- [Bi-reachability in Petri nets with data](https://mlsanity.com/paper/2405.16176/) (2024)

## Abstract (arXiv)

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.