Polynomial Reduction from PESP to SAT
Aus International Center for Computational Logic
Polynomial Reduction from PESP to SAT
Studienarbeit von Peter Großmann
- Betreuer Peter Steinke
- Wissensverarbeitung
- 21. Oktober 2011 – 21. Oktober 2011
- Download
SAT solvers have been already successfully applied in several industrial fields, which are
not directly related to propositional logic. In this work, the periodic event scheduling problem (PESP) will be presented and, furthermore, the order encoding from a PESP instance to a SAT instance. The N P-complete PESP is particularly important in several traffic scenarios with periodic properties. Most native domain solvers cannot solve large instances within a given time frame. This will be omitted by a rather short time consuming conversion from PESP to SAT and a fast state-of-the-art SAT solver, in order to achieve a fast calculated solution of a PESP instance.
