Pooling Problem: Alternate Formulations and Solution Methods

Charles Audet (), Jack Brimberg (), Pierre Hansen (), Sébastien Le Digabel () and Nenad Mladenovi\'{c} ()
Additional contact information
Charles Audet: GERAD and École Polytechnique de Montréal, C.P. 6079, Succursalle Centre-ville, Montréal, Québec, Canada H3C 3A7
Jack Brimberg: School of Business Administration, University of Prince Edward Island, Charlottetown, Prince Edward Island, Canada C1A 4P3
Pierre Hansen: GERAD and École des Hautes Études Commerciales, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada H3T 2A7
Sébastien Le Digabel: GERAD and École des Hautes Études Commerciales, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada H3T 2A7
Nenad Mladenovi\'{c}: GERAD and École des Hautes Études Commerciales, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada H3T 2A7

Management Science, 2004, vol. 50, issue 6, 761-776

Abstract: The pooling problem, which is fundamental to the petroleum industry, describes a situation in which products possessing different attribute qualities are mixed in a series of pools in such a way that the attribute qualities of the blended products of the end pools must satisfy given requirements. It is well known that the pooling problem can be modeled through bilinear and nonconvex quadratic programming. In this paper, we investigate how best to apply a new branch-and-cut quadratic programming algorithm to solve the pooling problem. To this effect, we consider two standard models: One is based primarily on flow variables, and the other relies on the proportion of flows entering pools. A hybrid of these two models is proposed for general pooling problems. Comparison of the computational properties of flow and proportion models is made on several problem instances taken from the literature. Moreover, a simple alternating procedure and a variable neighborhood search heuristic are developed to solve large instances and compared with the well-known method of successive linear programming. Solution of difficult test problems from the literature is substantially accelerated, and larger ones are solved exactly or approximately.

Keywords: pooling problem; bilinear programming; branch-and-cut; heuristics; variable neighborhood search (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1030.0207 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:50:y:2004:i:6:p:761-776

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().