de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Linear 0-1 inequalities and extended clauses

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44073

Barth,  Peter
Programming Logics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-94-216.pdf
(beliebiger Volltext), 283KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Barth, P.(1994). Linear 0-1 inequalities and extended clauses (MPI-I-94-216). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B557-7
Zusammenfassung
Extended clauses are the basic formulas of the 0-1 constraint solver for the constraint logic programming language CLP(PB). We present a method for transforming an arbitrary linear 0-1 inequality into a set of extended clauses, such that the solution space remains invariant. After applying well-known linearization techniques on non-linear 0-1 constraints followed by the presented transformation method, we are able to handle arbitrary 0-1 constraints in CLP(PB). The transformation method presented relies on cutting planes techniques known from 0-1 integer programming. We develop specialized redundancy criteria and so produce the minimal number of extended clauses needed for preserving equivalence. The method is enhanced by using a compact representation of linear 0-1 inequalities and extended clauses. Unit resolution for classical clauses is generalized to pseudo-Boolean unit resolution for arbitrary linear 0-1 inequalities. We extend the transformation method to constrained transformation when the inequality to be transformed is part of a larger set of linear 0-1 inequalities. Furthermore the method can be used to obtain all strongest extended cover inequalities of a knapsack inequality.