AUTHOREA
Log in
Sign Up
Browse Preprints
LOG IN
SIGN UP
Essential Site Maintenance
: Authorea-powered sites will be updated circa 15:00-17:00 Eastern on Tuesday 5 November.
There should be no interruption to normal services, but please contact us at
[email protected]
in case you face any issues.
Xin Cheng
Public Documents
1
On the P-formulation and the Split-Fraction-Formulation for the Generalized Pooling P...
Xin Cheng
and 1 more
July 21, 2021
The generalized pooling problem (GPP) is a NP-hard problem for which the solution time for securing a global optimal solution heavily depends on the strength of the problem formulation. The existing GPP formulations use either quality variables (P-formulation and the variants) or split-fraction variables (SF-formulation and the variants) to model the material balance at the pools. This paper is the first attempt to develop theoretical results for comparing the strength of P-formulation and SF-formulation. It is found that, an enhanced version of P-formulation, called P+-formulation, is at least as strong as SF-formulation under mild conditions. Furthermore, P+-formulation becomes identical to P-formulation when the pooling network comprises only mixers and splitters. With additional conditions that are often satisfied at the root node, P-formulation is proved to be as least as strong as SF-formulation. The theoretical results are verified by the computational study of 23 problem instances.