8 papers
A centerpoint theorem for three planar convex bodies
Hongyu Cheng, Amitabh Basu
For planar convex bodies satisfying , we prove that the union of the three slices , , co…
Sample Complexity of Stochastic Optimization with Integer Variables
Hongyu Cheng, Yinghao Zheng, Marco Molinaro +1
We establish sample complexity results for stochastic optimization over the integers, especially with a view to understand the complexity with respect to the corresponding continuo…
Linear Threshold for Oertel's Conjecture on the Mixed-Integer Volume
Hongyu Cheng, Amitabh Basu
Grünbaum's inequality guarantees that the centroid of a convex body has halfspace depth at least : every halfspace containing the centroid captures at least a fraction o…
Theoretical Challenges in Learning for Branch-and-Cut
Hongyu Cheng, Amitabh Basu
Machine learning is increasingly used to guide branch-and-cut (B&C) for mixed-integer linear programming by learning score-based policies for selecting branching variables and cutt…
Identifying faulty edges in resistive electrical networks
Barbara Fiedorowicz, Amitabh Basu
Given a resistive electrical network, we would like to determine whether all the resistances (edges) in the network are working, and if not, identify which edge (or edges) are faul…
Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming
Hongyu Cheng, Amitabh Basu
Mixed-integer programming (MIP) provides a powerful framework for optimization problems, with Branch-and-Cut (B&C) being the predominant algorithm in state-of-the-art solvers. The…
Learning Cut Generating Functions for Integer Programming
Hongyu Cheng, Amitabh Basu
The branch-and-cut algorithm is the method of choice to solve large scale integer programming problems in practice. A key ingredient of branch-and-cut is the use of cutting planes…
Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut
Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz +1
Data-driven algorithm design is a paradigm that uses statistical and machine learning techniques to select from a class of algorithms for a computational problem an algorithm that…