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.

We study two techniques to obtain new families of classical and general Dual-Feasible Functions: A conversion from minimal Gomory--Johnson functions; and computer-based search using polyhedral computation and an automatic maximality and extremality test.

In this note we announce the availability of an electronic compendium of extreme functions for Gomory--Johnson's infinite group problem. These functions serve as the strongest cut-generating functions for integer linear optimization problems. We also close several gaps in the literature.

We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory--Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand's two-sided discontinuous extreme functions and Basu--Hildebrand--K\"{o}ppe's piecewise linear extreme function with irrational breakpoints. The new function only admits piecewise microperiodic perturbations. We present an algorithm for computations with a restricted class of such perturbations.

We investigate three competing notions that generalize the notion of a facet of finite-dimensional polyhedra to the infinite-dimensional Gomory-Johnson model. These notions were known to coincide for continuous piecewise linear functions with rational breakpoints. We show that two of the notions, extreme functions and facets, coincide for the case of continuous piecewise linear functions, removing the hypothesis regarding rational breakpoints. We then separate the three notions using discontinuous examples.

Using a metaprogramming technique and semialgebraic computations, we provide computer-based proofs for old and new cutting-plane theorems in Gomory--Johnson's model of cut generating functions.

We study the integer minimization of a quasiconvex polynomial with quasiconvex polynomial constraints. We propose a new algorithm that is an improvement upon the best known algorithm due to Heinz (Journal of Complexity, 2005). This improvement is achieved by applying a new modern Lenstra-type algorithm, finding optimal ellipsoid roundings, and considering sparse encodings of polynomials. For the bounded case, our algorithm attains a time-complexity of s (r l M d)^{O(1)} 2^{2n log_2(n) + O(n)} when M is a bound on the number of monomials in each polynomial and r is the binary encoding length of a bound on the feasible region. In the general case, s l^{O(1)} d^{O(n)} 2^{2n log_2(n) +O(n)}. In each we assume d>= 2 is a bound on the total degree of the polynomials and l bounds the maximum binary encoding size of the input.

We describe new computer-based search strategies for extreme functions for the Gomory--Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions.

We study a mixed integer linear program with m integer variables and k non-negative continuous variables in the form of the relaxation of the corner polyhedron that was introduced by Andersen, Louveaux, Weismantel and Wolsey [Inequalities from two rows of a simplex tableau, Proc. IPCO 2007, LNCS, vol. 4513, Springer, pp. 1--15]. We describe the facets of this mixed integer linear program via the extreme points of a well-defined polyhedron. We then utilize this description to give polynomial time algorithms to derive valid inequalities with optimal l_p norm for arbitrary, but fixed m. For the case of m=2, we give a refinement and a new proof of a characterization of the facets by Cornuejols and Margot [On the facets of mixed integer programs with two integer variables and two constraints, Math. Programming 120 (2009), 429--456]. The key point of our approach is that the conditions are much more explicit and can be tested in a more direct manner, removing the need for a reduction algorithm. These results allow us to show that the relaxed corner polyhedron has only polynomially many facets.

For given matrix $A\in\Z^{d\times n}$, the set $P_{b}=\{z:Az=b,z\in\Z^n_+\}$ describes the preimage or fiber of $b\in\Z^d$ under the $\Z$-linear map $f_A:\Z^n_+\to\Z^d$, $x\mapsto Ax$. The fiber $P_{b}$ is called atomic, if $P_{b}=P_{b_1}+P_{b_2}$ implies $b=b_1$ or $b=b_2$. In this paper we present a novel algorithm to compute such atomic fibers. An algorithmic solution to appearing subproblems, computational examples and applications are included as well.