-
Article
Information complexity of mixed-integer convex optimization
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, improving upon the previous b...
-
Article
A theoretical and computational analysis of full strong-branching
Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to ...
-
Article
Open AccessSystemic advantage has a meaningful relationship with grade outcomes in students’ early STEM courses at six research universities
Large introductory lecture courses are frequently post-secondary students’ first formal interaction with science, technology, engineering, and mathematics (STEM) disciplines. Grade outcomes in these courses ar...
-
Article
Lipschitz Selectors May Not Yield Competitive Algorithms for Convex Body Chasing
The current best algorithms for the convex body chasing (CBC) problem in online algorithms use the notion of the Steiner point of a convex set. In particular, the algorithm that always moves to the Steiner poi...
-
Article
Branch-and-bound solves random binary IPs in poly(n)-time
Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes a...
-
Article
Solving sparse principal component analysis with global support
Sparse principal component analysis with global support (SPCAgs), is the problem of finding the top-r leading principal components such that all these principal components are linear combinations of a common subs...
-
Article
Lower bounds on the size of general branch-and-bound trees
A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general disjunctions of the form $$\pi ^{\top } x \le \pi _...
-
Chapter and Conference Paper
Information Complexity of Mixed-Integer Convex Optimization
We investigate the information complexity of mixed-integer convex optimization under different kinds of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous b...
-
Article
Sparse PSD approximation of the PSD cone
While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global pos...
-
Chapter
Supporting Faculty Adoption of Learning Analytics within the Complex World of Higher Education
Faculty adoption of learning analytics is critical to advancing a data-informed culture in higher education. Faculty care deeply about their students and want to make the most of the limited instructional time...
-
Article
Minimal cut-generating functions are nearly extreme
We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory–Johnson setting as well as a recent extension by Yıldız and C...
-
Article
Aggregation-based cutting-planes for packing and covering integer programs
In this paper, we study the strength of Chvátal–Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: given an IP formulat...
-
Article
Theoretical challenges towards cutting-plane selection
While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of selecting a...
-
Article
Mixed-integer quadratic programming is in NP
Mixed-integer quadratic programming is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this p...
-
Article
Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
We investigate how well the graph of a bilinear function \(b{:}\;[0,1]^n\rightarrow \mathbb {R}\) ...
-
Article
Testing Lipschitz Functions on Hypergrid Domains
A function \(f(x_1, \ldots , x_d)\) f ...
-
Chapter and Conference Paper
Minimal Cut-Generating Functions are Nearly Extreme
We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory-Johnson setting as well as a recent extension by Cornuéjols a...
-
Article
Approximating polyhedra with sparse inequalities
In this paper, we study how well one can approximate arbitrary polytopes using sparse inequalities. Our motivation comes from the use of sparse cutting-planes in mixed-integer programing (MIP) solvers, since t...
-
Chapter and Conference Paper
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characteriz...
-
Article
Improved Approximation Algorithms for the Average-Case Tree Searching Problem
We study the following tree search problem: in a given tree T=(V,E) a vertex has been marked and we want to identify it. In order to locate the marked vertex, we can use edge queries. An edge query e asks in whic...
