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.
翻译：无限的一组是轨道-无限的,如果在原子基本结构的变异之前,它只有有限的许多要素。我们研究线性编程的概略化,在线性不平等的轨道 -- -- 线性系统可以表示限制。作为我们的主要贡献,我们提供一个决定程序,用以检查这样一个系统是否具有真正的解决方案,并计算一个线性目标函数在所设定的解决方案上的最低/最大值。我们还表明,在只考虑整数解决方案的情况下,这些问题是不可变的。因此,轨道 -- -- 线性编程是可变的,而轨道 -- -- 线性线性编程则不是。
相关内容
微信扫码咨询专知VIP会员