Solving the pooling problem at scale with extensible solver GALINI
File(s)2105.01687v1.pdf (1.97 MB)
Working paper
Author(s)
Ceccon, Francesco
Misener, Ruth
Type
Working Paper
Abstract
This paper presents a Python library to model pooling problems, a class of
network flow problems with many engineering applications. The library
automatically generates a mixed-integer quadratically-constrained quadratic
optimization problem from a given network structure. The library additionally
uses the network structure to build 1) a convex linear relaxation of the
non-convex quadratic program and 2) a mixed-integer linear restriction of the
problem. We integrate the pooling network library with galini, an open-source
extensible global solver for quadratic optimization. We demonstrate galini's
extensible characteristics by using the pooling library to develop two galini
plug-ins: 1) a cut generator plug-in that adds valid inequalities in the galini
cut loop and 2) a primal heuristic plug-in that uses the mixed-integer linear
restriction. We test galini on large scale pooling problems and show that,
thanks to the good upper bound provided by the mixed-integer linear restriction
and the good lower bounds provided by the convex relaxation, we obtain
optimality gaps that are competitive with Gurobi 9.1 on the largest problem
instances.
network flow problems with many engineering applications. The library
automatically generates a mixed-integer quadratically-constrained quadratic
optimization problem from a given network structure. The library additionally
uses the network structure to build 1) a convex linear relaxation of the
non-convex quadratic program and 2) a mixed-integer linear restriction of the
problem. We integrate the pooling network library with galini, an open-source
extensible global solver for quadratic optimization. We demonstrate galini's
extensible characteristics by using the pooling library to develop two galini
plug-ins: 1) a cut generator plug-in that adds valid inequalities in the galini
cut loop and 2) a primal heuristic plug-in that uses the mixed-integer linear
restriction. We test galini on large scale pooling problems and show that,
thanks to the good upper bound provided by the mixed-integer linear restriction
and the good lower bounds provided by the convex relaxation, we obtain
optimality gaps that are competitive with Gurobi 9.1 on the largest problem
instances.
Date Issued
2021-05-04
Online Publication Date
2021-05-14T09:48:26Z
Citation
2021
Publisher
arXiv
Copyright Statement
© 2021 The Author(s)
Sponsor
Engineering and Physical Sciences Research Council
Identifier
http://arxiv.org/abs/2105.01687v1
Grant Number
EP/P016871/1
Subjects
math.OC
math.OC
Notes
42 pages
Publication Status
Published