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
August 1998
Annals of Operations Research;1998, Vol. 81 Issue 1-4, p421
Academic Journal
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.


Related Articles

  • Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods. Fernández, José; Tóth, Boglárka // Computational Optimization & Applications;Apr2009, Vol. 42 Issue 3, p393 

    Obtaining a complete description of the efficient set of multiobjective optimization problems can be of invaluable help to the decision-maker when the objectives conflict and a solution has to be chosen. In this paper we present an interval branch-and-bound algorithm which aims at obtaining a...

  • BRANCH-AND-BOUND AS A HIGHER-ORDER FUNCTION. Mckeown, G. P.; Rayward-Smith, V. J.; Turpin, H. J. // Annals of Operations Research;1991, Vol. 33 Issue 1-4, p379 

    The branch-and-bound paradigm is presented as a higher-order function and illustrated by instantiations, providing two well-known branch-and-bound algorithms for the Steiner tree problem in graphs and one for the travelling salesman problem. We discuss the advantages of such a specification and...

  • Parallel branch-and-branch algorithms: Survey and synthesis. Gendron, Bernard; Crainic, Teodor Gabriel // Operations Research;Nov/Dec94, Vol. 42 Issue 6, p1042 

    We present a detailed and up-to-date survey of the literature on parallel branch-and-bound algorithms. We synthesize previous work in this area and propose a new classification of parallel branch-and-bound algorithms. This classification is used to analyze the methods proposed in the literature....

  • Optimal periodic scheduling of multipurpose batch plants. Shah, N.; Pantelides, C. C.; Sargent, R. W. H. // Annals of Operations Research;1993, Vol. 42 Issue 1-4, p193 

    A rigorous mathematical programming framework for the scheduling of multipurpose batch plants operated in a cyclic mode is presented. The proposed formulation can deal with batch operations described by complex processing networks, involving shared intermediates, material recycles, and multiple...

  • A NEW ALGORITHM FOR THE 0-1 KNAPSACK PROBLEM. Martello, Silvano; Toth, Paolo // Management Science;May88, Vol. 34 Issue 5, p633 

    We present a new algorithm for the optimal solution of the 0-1 Knapsack problem, which is particularly effective for large-size problems. The algorithm is based on determination of an appropriate small subset of items and the solution of the corresponding "core problem": from this we derive a...

  • Surrogate Dual Multiplier Search Procedures in Integer Programming. Karwan, Mark H.; Rardin, Ronald L. // Operations Research;Jan/Feb84, Vol. 32 Issue 1, p52 

    Search procedures for optimal Lagrange multipliers are highly developed and provide good bounds in branch and bound procedures that have led to the successful application of Lagrangean duality in integer programming. Although the surrogate dual generally provides a better objective bound, there...

  • Recent advances in the solution of quadratic assignment problems. Anstreicher, Kurt M. // Mathematical Programming;Jul2003, Vol. 97 Issue 1/2, p27 

    The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these...

  • Liquid Phase Stability via Global Optimization. Rodrigues, Vânia; Pereira, Ana I.; Ferreira, Olga; Pinho, Simão P. // AIP Conference Proceedings;9/30/2010, Vol. 1281 Issue 1, p991 

    In this work, the Penalty Stretched Simulated Annealing Method and the Multilocal Branch and Bound method were applied to identify the stationary points of the tangent plane distance function defined for the Gibbs energy. The classic excess Gibbs energy Non Random Two Liquid model was used for...

  • A NEW BRANCH-AND-BOUND ALGORITHM FOR THE FIXED-CHARGE TRANSPORTATION PROBLEM. Kennington, Jeff; Unger, Ed // Management Science;Jun76, Vol. 22 Issue 10, p1116 

    A new branch-and-bound procedure specialized for the fixed-charge transportation problem has been developed. The technique strongly exploits the underlying transportation structure. The relaxed problem assumes this form and simple penalties are easily constructed from the optimal solution of...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics