Generalised Integer Programming Based on Logically Defined Relations

Abstract Many combinatorial optimisation problems can be modelled as integer linear programs. We consider a class of generalised integer programs where the constraints are allowed to be taken from a broader set of relations (instead of just being linear inequalities). The set of allowed relations is defined using a many-valued logic and the resulting class of relations have provably strong modelling properties. We give sufficient conditions for when such problems are polynomial-time solvable and we prove that they are APX -hard otherwise.

Authors

• Peter Jonsson
• Gustav Nordh

Keywords

No keywords are indexed for this paper.