The pooling problem is one of the fundamental optimization problems encountered in the petroleum industry. In the pooling problem, final products are produced using two stages of blending operations. In the first stage, raw materials are mixed together to produce intermediate products. In the second stage, intermediate products and some of the raw materials are blended together according to product demand and quality requirements. Generally, the pooling problem is a nonlinear problem because the output stream qualities, which are unknown, depend on the volume, which is also unknown, and on the quality of the input streams. Specifically, nonlinearity and nonconvexity are due to the use of bilinear terms either in the quality constraints or in the objective function. Nonlinearity and nonconvexity result in several local optima, making the process of solving large-scale pooling problems to global optimality very challenging. Therefore, developing efficient heuristics for large-scale pooling problems is very desirable. Moreover, devising tight bounds on the global solutions is essential to assess the quality of the proposed heuristics.
In this thesis, we use a Lagrangean relaxation approach where feasible solutions and lower bounds are generated for the pooling problem. The procedure targets all nonlinear constraints and penalizes their violation in the objective function. The resulting Lagrangean subproblem has a nonlinear objective function and linear constraints. The Lagrangean subproblem is reformulated as a mixed integer programming problem where the nonlinearities in the objective function are eliminated at the expense of using binary variables. The obtained Lagrangean lower bounds are strengthened using valid cuts that are based on the relaxed bilinear terms. In addition, at every iteration of the Lagrangean algorithm, the subproblem solutions are used to generate feasible solutions to the pooling problem.
The procedure is applied to fifteen pooling problems collected from the literature. Some of these problems have a single quality and others have multiple qualities. Numerical results show that for eight solved cases, the obtained Lagrangean lower bounds are equal to the global optima, whereas for seven cases the obtained Lagrangean lower bound is on average 8.2% from the global optimum. Numerical results indicate the efficiency of the heuristic. For nine cases, the heuristic gives the global solution, and for the other cases the heuristic solutions are within 1.8% of the global optimum.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/3553 |
| Date | January 2008 |
| Creators | Almutairi, Hossa |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0183 seconds