Optimization Online


Strong Convex Nonlinear Relaxations of the Pooling Problem

James Luedtke(jim.luedtke***at***wisc.edu)
Claudia D'Ambrosio(dambrosio***at***lix.polytechnique.fr)
Jeff Linderoth(linderoth***at***wisc.edu)
Jonas Schweiger(schweiger***at***zib.de)

Abstract: We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by considering a single product, a single attibute, and a single pool. The convex hull of the resulting nonconvex set is not polyhedral. We derive valid linear and convex nonlinear inequalities for the convex hull, and demonstrate that different subsets of these inequalities define the convex hull of the nonconvex set in three cases determined by the parameters of the set. Computational results on literature instances and newly created larger test instances demonstrate that the inequalities can significantly strengthen the convex relaxation of the pq-formulation of the pooling problem, which is the relaxation known to have the strongest bound.

Keywords: Bilevel optimization, nonconvex optimization, pooling problem

Category 1: Global Optimization

Category 2: Applications -- Science and Engineering (Chemical Engineering )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Zuse Institute Berlin Report 18-12, Berlin, Germany, March 2018

Download: [PDF]

Entry Submitted: 03/07/2018
Entry Accepted: 03/07/2018
Entry Last Modified: 03/07/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society