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

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

@article{9abe7fb1fedc4bf3b68eed6f3374427a,
title = "A new approach to integrating mixed integer programming and constraint logic programming",
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].",
keywords = "Constraint logic programming, Mixed integer programming",
author = "Robert Rodošek and Wallace, {Mark G.} and Hajian, {Mozafar T.}",
year = "1999",
month = "12",
day = "1",
language = "English",
volume = "86",
pages = "63--87",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer-Verlag London Ltd.",

}

A new approach to integrating mixed integer programming and constraint logic programming. / Rodošek, Robert; Wallace, Mark G.; Hajian, Mozafar T.

In: Annals of Operations Research, Vol. 86, 01.12.1999, p. 63-87.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Rodošek, Robert

AU - Wallace, Mark G.

AU - Hajian, Mozafar T.

PY - 1999/12/1

Y1 - 1999/12/1

N2 - 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].

AB - 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].

KW - Constraint logic programming

KW - Mixed integer programming

UR - http://www.scopus.com/inward/record.url?scp=0042094661&partnerID=8YFLogxK

M3 - Article

VL - 86

SP - 63

EP - 87

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

ER -