- Title
- Pooling problems: advances in theory and applications
- Creator
- Rigterink, Fabian
- Relation
- University of Newcastle Research Higher Degree Thesis
- Resource Type
- thesis
- Date
- 2017
- Description
- Research Doctorate - Doctor of Philosophy (PhD)
- Description
- This thesis presents advances in theory and applications of the pooling problem—a nonlinear optimisation problem of great importance to the oil and petroleum refining industry, but also to the mining industry. The nonlinearities of the problem arise from bilinear constraints that capture the blending of material. Linearisation is a common approach used in state-of-the-art optimisation software to solve these types of problems. A crucial task is to construct tight linear relaxations, the tightest being the convex hull. Typically, bilinear functions are linearised using a term-wise McCormick relaxation. For a single bilinear term, the McCormick relaxation is convex hull defining, however, for a bilinear function, it often is not. In addition to the McCormick inequalities, Padberg introduced triangle, clique, cut, generalised cut, and odd cycle inequalities, to further approximate the convex hull. On the theoretical side, we propose new multi-commodity flow formulations of the pooling problem which outperform previously known formulations. Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs is polynomially solvable. This result further defines the border between (strongly) NP-hard and polynomially solvable cases of the problem. Answering a question of Luedtke, Namazifar, and Linderoth, we show that the McCormick relaxation of a bilinear function can, in some sense, be arbitrarily looser than its convex hull. We present an alternative proof for a result of Misener, Smadbeck, and Floudas which characterises bilinear functions for which the McCormick relaxation is convex hull defining. Using McCormick and Padberg inequalities, we define the convex hulls of several additional classes of bilinear functions. As for bilinear functions for which we cannot define the convex hull, we find that McCormick and Padberg's triangle inequalities approximate the convex hull best, and we apply these inequalities to (quadratically constrained) quadratic programs to speed up a solver's performance. On the applied side, we model coal blending operations at the port of Newcastle, Australia—the world's largest coal export port. Coal is made-to-order according to customers' desired quality values and vessel loading times. The coal chain coordinator is interested in meeting these target qualities and times since deviations on either side typically result in contractually agreed costs. We model this setting as a dynamic, time-expanded pooling problem, apply flow discretisations, and solve large, realistic instances.
- Subject
- pooling problem; bilinear programming; nonlinear programming; global optimization; blending
- Identifier
- http://hdl.handle.net/1959.13/1350692
- Identifier
- uon:30594
- Rights
- Copyright 2017 Fabian Rigterink
- Language
- eng
- Full Text
- Hits: 511
- Visitors: 1709
- Downloads: 1143
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Thesis | 2 MB | Adobe Acrobat PDF | View Details Download | ||
| View Details Download | ATTACHMENT02 | Abstract | 372 KB | Adobe Acrobat PDF | View Details Download |