(614a) Optimal Operation and Design of Pooling and Other Bilinear Networks

Pooling and blending problems typically involve maximizing profit subject to supply, demand, storage capacity, and product quality constraints.  Applications of the pooling problem include:  petroleum refining, wastewater treatment, communications, and supply-chain operations [1].  Bilinear network flow problems typically involve maximizing profit subject to network topology constraints.  Applications of the bilinear network flow problem include:  superstructure optimization, reactor network design, and heat and water integration [2].

Pooling problems and network flow problems can be formulated as non-convex mixed-integer non-linear programs and generally have many local solutions.  Large-scale problem instances lead to challenging global optimization problems.  Algorithmically, one is interested in solving optimization problems with mostly bilinear nonlinearities and possibly integer variables to model fixed charges.  These types of problems are very challenging and continue to constitute a very difficult and important class of problems for the modeling and optimization of chemical supply chains.

Tight convex relaxations are essential when solving these difficult problems to global optimality with a branch-and-bound algorithm [3].  It is now understood that the successful application of convexification techniques often requires unconventional mathematical reformulations of the problem constraints.  We combine reformulation linearization techniques [4] and advanced convex envelope construction techniques [5] to produce tight subproblem formulations for these bilinear programming applications.  Extensive computational results will be provided.

[1] Misener, R. and Floudas, C.A.. “Advances for the pooling problem:  modeling, global optimization, and computational studies.” Appl. Comput.. Math. 8, 3-22, 2009.

[2] Ruiz, J.P. and Grossmann, I.E., “Exploiting vector space properties to strengthen the relaxation of bilinear programs arising in the global optimization of process networks.” Optimization Letters, 5, 1-11, 2011.

[3] Tawarmalani, M. and Sahinidis, N.V.. "Global optimization of mixed-integer nonlinear programs:  A theoretical and computational study." Mathematical Programming. 99, 563-591, 2004.

[4] Sherali, H.D. and Adams, W.P.. "A reformulation-linearization technique for solving discrete and continuous nonconvex problems." Norwell: Kluwer, 1999.

[5] Bao, X., Sahinidis, N.V., and Tawarmalani, M.. “Multiterm polyhedral relaxtions for nonconvex, quadratically-constrained quadratic programs.” Optimization Methods and Software. 24, 485-504, 2009.