1 citations · 1 across the 9 of their papers we have counts for
11 papers
Sharp Logarithmic Thresholds for Cut Schedules in an Abstract Branch-and-Cut Model
Hongyi Jiang
Branch-and-cut interleaves branching with cutting-plane generation. How the two operations share the work of proving a bound is a basic theoretical question. We study an abstract m…
A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles
Phillip Kerger, Marco Molinaro, Hongyi Jiang +1
Given any algorithm for convex optimization that uses exact first-order information (i.e., function values and subgradients), we show how to use such an algorithm to solve the prob…
Information Complexity of Mixed-integer Convex Optimization
Amitabh Basu, Hongyi Jiang, Phillip Kerger +1
We investigate the information complexity of mixed-integer convex optimization under different types of oracles. We establish new lower bounds for the standard first-order oracle,…
A Nonparametric Test of th-degree Inverse Stochastic Dominance
Hongyi Jiang, Zhenting Sun, Shiyun Hu
This paper proposes a nonparametric test for th-degree inverse stochastic dominance which is a powerful tool for ranking distribution functions according to social welfare. We c…
Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems
Hongyi Jiang, Samitha Samaranayake
Motivated by a transit line planning problem in transportation systems, we investigate the following capacitated assignment problem under a budget constraint. Our model involves $L…
Helly systems and certificates in optimization
Amitabh Basu, Tongtong Chen, Michele Conforti +1
Inspired by branch-and-bound and cutting plane proofs in mixed-integer optimization and proof complexity, we develop a general approach via Hoffman's Helly systems. This helps to d…
Enumerating integer points in polytopes with bounded subdeterminants
Hongyi Jiang, Amitabh Basu
We show that one can enumerate the vertices of the convex hull of integer points in polytopes whose constraint matrices have bounded and nonzero subdeterminants, in time polynomial…
Complexity of branch-and-bound and cutting planes in mixed-integer optimization -- II
Amitabh Basu, Michele Conforti, Marco Di Summa +1
We study the complexity of cutting planes and branching schemes from a theoretical point of view. We give some rigorous underpinnings to the empirically observed phenomenon that co…
Two-halfspace closure
Amitabh Basu, Hongyi Jiang
We define a new cutting plane closure for pure integer programs called the two-halfspace closure. It is a natural generalization of the well-known Chvátal-Gomory closure. We prove…
Complexity of branch-and-bound and cutting planes in mixed-integer optimization
Amitabh Basu, Michele Conforti, Marco Di Summa +1
We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency…
Split cuts in the plane
Amitabh Basu, Michele Conforti, Marco Di Summa +1
We provide a polynomial time cutting plane algorithm based on split cuts to solve integer programs in the plane. We also prove that the split closure of a polyhedron in the plane h…