Abstract: We present an overview of noncommercial software tools for the solution of mixed-integer linear programs (MILPs). We first review solution methodologies for MILPs and then present an overview of the available software, including detailed descriptions of eight software packages available under open source or other noncommercial licenses. Each package is categorized as a black box solver, a callable library, a solver framework, or some combination of these. The distinguishing features of all eight packages are described. The paper concludes with case studies that illustrate the use of two of the solver frameworks to develop custom solvers for specific problem classes and with benchmarking of the six black box solvers.

Abstract: This chapter concerns the use of convex optimization in real-time embedded systems, in areas such as signal processing, automatic control, real-time estimation, real-time resource allocation and decision making, and fast automated trading. By ‘embedded’ we mean that the optimization algorithm is part of a larger, fully automated system, that executes automatically with newly arriving data or changing conditions, and without any human intervention or action. By ‘real-time’ we mean that the optimization algorithm executes much faster than a typical or generic method with a human in the loop, in times measured in milliseconds or microseconds for small and medium size problems, and (a few) seconds for larger problems. In real-time embedded convex optimization the same optimization problem is solved many times, with different data, often with a hard real-time deadline. In this chapter we propose an automatic code generation system for real-time embedded convex optimization. Such a system scans a description of the problem family, and performs much of the analysis and optimization of the algorithm, such as choosing variable orderings used with sparse factorizations and determining storage structures, at code generation time. Compiling the generated source code yields an extremely efficient custom solver for the problem family. We describe a preliminary implementation, built on the Python-based modeling framework CVXMOD, and give some timing results for several examples.

Abstract: We introduce a randomized algorithm for computing the minimal-norm solution to an underdetermined system of linear equations. Given an arbitrary full-rank matrix Am×n with m < n, any vector bm×1, and any positive real number “ less than 1, the procedure computes a vector xn×1 approximating to relative precision ” or better the vector pn×1 of minimal Euclidean norm satisfying Am×n pn×1 = bm×1. The algorithm typically requires O(mn log(pn/")+m3) floating-point operations, generally less than the O(m2 n) required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm.