Enhancing the performance of constraint programming through the introduction of linear programming

J Little
Additional contact information
J Little: Brunel University

Journal of the Operational Research Society, 2001, vol. 52, issue 1, 82-92

Abstract: Abstract Constraint Programming (CP) has been successful in a number of combinatorial search and discrete optimisation problems. Yet other more traditional approaches, such as Integer Programming (IP), can still give a better performance on the same problem types. Central to IP's success is its reliance on a fast Linear Programming (LP) solver providing solutions during the search to the corresponding relaxed problems. These solutions are used to guide the search within IP as well as a means of detecting infeasibility and integrality. This paper shows that there is scope also to include LP within the CP framework, in order to similarly guide the CP search. The problems examined here are one for which CP on its own had proved markedly inferior to IP. Hence a hybrid solver based on the CP search and using an LP solver is configured and run on these problems. The outcome shows that using the LP solver within the CP search is a valuable addition to the available search strategies. An improved performance over the CP-only strategies is obtained and, further, comparable results are obtained to those from IP. Overall, CP+LP can be considered as a more robust approach than either CP or IP on their own on a variety of combinatorial search problems.

Keywords: integer programming; linear programming; constraint programming (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601047 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:52:y:2001:i:1:d:10.1057_palgrave.jors.2601047

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601047

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().