Formulations and solution methods for global optimization of the Pooling problem and its extensions
Loading...
Authors
Cheng, Xin
Date
Type
thesis
Language
eng
Keyword
Global Optimization , Pooling Problem , Bilinear Programming , P formulation , Multi-commodity Flow , Mixed-integer Bilinear Programming
Alternative Title
Abstract
The pooling problem is an important research topic in global optimization. Due to huge economic savings, this bilinear programming problem (BLP) has attracted many researchers in global optimization and boosted the development in this field. The thesis is concerned with formulations and algorithms for the pooling problem and its extensions.
A key issue in global optimization is the mathematical formulation. An engineering problem may be mathematically expressed differently. The computational efforts required by different formulations may vary significantly. The existing formulations use either quality variables (P-formulation and its variants) or split-fraction variables (SF-formulation and its variants) to model the blending effect. However, theoretical comparison of the formulations is only limited to those among the same category.
The first contribution is a theoretical comparison between P- and SF- formulations for the generalized pooling problem (GPP), which focuses on the tightness of the convex relaxations. A formulation that has a tighter convex relaxation is said to be stronger. It is proved first that P ̂-formulation (an enhanced P) is at least as strong as SF-formulation under bound consistency conditions that are usually satisfied by practical problems. Then P-formulation is proved to be equivalent to the P ̂-formulation under certain conditions.
Knowing the strength of P-formulation, the next contribution improves formulations for the water treatment network (WTN) and total water network (TWN) optimization problem. The proposed P*-formulation can notably reduce the solution time from the existing formulations.
Formulations that track commodity flows are shown to be stronger than their component flow counterparts, but their extension to water treatment networks is challenging due to the existence of treatment units. This thesis proposes a multi-commodity flow formulation for the WTN and proves its strength.
The last contribution is a discretization-based global optimization algorithm for mixed-integer bilinear programming problems (MIBLPs). It is found that the existing fix-base discretization formulation may lead to weak relaxation, and the mixed-integer linear programming (MILP) problem may become unnecessarily large. The proposed algorithm uses a hybrid formulation (H-formulation) which yields tight relaxation and allows flexible numbers of partitions. It is able to solve most of the test problems faster than the global solvers.
Description
Citation
Publisher
License
Queen's University's Thesis/Dissertation Non-Exclusive License for Deposit to QSpace and Library and Archives Canada
ProQuest PhD and Master's Theses International Dissemination Agreement
Intellectual Property Guidelines at Queen's University
Copying and Preserving Your Thesis
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.
Attribution 3.0 United States
ProQuest PhD and Master's Theses International Dissemination Agreement
Intellectual Property Guidelines at Queen's University
Copying and Preserving Your Thesis
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.
Attribution 3.0 United States