Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness.

Area of Science:

• Process Systems Engineering
• Optimization Theory
• Computational Complexity

Background:

• The standard pooling problem is a NP-hard, non-convex optimization problem frequently encountered in process systems engineering.
• Existing approaches often struggle with the inherent complexity and non-convexity of these problems.

Purpose of the Study:

• To investigate the topological structure and sparsity of the single quality standard pooling problem using a parametric approach.
• To validate the hypothesis that pooling problems are fundamentally based on piecewise-defined functions.
• To establish conditions under which the problem's complexity relates to the P/NP boundary.

Main Methods:

• A parametric approach is employed to analyze the pooling problem in its p-formulation.
• Dominant active topologies are introduced under relaxed flow availability to identify sparsity.
• The association between sparse patterns and piecewise objective functions is mathematically demonstrated.

Main Results:

• The analysis confirms that pooling problems exhibit a piecewise structure, aligning with prior intuition.
• Explicit identification of sparsity in pooling problems is achieved through dominant active topologies.
• Conditions for the vanishing of sparsity and the emergence of combinatorial complexity (P/NP boundary) are elucidated.

Conclusions:

• The parametric approach effectively reveals the underlying piecewise nature and sparsity of standard pooling problems.
• Understanding sparsity is crucial for managing the computational complexity of these optimization problems.
• The findings provide a theoretical foundation for developing more efficient algorithms for pooling problems.