Abstract
Extended clauses are the basic formulas of the 0–1 constraint solver used in 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. The method relies on cutting planes techniques known from integer programming. We develop special redundancy criteria and can so produce the minimal number of extended clauses. We show how the algorithm can be used to replace the resolution rule in the generalized resolution algorithm for extended clauses. Furthermore the method can be used to obtain all strongest extended cover inequalities of a knapsack inequality.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Balas and J. B. Mazzola. Nonlinear 0–1 programming: I. Linearization techniques. Mathematical Programming, 30:1–21, 1984.
P. Barth. A complete symbolic 0–1 constraint solver. In ACCLAIM Kick-Off Workshop, Stockholm, November 1992.
P. Barth and A. Bockmayr. Solving 0–1 problems in CLP(PB). In Proc. 9th Conf. Artificial Intelligence for Applications (CAIA), Orlando. IEEE, 1993.
A. Bockmayr. Logic programming with pseudo-Boolean constraints. In A. Colmerauer and F. Benhamou, editors, Constraint Logic Programming — Selected Research. MIT Press, 1992. (to appear).
H. Crowder, E.L. Johnson, and M. Padberg. Solving large-scale zero-one linear programming problems. Operations Research, 31(5):803–834, September 1983.
F. Granot and P. L. Hammer. On the use of boolean functions in 0–1 programming. Methods of Operations Research, 12:154–184, 1971.
P.L. Hammer and S. Rudeanu. Boolean Methods in Operations Research and Related Areas. Springer-Verlag, 1968.
J. N. Hooker. Generalized resolution for 0–1 linear inequalities. Annals of Mathematics and Artificial Intelligence, 6:271–286, 1992.
J. Jaffar and J.-L. Lassez. Constraint logic programming. In Proc. 14th ACM Symp. Principles of Programming Languages, Munich, 1987.
E.L. Johnson, M. Kostreva, and U.H. Suhl. Solving 0–1 integer programming problems arising from large scale planning models. Operations Research, 33(4):803–819, July 1985.
G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. Series in Discrete Mathematics and Optimization. Wiley-Interscience, 1988.
P. Van Hentenryck. Constraint satisfaction in logic programming. MIT Press, 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barth, P. (1993). Linear 0–1 inequalities and extended clauses. In: Voronkov, A. (eds) Logic Programming and Automated Reasoning. LPAR 1993. Lecture Notes in Computer Science, vol 698. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56944-8_40
Download citation
DOI: https://doi.org/10.1007/3-540-56944-8_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56944-2
Online ISBN: 978-3-540-47830-0
eBook Packages: Springer Book Archive