2013 | OriginalPaper | Buchkapitel
ILP Modulo Theories
verfasst von : Panagiotis Manolios, Vasilis Papavasileiou
Erschienen in: Computer Aided Verification
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present Integer Linear Programming (ILP) Modulo Theories (IMT). An IMT instance is an Integer Linear Programming instance, where some symbols have interpretations in background theories. In previous work, the IMT approach has been applied to industrial synthesis and design problems with real-time constraints arising in the development of the Boeing 787. Many other problems ranging from operations research to software verification routinely involve linear constraints and optimization. Thus, a general ILP Modulo Theories framework has the potential to be widely applicable. The logical next step in the development of IMT and the main goal of this paper is to provide theoretical underpinnings. This is accomplished by means of BC(
T
), the Branch and Cut Modulo
T
abstract transition system. We show that BC(
T
) provides a sound and complete optimization procedure for the ILP Modulo
T
problem, as long as
T
is a decidable, stably-infinite theory. We compare a prototype of BC(
T
) against leading SMT solvers.