LinOpt - Linear Optimization Library

Background

There's something I find genuinely interesting about where formal mathematical optimization came from. George Dantzig developed the simplex algorithm in 1947, just after WWII, while working as a mathematician for the US Air Force. The problems driving it weren't abstract — the military had real planning questions: how do you move supplies through a logistics network efficiently? How do you allocate resources across competing needs without waste? One of the early demonstrations of the method was the Stigler diet problem (1945), which asked what the cheapest possible diet was that still met minimum nutritional requirements for a person. The Berlin Airlift in 1948 was optimized using linear programming. It's one of those cases where mathematicians were handed genuinely hard operational problems and the resulting tools turned out to be foundational for decades of work that had nothing to do with the military.

I wrote LinOpt in grad school as an implementation of the simplex algorithm from scratch — a C++ library for solving linear programs and doing polyhedral computations, with arbitrary-precision arithmetic support through GMP and vertex enumeration through LRS. It could use some modernization, but the core is solid.

Architecture

Component	Purpose	Key Features
`mat<T>`	Matrix operations	Determinant, inverse, row operations, LRS integration
`vec<T>`	Vector operations	Element-wise operations, slicing, concatenation
`optim<T>`	LP solver	Two-phase simplex, pivot operations, tableau management
`polytope<T>`	Polyhedral geometry	Vertex enumeration, facet computation, H-representation
`kvp<T>`	Key-value storage	Associative structures for optimization bookkeeping

The whole thing is templated — mat<double> for speed, mat<mpq_class> when you need exact rational arithmetic via GMP. The LRS integration is a direct C interface without wrapper overhead, which matters for the polyhedral computations where you're enumerating vertices of potentially large polytopes.

Usage

CMake setup

CMake Configuration CMake

find_package(GMP REQUIRED)

include_directories(
    ${CMAKE_SOURCE_DIR}/src
    ${CMAKE_SOURCE_DIR}/lrslib-071
)

target_link_libraries(myapp linopt lrs GMP::GMP)

Solving a linear program

LP Solver C++

// Define constraint matrix H and objective vector c
mat<double> H(2, 3);
H(0, 0, 1); H(0, 1, -1); H(0, 2, 0);
H(1, 0, 1); H(1, 1, 0); H(1, 2, -1);

vec<double> c(H.size_x);
c.set(0, 0); c.set(1, -1); c.set(2, -1);

optim<double> o(H, c);
vec<double> solution = (o.simplex()).trunc(0, H.size_x-1);

Matrix operations

Matrix Computations C++

mat<double> A(3, 3);
A.identity();

mat<double> B = A.transpose();
double det = A.det();

A.row_swap(0, 1);
A.row_add(0, 1, 2.0);

Technical details

The solver is a two-phase simplex — phase one finds a feasible basis when the origin isn't feasible, phase two optimizes from there. Matrices are stored in 1D arrays with column-major ordering for cache locality. A few key build parameters worth knowing about:

Key Build Flags CMake

CMAKE_CXX_FLAGS_RELEASE = "-O3 -DNDEBUG -DLRS_QUIET"

-DTOL 0.000000000000001    # Tolerance for zero comparisons
-DFUDGE 0.001              # Equality constraint fudging
-DMAXITER 100000           # Maximum simplex iterations

Dependencies: GMP 6.0+ for arbitrary-precision arithmetic, LRS 7.1 for reverse-search vertex enumeration, CMake 3.16+, C++17.