Complexity of optimizing over the integers
From MaRDI portal
Communication complexity, information complexity (68Q11) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Mixed integer programming (90C11) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60)
Abstract: In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like "input", "size" and "complexity" in the context of general mathematical optimization, avoiding context dependent definitions which is one of the sources of difference in the treatment of complexity within continuous and discrete optimization. In the second part of the paper, we employ the language developed in the first part to study information theoretic and algorithmic complexity of {em mixed-integer convex optimization}, which contains as a special case continuous convex optimization on the one hand and pure integer optimization on the other. We strive for the maximum possible generality in our exposition. We hope that this paper contains material that both continuous optimizers and discrete optimizers find new and interesting, even though almost all of the material presented is common knowledge in one or the other community. We see the main merit of this paper as bringing together all of this information under one unifying umbrella with the hope that this will act as yet another catalyst for more interaction across the continuous-discrete divide. In fact, our motivation behind Part I of the paper is to provide a common language for both communities.
Recommendations
Cites work
- 0/1 polytopes with quadratic Chvátal rank
- A \(O(1/\epsilon ^{2})^{n }\)-time sieving algorithm for approximate integer programming
- A brief history of linear and mixed-integer programming computation
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A new algorithm for minimizing convex functions over convex sets
- A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
- A note on non-degenerate integer programs with small sub-determinants
- A polyhedral study of binary polynomial programs
- A strongly polynomial algorithm for bimodular integer linear programming
- A Theorem Concerning the Integer Lattice
- Algorithms in real algebraic geometry
- An application of simultaneous diophantine approximation in combinatorial optimization
- An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra
- An improved cutting plane method for convex optimization, convex-concave games, and its applications
- An observation on the structure of production sets with indivisibilities
- Bounds on the Chvatal rank of polytopes in the 0/1-cube
- Branch-and-bound solves random binary IPs in poly(n)-time
- Centerpoints: a link between optimization and convex geometry
- Chvátal closures for mixed integer programming problems
- Complexity of integer quasiconvex polynomial optimization
- Complexity, exactness, and rationality in polynomial optimization
- Computability and Noncomputability in Classical Analysis
- Convex optimization: algorithms and complexity
- Convexity in cristallographical lattices
- Cook, Kannan and Schrijver's example revisited
- Cutting planes, connectivity, and threshold logic
- Discretely ordered modules as a first-order extension of the cutting planes proof system
- Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
- Enumerating integer points in polytopes with bounded subdeterminants
- Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
- Geometric algorithms and combinatorial optimization
- Hard Knapsack Problems
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 4202031 (Why is no real title available?)
- scientific article; zbMATH DE number 3827201 (Why is no real title available?)
- scientific article; zbMATH DE number 3900744 (Why is no real title available?)
- scientific article; zbMATH DE number 3980484 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3770461 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 52121 (Why is no real title available?)
- scientific article; zbMATH DE number 3628385 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 408793 (Why is no real title available?)
- scientific article; zbMATH DE number 512977 (Why is no real title available?)
- scientific article; zbMATH DE number 545277 (Why is no real title available?)
- scientific article; zbMATH DE number 2086404 (Why is no real title available?)
- scientific article; zbMATH DE number 2086919 (Why is no real title available?)
- scientific article; zbMATH DE number 1390276 (Why is no real title available?)
- scientific article; zbMATH DE number 7561762 (Why is no real title available?)
- scientific article; zbMATH DE number 2196290 (Why is no real title available?)
- scientific article; zbMATH DE number 3291139 (Why is no real title available?)
- scientific article; zbMATH DE number 3349780 (Why is no real title available?)
- Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\). II: Application of \(K\)-convexity
- Integer convex minimization by mixed integer linear optimization
- Integer optimization on convex semialgebraic sets
- Integer program with bimodular matrix
- Integer programming and algorithmic geometry of numbers
- Integer Programming with a Fixed Number of Variables
- Integer quadratic programming in the plane
- Introductory lectures on convex optimization. A basic course.
- Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
- Lectures on convex optimization
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
- Lower bounds on the size of general branch-and-bound trees
- Minimizing cubic and homogeneous polynomials over integers in the plane
- Minkowski's Convex Body Theorem and Integer Programming
- Mixed integer programming computation
- Mixed-integer quadratic programming is in NP
- Nonlinear discrete optimization. An algorithmic theory
- On t-branch split cuts for mixed-integer programs
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On approximation algorithms for concave mixed-integer quadratic programming
- On cutting-plane proofs in combinatorial optimization
- On Integer Programming and the Branch-Width of the Constraint Matrix
- On integer programming with bounded determinants
- On the Chvátal rank of polytopes in the 0/1 cube
- On the complexity of cutting-plane proofs
- On the complexity of cutting-plane proofs using split cuts
- On the complexity of integer programming
- On the complexity of nonlinear mixed-integer optimization
- On the impact of running intersection inequalities for globally solving polynomial optimization problems
- On the matrix-cut rank of polyhedra.
- On the power and limitations of branch and cut
- On the width of semialgebraic proofs and algorithms
- On Vaidya's Volumetric Cutting Plane Method for Convex Programming
- Partitions of mass-distributions and of convex bodies by hyperplanes
- Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
- Split cuts in the plane
- Stabbing planes
- Subdeterminants and concave integer quadratic programming
- The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
- The multilinear polytope for acyclic hypergraphs
- The Running Intersection Relaxation of the Multilinear Polytope
- The width and integer optimization on simplices with bounded minors of the constraint matrices
- Tight complexity lower bounds for integer linear programming with few constraints
- Transversal numbers over subsets of linear spaces
- Trivial integer programs unsolvable by branch-and-bound
Cited in
(6)- The computational complexity of maximization and integration
- Integer complexity: algorithms and computational results
- Information complexity of mixed-integer convex optimization
- Equalizer zero-determinant strategy in discounted repeated Stackelberg asymmetric game
- Reducing the large set threshold for Oertel's conjecture on the mixed-integer volume
- Information complexity of mixed-integer convex optimization
This page was built for publication: Complexity of optimizing over the integers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6160281)
