uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Integration of Constraint Programming and Integer Programming for Combinatorial Optimization
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
2000 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The last several years have seen an increasing interest in combining the models and methods of optimization with those of constraint programming. Integration of the two was initially impeded by their different cultural origins, one having developed largely in the operations research community and the other in the computer science and artificial intelligence communities. The advantages of merger, however, are rapidly overcomingthis barrier.

The main objective for an integration of Constraint Programming over finite domains (CP) and Integer Programming (IP) is to take advantage of both the inference through constraint propagation and the (continuous) relaxations through Linear Programming (LP), in order to reduce the search needed to find feasible, good and optimal solutions.

The key decisions to be made for integrating CP and IP are (a) the model(s), (b) the inference, (c) the relaxations, and, (d) the search and branching strategies to use. In this thesis it is advocated to model specifically for a hybrid solver, having part of the model operated on by CP inference and part of the model constituting an LP relaxation. We propose mixed (global) constraints spanning both discrete and continuous variables to bridge the gap between CP and LP, providing inference as well as information for search strategies. Inference comes as cutting planes and domains reductions for LPand CP respectively. Branching is done in the CP part, utilizing information from the LP relaxation.

Apart from a general framework for integration, specific constraints and structures studied include several variations of variable subscripts and piecewise linear functions. Computational experiments show the benefit and potential of a hybrid scheme, illustrated on production planning and configuration problems.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis , 2000. , iv, 143 p.
Uppsala theses in computing science, ISSN 0283-359X ; 33
National Category
Computer Science
Research subject
Computing Science
URN: urn:nbn:se:uu:diva-821ISBN: 91-506-1396-0OAI: oai:DiVA.org:uu-821DiVA: diva2:170701
Public defence
2000-03-31, Room 1211, Polacksbacken, Uppsala University, Uppsala, 14:00 (English)
Available from: 1999-03-10 Created: 1999-03-10 Last updated: 2011-02-17Bibliographically approved

Open Access in DiVA

No full text

By organisation
Division of Computing ScienceComputing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 531 hits
ReferencesLink to record
Permanent link

Direct link