Mixed-Integer Quadratic Optimization: Complexity, Algorithms and Computing

Mixed-Integer Nonlinear Optimization is the mother of all deterministic optimization models. As such, it has enormous modeling power, with applications in all kinds of areas like manufacturing and transportation logistics, design of water and gas networks, chemical engineering, portfolio optimization, etc. But of course in its full generality, it is foolhardy to consider algorithms and meaningful positive theoretical results. On the other hand, there are many well-known positive results for the linear case, so it is natural to seek to build up from the linear case, to get positive results (both theoretical and computational) for broader models. Natural extensions involve convexity and separability, and their relatives, and polynomials. A natural step in this direction involves attempting to exploit quadratic functions. I will survey some recent results in this direction --- both negative and positive complexity results and practical methods.