Convex Over and Under ENvelopes for Nonlinear Estimation (Couenne) is an

open-source Open source is source code that is made freely available for possible modification and redistribution. Products include permission to use the source code, design documents, or content of the product. The open-source model is a decentralized sof ...

library for solving

global optimization Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the max ...

problems, also termed mixed integer nonlinear optimization problems. A global optimization problem requires to minimize a

function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-orie ...

, called

objective function In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cos ...

, subject to a set of constraints. Both the objective function and the constraints might be nonlinear and nonconvex. For solving these problems, Couenne uses a reformulation procedure and provides a

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

approximation of any nonconvex optimization problem.P. Belotti, J. Lee, L. Liberti, F. Margot, & A. Wächter (2009), Branching and bounds tightening techniques for non-convex MINLP. Optimization Methods & Software, 24(4-5), 597-634. Couenne is an implementation of a

branch-and-bound Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutio ...

where every subproblem is solved by constructing a

relaxation to obtain a lower bound. Branching may occur at both continuous and integer variables, which is necessary in global optimization problems. It requires the input to be specified in A Mathematical Programming Language (

AMPL AMPL (A Mathematical Programming Language) is an algebraic modeling language to describe and solve high-complexity problems for large-scale mathematical computing (i.e., large-scale optimization and scheduling-type problems). It was developed b ...

) .nl format, so as to be used from AMPL, and writes as an output a file .sol containing the best solution found until that moment (if the optimization is interrupted) or the global optimum if it completes without interruption. The development of Couenne began in 2006 within a collaboration between IBM and

Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...

. It is

open-source software Open-source software (OSS) is computer software that is released under a license in which the copyright holder grants users the rights to use, study, change, and distribute the software and its source code to anyone and for any purpose. Ope ...

and is currently released under the

Eclipse Public License The Eclipse Public License (EPL) is a free and open source software license most notably used for the Eclipse IDE and other projects by the Eclipse Foundation. It replaces the Common Public License (CPL) and removes certain terms relating to ...

v1.0. The source code is available for download in the Computational Infrastructure for Operations Research

COIN-OR Computational Infrastructure for Operations Research (COIN-OR), is a project that aims to "create for mathematical software what the open literature is for mathematical theory." The open literature (e.g., a research journal) provides the operat ...

repository and on GitHub. Couenne uses other packages both in COIN-OR ( CBC, CLP, COIN-OR OSI, COIN-OR Bonmin, COIN-OR Cgl, Interior Point OPTimizer (

IPOPT IPOPT, short for "Interior Point OPTimizer, pronounced I-P-Opt", is a software library for large scale nonlinear optimization of continuous systems. It is written in Fortran and C and is released under the EPL (formerly CPL). IPOPT implement ...

)) and outside (

LAPACK LAPACK ("Linear Algebra Package") is a standard software library for numerical linear algebra. It provides routines for solving systems of linear equations and linear least squares, eigenvalue problems, and singular value decomposition. It al ...

Basic Linear Algebra Subprograms Basic Linear Algebra Subprograms (BLAS) is a specification that prescribes a set of low-level routines for performing common linear algebra operations such as vector addition, scalar multiplication, dot products, linear combinations, and matrix ...

(BLAS), MUltifrontal Massively Parallel sparse direct Solver (

MUMPS MUMPS ("Massachusetts General Hospital Utility Multi-Programming System"), or M, is an imperative, high-level programming language with an integrated transaction processing key–value database. It was originally developed at Massachusetts Gen ...

), Nauty, Solving Constraint Integer Programs ( SCIP), SoPlex).

References

External links

*
Source code (trunk)

Project page

User manual
{{Mathematical optimization software Mathematical optimization software Numerical software

See also

References

External links