Intro
Preface
Organization
Contents
Information Complexity of Mixed-Integer Convex Optimization
1 First-order Information Complexity
1.1 Our Results
1.2 Formal Definitions and Statement of Results
1.3 Discussion and Future Avenues
2 Proof Sketches
2.1 Proof Sketch of Theorem 1
2.2 Proof of Theorem 3
2.3 Proof Sketch of Theorem 5
2.4 Proof Sketch of Theorems 2 and 4
References
Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products
1 Introduction
2 RLT for Bilinear Products
3 Detection of Implicit Products

4 Separation Algorithm
4.1 Row Marking
4.2 Projection Filtering
5 Computational Results
5.1 Setup
5.2 Impact of RLT Cuts
5.3 Separation
5.4 Experiments with Gurobi
5.5 Summary
References
A Nearly Optimal Randomized Algorithm for Explorable Heap Selection
1 Introduction
2 The Explorable Heap Selection Problem
3 A New Algorithm
3.1 The Algorithm
3.2 Proof of Correctness
3.3 Running Time Analysis
3.4 Space Complexity Analysis
4 Lower Bound
References
Sparse Approximation over the Cube
1 Introduction and Literature Review

2 Preliminaries
3 The l1-Relaxation for Random Targets b
4 Proximity Between Optimal Solutions of ([P0]P0) and ([P1]P1)
5 A Deterministic Algorithm
6 Extension
References
Recycling Inequalities for Robust Combinatorial Optimization with Budget Uncertainty
1 Introduction
2 Recycling Valid Inequalities
3 Facet-Defining Recycled Inequalities
4 Computational Study
4.1 Robust Independent Set
4.2 Robust Bipartite Matching
5 Conclusion
References
Inapproximability of Shortest Paths on Perfect Matching Polytopes
1 Introduction
1.1 Our Result

1.2 Pivot Rules for Circuit-Augmentation Algorithms
1.3 Related Works
2 Proof of Theorem 1
2.1 Preliminaries
2.2 Reduction
2.3 Proof of Lemma 3
References
Monoidal Strengthening and Unique Lifting in MIQCPs
1 Introduction
2 Monoidal Strengthening in the Homogeneous Case
3 Monoidal Strengthening in the Non-homogeneous Case
3.1 A Technical Consideration for Sg
3.2 Monoid Construction
4 Solving the Monoidal Strengthening Problem
5 Unique Lifting
6 Computational Results
References
From Approximate to Exact Integer Programming
1 Introduction

1.1 Contributions of This Paper
1.2 Related Work
2 Preliminaries
3 The Cut-Or-Average Algorithm
3.1 Bounding the Number of Iterations
3.2 Correctness and Efficiency of Subroutines
3.3 Conclusion on the Cut-Or-Average Algorithm
4 An Asymmetric Approximate Carathéodory Theorem
5 IPs with Polynomial Variable Range
References
Optimizing Low Dimensional Functions over the Integers
1 Introduction
1.1 Applications
1.2 Overview of Techniques
2 Non-negative Variables
3 Bounded Variables