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

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

0.00 Avg rating0 Votes
Article ID: iaor2000471
Country: Netherlands
Volume: 86
Issue: 1
Start Page Number: 63
End Page Number: 87
Publication Date: Mar 1999
Journal: Annals of Operations Research
Authors: , ,
Keywords: logical constraints, constraint handling languages
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 and the MIP system CPLEX, 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 non-linear 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 and the Progressive Party Problem.

Reviews

Required fields are marked *. Your email address will not be published.