Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-94-216

Linear 0-1 inequalities and extended clauses

Barth, Peter

MPI-I-94-216. April 1994, 53 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
Categories / Keywords: constraint logic programming, pseudo-Boolean constraints, 0-1 integer programming, extended clauses, extended cover inequalities
Computing Reviews Classification: D.1.6 Software - Programming Techniques - Logic Programming
F.4.1 Theory of Computation - Mathematical Logic And Formal Languages - Mathematical Logic - Logic programming
G.1.6 Mathematics of Computing - Numerical Analysis - Optimization - Integer programming
I.2.3 Computing Methodologies - Artificial Intelligence - Deduction and Theorem Proving - Logic programming
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-94-216.pdfMPI-I-94-216.pdfMPI-I-94-216.dvi - MPI-I-94-216.dvi
246 KBytes; 282 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-216
Hide details for BibTeXBibTeX
@TECHREPORT{Barth-94-mpii216,
  AUTHOR = {Barth, Peter},
  TITLE = {Linear 0-1 inequalities and extended clauses},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-216},
  MONTH = {April},
  YEAR = {1994},
  ISSN = {0946-011X},
}