A new approach to integrating mixed integer programming and constraint logic programming

Robert Rodošek, Mark G. Wallace, Mozafar T. Hajian

Research output: Contribution to journalArticleResearchpeer-review

65 Citations (Scopus)

Abstract

This paper represents an integration of Mixed Integer Programming (MIP) and Constraint Logic Programming (CLP) which, like MIP, tightens bounds rather than adding constraints during search. The integrated system combines components of the CLP system ECLiPSe [7] and the MIP system CPLEX [5], in which constraints can be handled by either one or both components. Our approach is introduced in three stages. Firstly, we present an automatic transformation which maps CLP programs onto such CLP programs that any disjunction is eliminated in favour of auxiliary binary variables. Secondly, we present improvements of this mapping by using a committed choice operator and translations of pre-defined nonlinear constraints. Thirdly, we introduce a new hybrid algorithm which reduces the solution space of the problem progressively by calling finite domain propagation of ECLiPSe as well as dual simplex of CPLEX. The advantages of this integration are illustrated by efficiently solving difficult optimisation problems like the Hoist Scheduling Problem [23] and the Progressive Party Problem [27].

Original languageEnglish
Pages (from-to)63-87
Number of pages25
JournalAnnals of Operations Research
Volume86
Publication statusPublished - 1 Dec 1999
Externally publishedYes

Keywords

  • Constraint logic programming
  • Mixed integer programming

Cite this