Rule Induction in Knowledge Graphs Using Linear Programming
Sanjeeb Dash, João Gonçalves
AAAI 2023
We study the master equality polyhedron (MEP) which generalizes the master cyclic group polyhedron (MCGP) and the master knapsack polyhedron (MKP). We present an explicit characterization of the polar of the nontrivial facet-defining inequalities for MEP. This result generalizes similar results for the MCGP by Gomory (1969) and for the MKP by Araóz (1974). Furthermore, this characterization gives a polynomial time algorithm for separating an arbitrary point from MEP. We describe how facet-defining inequalities for the MCGP can be lifted to obtain facet-defining inequalities for MEP, and also present facet-defining inequalities for MEP that cannot be obtained in such a way. Finally, we study the mixed-integer extension of MEP and present an interpolation theorem that produces valid inequalities for general mixed integer programming problems using facets of MEP. © 2008 Springer-Verlag.
Sanjeeb Dash, João Gonçalves
AAAI 2023
Sanjeeb Dash, Oktay Günlük, et al.
Mathematical Programming
Ramesh Neelamani, Sanjeeb Dash, et al.
SIAM Journal on Discrete Mathematics
Oktay Günlük, Yves Pochet
Mathematical Programming, Series B