What makes Models Compositional? A Theoretical View
Parikshit Ram, Tim Klinger, et al.
IJCAI 2024
Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization is NP-hard. In this paper, we study the cardinality constrained multilinear set in the special case when the number of monomials is exactly two. We give an extended formulation, with two more auxiliary variables and exponentially many inequalities, of the convex hull of solutions of the standard linearization of this problem. We also show that the separation problem can be solved efficiently.
Parikshit Ram, Tim Klinger, et al.
IJCAI 2024
Sanjeeb Dash, Oktay Günlük, et al.
INFORMS Journal on Computing
Lee Martie, Jessie Rosenberg, et al.
ICSE 2023
Sumit Neelam, Udit Sharma, et al.
EMNLP 2022