This paper offers a new standard, called MOSDEX (Mathematical Optimization Solver Data EXchange), for managing the interaction of data with solvers for mathematical optimization. The rationale for this standard is to take advantage of modern software tools that can efficiently handle very large datasets that have become the norm for data analytics in the past … Read more
Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into … Read more
An essential component in modern solvers for mixed-integer (linear) programs (MIPs) is the separation of additional inequalities (cutting planes) to tighten the linear programming relaxation. Various algorithmic decisions are necessary when integrating cutting plane methods into a branch-and-bound (B&B) solver as there is always the trade-off between the efficiency of the cuts and their costs, … Read more
MatQapNB is a MATLAB toolbox that implements a parallel branch-and-bound method using NewtBracket (the Newton bracketing method [4]) for its lower bounding procedure. It can solve small to medium scale Quadratic Assignment Problem (QAP) instances with dimension up to 30. MatQapNB was used in the numerical experiments on QAPs in the recent article “Solving challenging … Read more
We present GALINI, an open source solver for nonconvex mixed-integer quadratically-constrained quadratic programs formulated with the Python algebraic modeling library Pyomo. GALINI uses Pyomo to represent optimization problems and leverages the existing library ecosystem to implement different parts of the solver. GALINI includes a generic branch \& bound algorithm that can be use develop new … Read more
Many practical applications require the solution of numerically challenging linear programs (LPs) and mixed-integer programs (MIPs). Scaling is a widely used preconditioning technique that aims at reducing the error propagation of the involved linear systems, thereby improving the numerical behavior of the dual simplex algorithm and, consequently, LP-based branch-and-bound. A reliable scaling method often makes … Read more
In 2020, DIDO© turned 20! The software package emerged in 2001 as a basic, user-friendly MATLAB teaching tool to illustrate the various nuances of Pontryagin’s Principle but quickly rose to prominence in 2007 after NASA announced it had executed a globally optimal maneuver using DIDO. Since then, the toolbox has grown in applications well beyond … Read more
Different versions of polyhedral outer approximation is used by many algorithms for mixed-integer nonlinear programming (MINLP). While it has been demonstrated that such methods work well for convex MINLP, extending them to solve also nonconvex problems has been challenging. One solver based on outer linearization of the nonlinear feasible set of MINLP problems is the … Read more
We translate the algorithmic question of whether to linearize convex Mixed-Integer Quadratic Programming problems (MIQPs) into a classification task, and use machine learning (ML) techniques to tackle it. We represent MIQPs and the linearization decision by careful target and feature engineering. Computational experiments and evaluation metrics are designed to further incorporate the optimization knowledge in … Read more
JuMP is an open-source algebraic modeling language in the Julia language. In this work, we discuss a complete re-write of JuMP based on a novel abstract data structure, which we call \textit{MathOptInterface}, for representing instances of mathematical optimization problems. MathOptInterface is significantly more general than existing data structures in the literature, encompassing, for example, a … Read more