de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Towards Conflict-driven Learning for Virtual Substitution

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons127668

Košta,  Marek
Automation of Logic, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons73108

Sturm,  Thomas
Automation of Logic, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Korovin, K., Košta, M., & Sturm, T. (2014). Towards Conflict-driven Learning for Virtual Substitution. In V. P. Gerdt, W. Koepf, W. M. Seiler, & E. V. Vorozhtsov (Eds.), Computer Algebra in Scientific Computing (pp. 256-270). Berlin: Springer. doi:10.1007/978-3-319-10515-4_19.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-5369-6
Abstract
We consider satisfiability modulo theory-solving for linear real arithmetic. Inspired by related work for the Fourier–Motzkin method, we combine virtual substitution with learning strategies. For the first time, we present virtual substitution—including our learning strategies—as a formal calculus. We prove soundness and completeness for that calculus. Some standard linear programming benchmarks computed with an experimental implementation of our calculus show that the integration of learning techniques into virtual substitution gives rise to considerable speedups. Our implementation is open-source and freely available.