Recursive McCormick Linearizations of Multilinear Programs: Minimum Size Formulations
Multilinear Programs (MLPs) are a particular class of MINLPs which have multilinear functions in both the objective and the constraints. MLPs are typically solved by using Branch-and-Bound algorithms which rely on Linear Programming (LP) relaxations to obtain lower bounds. These LP relaxations are derived using Recursive McCormick Linearizations i.e., by recursively introducing additional variables that represent bilinear products and by relaxing using McCormick envelopes. The size of the LP relaxation depends on the heuristic employed to identify the collection of variables to add. In this talk, we introduce the first approach for identifying the smallest size LP relaxation for a given MLP, by investigating an Integer Programming (IP) model that solves a specialized network flow representation where linearizations are encoded as in-trees. Our results on a collection of benchmarks indicate that the IP formulation can find smaller linearizations (up to 30% reduction in number of variables) and tighter relaxations (30% reduction in the root-node optimality gaps). We also provide insights into computing the best bound Recursive McCormick Linearization for a given LP size.
Time: Thu 2022-03-10 15.00 - 16.00
Location: 3721, note that it is online, but we setup with projector here
Video link: Zoom link, Meeting ID: 636 5838 1373
Lecturer: Arvind U Raghunathan
Arvind Raghunathan is currently a Senior Principal Research Scientist in the Data Analytics Group at Mitsubishi Electric Research Laboratories in Cambridge, Massachusetts, USA. His research focuses on algorithms for optimization of large-scale nonlinear and mixed integer nonlinear programs with applications in power grid, robotics, transportation systems, and model-based control of processes. He serves on the editorial board of Optimization and Engineering, and Journal of Optimization Theory and Applications. He is a member of INFORMS and SIAM. Arvind received the Ph.D. degree in Chemical Engineering from Carnegie Mellon University in Pittsburgh, USA.