LinOpt

A high-performance C++ library for linear optimization and polyhedral computations

View on GitHub

Project Overview

LinOpt Vector Test Output

LinOpt is a comprehensive C++ library designed for solving linear optimization problems and performing polyhedral computations with high precision and performance.

The project provides a complete toolkit for:

  • Linear Programming: Simplex algorithm implementation with two-phase optimization
  • Matrix Operations: High-performance matrix and vector computations with arbitrary precision
  • Polyhedral Geometry: Integration with LRS library for vertex enumeration and facet computation
  • Numerical Precision: Support for both floating-point and rational arithmetic using GMP

Key Innovation

What makes this project particularly interesting is its seamless integration of modern C++ templates with the venerable LRS (lrslib) library, providing both high-level abstractions and low-level performance for computational geometry and optimization problems.

System Architecture

LinOpt employs a layered architecture that combines template-based C++ abstractions with high-performance numerical libraries.

Core Components

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

Design Patterns

  • Template Metaprogramming: Generic programming for type-safe numerical computations
  • RAII: Resource management through constructors and destructors
  • Operator Overloading: Intuitive mathematical syntax for matrix/vector operations
  • External Library Integration: Seamless C interface to LRS and GMP libraries

Key Features

1. Linear Programming Solver

Comprehensive implementation of the simplex algorithm:

  • Two-Phase Optimization: Automatic handling of infeasible starting points
  • Mixed Constraints: Support for both ≤ and ≥ inequality constraints
  • Artificial Variables: Automatic introduction and elimination of artificial variables
  • Pivot Operations: Efficient tableau updates and basis management

2. High-Performance Matrix Operations

Optimized matrix and vector computations:

  • Arbitrary Precision: Support for both double and GMP rational arithmetic
  • Memory Efficiency: 1D array storage with optimized access patterns
  • Linear Algebra: Determinant, inverse, eigenvalue computations
  • Row Operations: Elementary row operations for matrix manipulation

3. Polyhedral Geometry Integration

Advanced computational geometry capabilities:

  • LRS Integration: Direct interface to lrslib for vertex enumeration
  • H-Representation: Support for half-space representations of polytopes
  • V-Representation: Vertex-based polyhedral descriptions
  • Dual Descriptions: Conversion between different polyhedral representations

4. Numerical Precision and Stability

Robust numerical computations:

  • GMP Integration: Arbitrary-precision arithmetic for exact computations
  • Floating-Point Control: Configurable tolerance and precision settings
  • Numerical Stability: Careful handling of near-zero values and degeneracy
  • Error Handling: Comprehensive error checking and validation

Usage Examples

Basic Setup

CMake Configuration CMake 
# Find required packages
find_package(GMP REQUIRED)

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

# Link libraries
target_link_libraries(myapp linopt lrs GMP::GMP)

Linear Programming Example

Simple 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);

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

Matrix Operations

Matrix Computations C++ 
// Create and manipulate matrices
mat<double> A(3, 3);
A.identity();  // Create identity matrix

// Matrix operations
mat<double> B = A.transpose();
double det = A.det();  // Compute determinant

// Row and column operations
A.row_swap(0, 1);
A.row_add(0, 1, 2.0);

Technical Implementation

Technology Stack

LinOpt is built using modern C++ with integration to established numerical libraries:

  • C++17: Modern C++ features for template metaprogramming and type safety
  • GMP (GNU Multiple Precision): Arbitrary-precision arithmetic library
  • LRS (lrslib): Library for reverse search vertex enumeration
  • CMake: Cross-platform build system configuration

Performance Optimizations

Optimization Implementation Benefit
Memory Layout 1D array storage with column-major ordering Improved cache locality and memory access patterns
Template Specialization Optimized implementations for common data types Reduced runtime overhead and better compiler optimization
LRS Integration Direct C interface to lrslib without wrapper overhead Maximum performance for polyhedral computations
Compile-time Configuration Configurable precision and tolerance via preprocessor Flexible trade-offs between speed and accuracy

Dependencies

  • GMP 6.0+: GNU Multiple Precision Arithmetic Library for exact computations
  • LRS 7.1: Library for reverse search vertex enumeration algorithms
  • CMake 3.16+: Build system for cross-platform compilation
  • C++17 Compiler: GCC 7+, Clang 5+, or MSVC 2017+

Build Configuration

Key Build Flags CMake 
# Compiler flags for different build types
CMAKE_CXX_FLAGS_DEBUG = "-g -O0 -Wall -Wextra -DDEBUG"
CMAKE_CXX_FLAGS_RELEASE = "-O3 -DNDEBUG -DLRS_QUIET"

# Key preprocessor definitions
-DTOL 0.000000000000001    # Tolerance for zero comparisons
-DFUDGE 0.001              # Equality constraint fudging
-DMAXITER 100000           # Maximum simplex iterations
-DUSE_OUTPUT_FILE          # Enable file output in drivers

Testing Framework

Comprehensive unit testing ensures reliability:

  • Vector Tests: Element-wise operations, slicing, and concatenation
  • Matrix Tests: Linear algebra operations, determinant, and inverse
  • KVP Tests: Key-value pair storage and retrieval
  • Optimization Tests: Linear programming solver validation