On the complexity of nonlinear mixed-integer optimization

DOI10.1007/978-1-4614-1927-3_19MaRDI QIDQ2897310zbMATH OpenOpenAlexFDO

Authors Matthias Köppe

Publication date 10 July 2012

Published in Mixed Integer Nonlinear Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.4895

Mathematics Subject Classification ID

Mixed integer programming (90C11) Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: This is a survey on the computational complexity of nonlinear mixed-integer optimization. It highlights a selection of important topics, ranging from incomputability results that arise from number theory and logic, to recently obtained fully polynomial time approximation schemes in fixed dimension, and to strongly polynomial-time algorithms for special cases.

Recommendations

• Undecidability and hardness in mixed-integer nonlinear programming
• Nonlinear integer programming
• scientific article; zbMATH DE number 757674
• Integer Polynomial Optimization in Fixed Dimension
• scientific article; zbMATH DE number 846225

Cited in

(22)

• A note on a pair of nonlinear mixed integer programming problems
• Nonlinear integer programming by Darwin and Boltzmann mixed strategy
• Knapsack with variable weights satisfying linear constraints
• Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held October 18--24, 2015
• The mathematics of playing golf, or: A new class of difficult nonlinear mixed integer programs
• The complexity of approximating a nonlinear program
• Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem
• Optimal dynamic formation control of multi-agent systems in constrained environments
• On the complexity of quasiconvex integer minimization problem
• Minimizing cubic and homogeneous polynomials over integers in the plane
• scientific article; zbMATH DE number 1264409 (Why is no real title available?)
• scientific article; zbMATH DE number 976325 (Why is no real title available?)
• Optimizing a multi-stage production/inventory system by DC programming based approaches
• Short Presburger Arithmetic Is Hard
• Mixed-integer convex representability
• Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
• Intractability of approximate multi-dimensional nonlinear optimization on independence systems
• Undecidability and hardness in mixed-integer nonlinear programming
• Some graph optimization problems with weights satisfying linear constraints
• Related machine scheduling with machine speeds satisfying linear constraints
• Complexity of optimizing over the integers
• Scheduling and fixed-parameter tractability

This page was built for publication: On the complexity of nonlinear mixed-integer optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2897310)