Optimization models are built in a variety of modeling languages and solved by a variety of solvers, but once a solution exists, the information needed to understand it is fragmented: each solver exposes a partial, differently named set of native diagnostics, and the modeling language has already canonicalized the formulation the user wrote. We present … Read more
We present the architecture and central parts of the FICO Xpress Global optimization solver. In particular, we focus on how we built a global solver for the general class of mixed-integer nonlinear optimization problems by combining and extending two existing components of the FICO Xpress Solver, namely the mixed-integer linear optimization solver and the successive … Read more
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