OptimaX

OptimaX is a modern C++20 header-only library for mathematical optimization, linear programming, algorithmic duality, and decision structures. It bridges polyhedral optimization, network simplex, combinatorial assignments, and game-theoretic minimax models through coherent reusable abstractions. Internally, algorithms execute over contiguous index domains and cache-efficient vectors; externally, problems are formulated with clean mathematical semantics. The library has zero third-party dependencies beyond the C++ Standard Library.

While industrial solvers focus on massive sparse benchmarks with heavy external dependencies (BLAS/LAPACK, Fortran runtimes, Protobuf), OptimaX fills the unserved space in modern C++: a lightweight, zero-dependency, header-only engine designed for structural algorithms, exact duality certificates, and educational clarity.

---

Why OptimaX

• Pure ISO C++20 & Zero Dependencies: Header-only implementation requiring only a standard C++20 compiler (-std=c++20).
• First-Class Algorithmic Duality: Every linear program constructively produces its canonical dual alongside certified proofs of complementary slackness.
• Dual Numerical Engines: Supports standard floating-point (double) alongside an exact rational engine (rational<std::int64_t>) for zero-drift textbook verification and Farkas certificates.
• Combinatorial & Game-Theoretic Bridges: Native reductions from bipartite matching, min-cost network flows, and zero-sum matrix games directly to polyhedral linear programs.
• Cache-Conscious Mechanical Sympathy: Dense indexed execution layouts eliminating pointer chasing in core tableau pivots.

---

Architecture and Structural Bridges

flowchart TD
    A["Linear Program Formulation"] --> B["Primal / Dual Simplex"]
    A --> C["Duality & Certificates"]
    B --> C
    D["Combinatorial Assignment"] --> A
    E["Min-Cost Network Flow"] --> A
    F["Matrix Games (Minimax)"] --> A

    C --> G["Complementary Slackness Proofs"]
    C --> H["Farkas Infeasibility Certificates"]

Loading

---

Subsystem Roadmap

OptimaX is structured into seven modular subsystems under include/optimax/:

1. core/: Contiguous problem domains, dense matrix layouts, and exact rational arithmetic (rational<std::int64_t>).
2. simplex/: Primal simplex, dual simplex, revised simplex, and Bland's anti-cycling pivot selection.
3. duality/: Canonical dual program generators, complementary slackness verifiers, and Farkas certificates.
4. network/: Min-cost flow, network simplex, cycle-canceling, and successive shortest path algorithms.
5. combinatorial/: Assignment problem (Hungarian / Kuhn-Munkres in $O(n^3)$), transportation problem, and total unimodularity tests.
6. games/: Two-player zero-sum matrix games, minimax theorem, and optimal mixed strategy LP reductions.
7. concepts/: C++20 concepts for number types, matrix layouts, linear constraints, and optimization solvers.

---

Installation and Quick Start

CMake FetchContent

include(FetchContent)

FetchContent_Declare(
    OptimaX
    GIT_REPOSITORY https://github.com/nijuna/OptimaX.git
    GIT_TAG        main
)
FetchContent_MakeAvailable(OptimaX)

add_executable(my_project main.cpp)
target_link_libraries(my_project PRIVATE OptimaX::OptimaX)

Direct Header Inclusion

Add the include/ directory to your compiler search path:

g++ -std=c++20 -O2 -I/path/to/OptimaX/include main.cpp -o my_project

---

Build and Verification

Requirements

• ISO C++20 compliant compiler (GCC 11+, Clang 13+, MSVC 19.29+)
• Build systems: GNU Make or CMake 3.15+

Build Targets

# Compile and run core test suite
make test

# Compile and execute standalone examples
make examples

# Clean build artifacts
make clean

---

Repository Structure

OptimaX/
├── .github/
│   └── workflows/
│       └── ci.yml
├── CMakeLists.txt
├── Makefile
├── README.md
├── LICENSE
├── cmake/
│   └── OptimaXConfig.cmake.in
├── docs/
├── examples/
├── include/
│   └── optimax/
│       ├── optimax.hpp
│       ├── combinatorial/
│       ├── concepts/
│       ├── core/
│       ├── duality/
│       ├── games/
│       ├── network/
│       └── simplex/
└── tests/
    └── test_main.cpp

---

License

OptimaX is released under the MIT License.