Algorithm Index

This page provides a cross-reference of algorithms documented across the COIN-OR libraries. Click any algorithm to see its mathematical formulation, complexity analysis, and all implementations.

Presolve Reductions

• Bound Tightening (1 impl) - CoinUtils
• Branch-and-Bound Node Management (1 impl) - Cbc
• Branch-and-Bound Tree Search (1 impl) - CoinUtils
• Direct MIQCQP branch-and-bound (1 impl) - SHOT
• Doubleton Elimination (1 impl) - CoinUtils
• Dual Bound Propagation (1 impl) - CoinUtils
• Forcing Constraint Detection (1 impl) - CoinUtils
• LP Presolve (Preprocessing) (1 impl) - Clp
• LP Presolve - simplifies LP before solving via reversible transforms (1 impl) - CoinUtils
• Optimization-Based Bound Tightening (1 impl) - SHOT
• Singleton Column/Row Elimination (1 impl) - CoinUtils
• Slack Elimination (eliminateSlack) (1 impl) - Cgl
• Tripleton Elimination (1 impl) - CoinUtils
• Variable Substitution (Non-Singleton) (1 impl) - CoinUtils

Matrix Factorization

• ABC (Alternative Basis Code) LU Factorization (1 impl) - Clp
• Dense LU Factorization (LAPACK-style) (1 impl) - CoinUtils
• LU Factorization with Forrest-Tomlin Updates (1 impl) - Clp
• LU factorization with Markowitz pivot selection (1 impl) - CoinUtils
• Left-looking LU with BTF preprocessing and partial pivoting (1 impl) - SuiteSparse
• Multifrontal LU with threshold partial pivoting (1 impl) - SuiteSparse
• Sparse LDL' factorization (up-looking) (1 impl) - SuiteSparse
• Sparse LU with Markowitz Pivoting (1 impl) - CoinUtils

Simplex Method

• Bron-Kerbosch with pivoting for weighted cliques (1 impl) - CoinUtils
• Dual Simplex Method (1 impl) - Clp
• Primal Simplex Method (1 impl) - Clp
• Simplex Basis Warm Start (1 impl) - CoinUtils
• Simplex Method for Linear Programming (1 impl) - Clp
• Steepest Edge Dual Pivot Selection (1 impl) - Clp
• Steepest Edge and Devex Primal Pivot Selection (1 impl) - Clp

Interior Point Methods

• Direct interior point NLP solve (1 impl) - SHOT
• Interior Point Method (Barrier Method) (1 impl) - Clp
• Interior Point Method via Ipopt (1 impl) - Gravity

Branch and Bound

• Adaptive Hybrid Node Selection (1 impl) - Cbc
• Branch-and-Cut (B&C) for Mixed-Integer Programming (1 impl) - Cbc
• Branch-and-cut with lazy ESH constraints (1 impl) - SHOT
• Branching Variable Selection Strategies (1 impl) - Cbc
• Extended Cutting Plane (Westerlund-Pettersson) (1 impl) - SHOT
• Hot-Start Optimization for Strong Branching (1 impl) - Clp
• Iterative cutting plane for convex minimax (1 impl) - SHOT
• Lift-and-Project Cutting Planes (1 impl) - Cgl
• Price-and-Cut Hybrid (generateVars + generateCuts) (1 impl) - Dip
• Root Node vs. Tree Strategy (1 impl) - Cbc
• Search Tree Management with Priority Heap (1 impl) - Cbc
• Stern-Brocot tree / mediant search for best rational approximation (1 impl) - CoinUtils

Primal Heuristics

• Feasibility Pump (FP) (1 impl) - Cbc
• Greedy Cover Heuristic (findGreedyCover) (1 impl) - Cgl
• MIP Primal Heuristics Framework (1 impl) - Cbc

Conflict Analysis

• Clique Storage (1 impl) - CoinUtils
• Conflict Graph Construction (1 impl) - CoinUtils
• Greedy Maximal Clique (greedy_maximal_clique) (1 impl) - Cgl

Data Structures

• Compressed Sparse Column/Row (CSC/CSR) format (1 impl) - CoinUtils
• Dense Vector Storage (1 impl) - CoinUtils
• Hyper-sparse Computation (1 impl) - HiGHS
• Indexed sparse vector - hybrid sparse/dense storage (1 impl) - CoinUtils
• Merge-style sparse dot product (1 impl) - CoinUtils
• Sparse Matrix Operations (1 impl) - SuiteSparse

File I/O

• LP File Parsing (1 impl) - CoinUtils
• LP Method Selection (LPMethod enum) (1 impl) - Cbc
• MPS File Parsing (1 impl) - CoinUtils

Other Algorithms

• Approximate Minimum Degree (AMD) (1 impl) - SuiteSparse
• Convergence Properties (1 impl) - SHOT
• Data Layout Optimization (1 impl) - Clp
• Design Pattern: Abstract Factory + Strategy (1 impl) - Osi
• Duff's device - Tom Duff's loop unrolling technique that uses switch (1 impl) - CoinUtils
• Duplicate Detection via Random Hashing (1 impl) - CoinUtils
• Empty Row/Column Removal (1 impl) - CoinUtils
• Essential for Extended Supporting Hyperplane (ESH) method (1 impl) - SHOT
• Extended Supporting Hyperplane (ESH) method adds (1 impl) - SHOT
• Extended Supporting Hyperplane (Kronqvist 2016) (1 impl) - SHOT
• Fixed Variable Removal (1 impl) - CoinUtils
• Floating-Point Comparison (1 impl) - CoinUtils
• Forward mode computes derivatives in the direction of inputs. (1 impl) - CppAD
• Function Pointer Dispatch (scatterStruct) (1 impl) - Clp
• Implied Free Variable Detection (1 impl) - CoinUtils
• Integrality Distance Threshold (away_) (1 impl) - Cgl
• Linear Solver Selection (SymLinearSolverFactory) (1 impl) - Ipopt
• MIP Solution Pool (getAllVariableSolutions) (1 impl) - SHOT
• MIP Solving (1 impl) - HiGHS
• MIP Start (Warm Starting) (addMIPStart) (1 impl) - SHOT
• Message Handling System (1 impl) - CoinUtils
• Model Construction Interface (1 impl) - CoinUtils
• Monotone Min-Heap (1 impl) - CoinUtils
• Objective Propagation (1 impl) - HiGHS
• Online Active Set Strategy (1 impl) - qpOASES
• Online Active Set Strategy - works well for model (1 impl) - qpOASES
• Operator overloading records a "tape" of operations. (1 impl) - CppAD
• PAMI - Parallel Minor Iterations (iterateMulti) (1 impl) - HiGHS
• Parallel Array Sorting (1 impl) - CoinUtils
• Preprocessing Pipeline (IPPMode) (1 impl) - Cbc
• Reverse mode automatic differentiation (1 impl) - ADOL-C
• Row Classification (determineOneRowType) (1 impl) - Cgl
• SYMAMD (Symmetric AMD using COLAMD) (1 impl) - SuiteSparse
• Solves KKT conditions directly when active set is known. (1 impl) - qpOASES
• Sparsification (sparsify) (1 impl) - HiGHS
• Sparsity Pattern Extraction (getConstraintsJacobianSparsityPattern) (1 impl) - SHOT
• Standard ESH outer approximation (1 impl) - SHOT
• Tarjan's Strongly Connected Components (1 impl) - SuiteSparse
• Update/Downdate (rank-k modification) (1 impl) - SuiteSparse
• Warm Starting (setStartingPoint) (1 impl) - SHOT
• Warm-Starting Protocol (1 impl) - Clp