Algorithms & Software

Numerica Key Code


Consider a project involving packing ellipsoids of given (but varying) dimensions into a finite container in a way that minimizes the maximum overlap between adjacent ellipsoids. A bilevel optimization algorithm is described for finding local solutions, for both the general case and the easier special case in which the ellipsoids are spheres. Algorithm and analysis tools from semi-definite programming and trust-region methods are key to the approach. The goal is to apply the method to the problem of chromosome arrangement in cell nuclei, and compare our results with the experimental observations reported in the biological literature.


There is an arms race to perform increasingly sophisticated data analysis on ever more varied types of data (text, audio, video, OCR, sensor data, etc.). Current data processing systems typically assume that the data have rigid, precise semantics, which these new data sources do not possess. On the other hand, many of the state-of-the-art approaches […]


Jellyfish is an algorithm for solving data-processing problems with matrix-valued decision variables regularized to have low rank. Particular examples of problems solvable by Jellyfish include matrix completion problems and least-squares problems regularized by the nuclear norm or γ2-norm. Jellyfish implements a projected incremental gradient method with a biased, random ordering of the increments. This biased […]

Mixed-Integer Quadratic Optimization: Algorithms and Complexity

Mixed-integer quadratic programming (MIQP) is the simplest yet arguably the most important class of mixed-integer nonlinear programming (MINLP) that contains two major sources of difficulties: discrete decision variables and nonlinearity in the objective function. Not only many important applications can be naturally modeled as MIQPs, but a variety of more general MINLPs can be reformulated […]


The PATH solver for mixed complementarity problems (MCPs) was introduced in 1995 and has since become the standard against which new MCP solvers are compared. License The version that is downloadable from here (i.e. the file in this directory) is free, but is limited to problems with no more than 300 variables and 2,000 […]

Structural properties and strong relaxations for mixed integer polynomial optimization

Research in nonconvex nonlinear programming (NLP) and mixed-integer nonlinear programming (MINLP) has witnessed a significant growth at the theoretical, algorithmic and software levels over the last few years. While these new classes of algorithms have already had a remarkable impact across science, engineering, and economics, there exist a variety of important applications that these methods […]