How ergo-code/highs works
Main components
• Core Solver Engine – The heart of HiGHS resides in the “src” directory. This includes multiple submodules such as:
– lp_data: Data structures for models, options, and core routines.
– simplex: The revised simplex solvers for LP.
– ipm (interior point methods): Implements the interior point algorithms.
– mip: Mixed Integer Programming components.
– qpsolver and pdlp: Modules for quadratic programming and advanced linear programming.
– presolve: Components to precondition, simplify, or analyze the optimization model.
– model and parallel: Support for model construction and parallel execution.
• Interfaces – Found in “src/interfaces” (and mirrored by files under “app” and “examples”). They provide language bindings for C, C#, Python, and Fortran. These components serve as entry points for external usage.
• I/O and File Readers – Located in “src/io”, these components handle reading LP, MPS and other file formats.
• Command Line & Demo – The “app” directory contains files like RunHighs.cpp and CLI11.hpp that support a command-line interface and possibly a web demo (“highs_webdemo_shell.html”), which acts as an additional frontend.
• Build and Test Infrastructure – Multiple build system files (CMakeLists.txt, bazel files, meson.build), custom check routines under the “check” directory, and extensive GitHub Actions workflows (under “.github/workflows”) show that the project has robust CI/CD and testing in place.
• External Dependencies – The “extern” folder includes third-party libraries such as pdqsort, catch.hpp, and zstr for additional functionality.
• Documentation – The “docs” directory maintains generated documentation alongside scripts to produce API and user documentation.
• Examples – The “examples” directory offers numerous use case scripts in C, C++, Python, etc., illustrating how to interface with the solver.
Out relationships and interactions
• Input Flow – Data (e.g., MPS/LP files) is ingested through I/O modules (in “src/io”) and preprocessed (using “src/presolve”).
• Core Processing – The processed data is then sent to the optimization solvers (simplex, ipm, mip, qpsolver, etc.) that perform the heavy lifting.
• Output Flow – Results are stored or output via designated I/O mechanisms.
• Interfaces – They wrap around the core library, allowing different programming languages and applications to invoke the solver. They communicate with the core engine by using shared headers (e.g., “Highs.h” in “src/”) and specialized interface files.
• Build/Integration – The multiple build scripts and configuration files (CMakeLists.txt, BUILD.bazel, meson.build) indicate that the system is designed for cross-platform builds and integration testing. CI pipelines coordinate the building, testing, and code quality checks.
Design patterns and design principles
• Layered Architecture – Separate layers for the core optimization logic, I/O processing, and user interfaces.
• Modular Design – Each functionality (simplex, ipm, mip, etc.) is encapsulated in its own module with organized directories.
• Multi-interface Support – Separate modules for C, C#, Fortran, and Python interact with the central engine, suggesting the use of thin wrapper patterns.
• Build System Abstraction – Support for multiple build systems (CMake, Meson, Bazel) indicates an emphasis on portability and maintainability.
Relevant technologies and frameworks
• Languages: Mainly C++ (with some C), and interfaces for Python (highspy), C, C#, and Fortran.
• Build Tools: CMake, Bazel, Meson, and Nix (for reproducibility).
• Testing and CI: Extensive suite of unit tests (in “check” and “tests”) and CI workflows configured in GitHub Actions.
• External Libraries: Utilizes lightweight libraries from “extern” (e.g., catch.hpp for testing and pdqsort for efficient sorting).
Summarize the key architectural components
• Frontend/CLI: Handles command line input and demo (in “app”).
• Core Computation Layer: Contains the optimization algorithms in “src” split into various modules like lp_data, simplex, ipm, mip, etc.
• I/O Module: Reads, writes, and preprocesses optimization models.
• Multi-language Interfaces: Wrap around the core solver to support different programming environments.
• Build and Test Infrastructure: Manages CI/CD and cross-platform builds.
• Documentation and Examples: Provide user guidance and example usage.