Piecewise Polyhedral Formulations for a Multilinear Term

2020/01/02 by Sundar, Kaarthik, Nagarajan, Harsha, Linderoth, Jeff +2
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2001.00514

Abstract

In this paper, we present a mixed-integer linear programming (MILP) formulation of a piecewise, polyhedral relaxation (PPR) of a multilinear term using its convex hull representation. Based on the solution of the PPR, we also present a MILP formulation whose solutions are feasible for nonconvex, multilinear equations. We then present computational results showing the effectiveness of proposed formulations on instances of standard benchmarks of nonlinear programs (NLPs) with multilinear terms and compare the proposed formulation with a traditional formulation that is built by recursively relaxing bilinear groupings of multilinear terms.

Related

• Building Formulations for Piecewise Linear Relaxations of Nonlinear Functions
• Polyhedral Properties of RLT Relaxations of Nonconvex Quadratic Programs and Their Implications on Exact Relaxations
• New SOCP relaxation and branching rule for bipartite bilinear programs
• Extracting structure from functional expressions for continuous and discrete relaxations of MINLP
• Recursive McCormick Linearization of Multilinear Programs