Towards a closer integration of finite domain propagation and simplex-based algorithms

Mozafar T. Hajian, Hani El-Sakkout, Mark Wallace, Jonathan M. Lever, Barry Richards

Research output: Contribution to journalArticleResearchpeer-review

Abstract

This paper describes our experience in implementing an industrial application using the finite domain solver of the ECLiPSe constraint logic programming (CLP) system, in conjunction with the mathematical programming (MP) system, FortMP. In this technique, the ECLiPSe system generates a feasible solution that is adapted to construct a starting point (basic solution) for the MP solver. The basic solution is then used as an input to the FortMP system to warm-start the simplex (SX) algorithm, hastening the solution of the linear programming relaxation, (LPR). SX proceeds as normal to find the optimal integer solution. Preliminary results indicate that the integration of the two environments is suitable for this application in particular, and may generally yield significant benefits. We describe adaptations required in the hybrid method, and report encouraging experimental results for this problem.

Original languageEnglish
Pages (from-to)421-431
Number of pages11
JournalAnnals of Operations Research
Volume81
Publication statusPublished - 1 Dec 1998
Externally publishedYes

Keywords

  • Branch and bound
  • Combinatorial optimisation
  • Constraint satisfaction
  • Finite domain propagation
  • Integer programming
  • Simplex method

Cite this

Hajian, Mozafar T. ; El-Sakkout, Hani ; Wallace, Mark ; Lever, Jonathan M. ; Richards, Barry. / Towards a closer integration of finite domain propagation and simplex-based algorithms. In: Annals of Operations Research. 1998 ; Vol. 81. pp. 421-431.
@article{4288d56be8d249bd80f5838a3d1ba0c3,
title = "Towards a closer integration of finite domain propagation and simplex-based algorithms",
abstract = "This paper describes our experience in implementing an industrial application using the finite domain solver of the ECLiPSe constraint logic programming (CLP) system, in conjunction with the mathematical programming (MP) system, FortMP. In this technique, the ECLiPSe system generates a feasible solution that is adapted to construct a starting point (basic solution) for the MP solver. The basic solution is then used as an input to the FortMP system to warm-start the simplex (SX) algorithm, hastening the solution of the linear programming relaxation, (LPR). SX proceeds as normal to find the optimal integer solution. Preliminary results indicate that the integration of the two environments is suitable for this application in particular, and may generally yield significant benefits. We describe adaptations required in the hybrid method, and report encouraging experimental results for this problem.",
keywords = "Branch and bound, Combinatorial optimisation, Constraint satisfaction, Finite domain propagation, Integer programming, Simplex method",
author = "Hajian, {Mozafar T.} and Hani El-Sakkout and Mark Wallace and Lever, {Jonathan M.} and Barry Richards",
year = "1998",
month = "12",
day = "1",
language = "English",
volume = "81",
pages = "421--431",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer-Verlag London Ltd.",

}

Towards a closer integration of finite domain propagation and simplex-based algorithms. / Hajian, Mozafar T.; El-Sakkout, Hani; Wallace, Mark; Lever, Jonathan M.; Richards, Barry.

In: Annals of Operations Research, Vol. 81, 01.12.1998, p. 421-431.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Towards a closer integration of finite domain propagation and simplex-based algorithms

AU - Hajian, Mozafar T.

AU - El-Sakkout, Hani

AU - Wallace, Mark

AU - Lever, Jonathan M.

AU - Richards, Barry

PY - 1998/12/1

Y1 - 1998/12/1

N2 - This paper describes our experience in implementing an industrial application using the finite domain solver of the ECLiPSe constraint logic programming (CLP) system, in conjunction with the mathematical programming (MP) system, FortMP. In this technique, the ECLiPSe system generates a feasible solution that is adapted to construct a starting point (basic solution) for the MP solver. The basic solution is then used as an input to the FortMP system to warm-start the simplex (SX) algorithm, hastening the solution of the linear programming relaxation, (LPR). SX proceeds as normal to find the optimal integer solution. Preliminary results indicate that the integration of the two environments is suitable for this application in particular, and may generally yield significant benefits. We describe adaptations required in the hybrid method, and report encouraging experimental results for this problem.

AB - This paper describes our experience in implementing an industrial application using the finite domain solver of the ECLiPSe constraint logic programming (CLP) system, in conjunction with the mathematical programming (MP) system, FortMP. In this technique, the ECLiPSe system generates a feasible solution that is adapted to construct a starting point (basic solution) for the MP solver. The basic solution is then used as an input to the FortMP system to warm-start the simplex (SX) algorithm, hastening the solution of the linear programming relaxation, (LPR). SX proceeds as normal to find the optimal integer solution. Preliminary results indicate that the integration of the two environments is suitable for this application in particular, and may generally yield significant benefits. We describe adaptations required in the hybrid method, and report encouraging experimental results for this problem.

KW - Branch and bound

KW - Combinatorial optimisation

KW - Constraint satisfaction

KW - Finite domain propagation

KW - Integer programming

KW - Simplex method

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

M3 - Article

VL - 81

SP - 421

EP - 431

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

ER -