1 citations · 1 across the 9 of their papers we have counts for
9 papers · 1 filter
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,…
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…
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…