Polynomial Reduction from PESP to SAT

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Toggle side column

Polynomial Reduction from PESP to SAT

Studienarbeit von Peter Großmann
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.