17 citations · 21 across the 8 of their papers we have counts for
8 papers
The Complexity of Recognizing Facets for the Knapsack Polytope
Rui Chen, Haoran Zhu
The complexity class DP is the class of all languages that are the intersection of a language in NP and a language in coNP. It was conjectured that recognizing a facet for the knap…
Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints
Alberto Del Pia, Jeff Linderoth, Haoran Zhu
We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based…
New Classes of Facets for Complementarity Knapsack Problems
Alberto Del Pia, Jeff Linderoth, Haoran Zhu
The complementarity knapsack problem (CKP) is a knapsack problem with real-valued variables and complementarity conditions between pairs of its variables. We extend the polyhedral…
On the Complexity of Separating Cutting Planes for the Knapsack Polytope
Alberto Del Pia, Jeff Linderoth, Haoran Zhu
We close three open problems in the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cove…
Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets: Theory and Computation
Alberto Del Pia, Jeff Linderoth, Haoran Zhu
We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequali…
On the Polyhedrality of the Chvatal-Gomory Closure
Haoran Zhu
In this paper, we provide an equivalent condition for the Chvatal-Gomory (CG) closure of a closed convex set to be finitely-generated. Using this result, we are able to prove that,…
A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees
Haoran Zhu, Pavankumar Murali, Dzung T. Phan +2
Several recent publications report advances in training optimal decision trees (ODT) using mixed-integer programs (MIP), due to algorithmic advances in integer programming and a gr…
Integer packing sets form a well-quasi-ordering
Alberto Del Pia, Dion Gijswijt, Jeff Linderoth +1
An integer packing set is a set of non-negative integer vectors with the property that, if a vector is in the set, then every non-negative integer vector with is…