Hybrid benders decomposition algorithms in constraint logic programming

Andre Eremin, Mark Wallace

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

27 Citations (Scopus)


Benders Decomposition is a form of hybridisation that allows linear programming to be combined with other kinds of algorithms. It extracts new constraints for one subproblem from the dual values of the other subproblem. This paper describes an implementation of Benders Decomposition, in the ECLiPSe language, that enables it to be used within a constraint programming framework. The programmer is spared from having to write down the dual form of any subproblem, because it is derived by the system. Examples are used to show how problem constraints can be modelled in an undecomposed form. The programmer need only specify which variables belong to which subproblems, and the Benders Decomposition is extracted automatically. A class of minimal perturbation problems is used to illustrate how different kinds of algorithms can be used for the different subproblems. The implementation is tested on a set of minimal perturbation benchmarks, and the results are analysed.
Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming – CP 2001
Subtitle of host publication7th International Conference, CP 2001 Paphos, Cyprus, November 26 – December 1, 2001 Proceedings
EditorsToby Walsh
Place of PublicationBerlin Germany
Number of pages15
ISBN (Print)3540428631
Publication statusPublished - 2001
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2001 - Paphos, Cyprus
Duration: 26 Nov 20011 Dec 2001
Conference number: 7th

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceInternational Conference on Principles and Practice of Constraint Programming 2001
Abbreviated titleCP 2001

Cite this