12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Integer quadratic quasi-polyhedra
View graph of relations

« Back

Integer quadratic quasi-polyhedra

Research output: Contribution in Book/Report/ProceedingsChapter (peer-reviewed)

Published

Publication date2010
Host publicationInteger Programming and Combinatorial Optimization: Proceedings of the 14th International IPCO Conference
EditorsFriedrich Eisenbrand, F. Bruce Shepherd
Place of publicationBerlin
PublisherSpringer
Pages258-270
Number of pages13
Original languageEnglish

Conference

Conference14th International Conference, IPCO 2010
CountrySwitzerland
CityLausanne
Period9/06/1011/06/10

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6080

Conference

Conference14th International Conference, IPCO 2010
CountrySwitzerland
CityLausanne
Period9/06/1011/06/10

Abstract

This paper introduces two fundamental families of `quasi-polyhedra' (polyhedra with a countably infinite number of facets) that arise in the context of integer quadratic programming. It is shown that any integer quadratic program can be reduced to the minimisation of a linear function over a quasi-polyhedron in the first family. Some fundamental properties of the quasi-polyhedra are derived, along with connections to some other well-studied convex sets. Several classes of facet-inducing inequalities are also derived. Finally, extensions to the mixed-integer case are briefly examined.