Generalised integer programming based on logically defined relations
2006 (English)In: Mathematical Foundations of Computer Science 2006: 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006. Proceedings / [ed] Rastislav Královic and Pawel Urzyczyn, Springer Berlin/Heidelberg, 2006, Vol. 4162, 549-560 p.Chapter in book (Refereed)
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.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2006. Vol. 4162, 549-560 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 4162
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-48071DOI: 10.1007/11821069_48ISBN: 3-540-37791-3ISBN: 978-3-540-37791-7ISBN: 978-3-540-37793-1OAI: oai:DiVA.org:liu-48071DiVA: diva2:268967