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 language | English |
|---|---|
| Pages (from-to) | 421-431 |
| Number of pages | 11 |
| Journal | Annals of Operations Research |
| Volume | 81 |
| Publication status | Published - 1 Dec 1998 |
| Externally published | Yes |
Keywords
- Branch and bound
- Combinatorial optimisation
- Constraint satisfaction
- Finite domain propagation
- Integer programming
- Simplex method
Cite this
}
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 journal › Article › Research › peer-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 -