lp_data

LP Data

This directory contains a rich collection of C++ libraries for handling Linear Programming (LP) data structures.

It provides core components for representing, manipulating, and solving linear programs, with a focus on efficient handling of sparse data and various utility functions for pre-processing and analysis.

Core Data Structures

This set of libraries provides the fundamental building blocks for representing and working with linear programming problems.

• lp_types.h: Defines common types and constants used throughout the linear programming solver.
• lp_data.h: Provides the main LinearProgram class for storing the complete data of a linear program, including the objective function, constraint matrix, and variable bounds.
• lp_utils.h: Contains basic utility functions for operations on fractional numbers and row/column vectors.

Sparse Data Representation

Given that large-scale linear programs are often sparse, this directory offers a suite of libraries for efficient sparse data handling.

• sparse.h: Implements data structures for sparse matrices, based on well-established references in the field of direct methods for sparse matrices.
• sparse_vector.h: Provides classes to represent sparse vectors efficiently.
• sparse_column.h & sparse_row.h: Specializations of sparse vectors for column-oriented and row-oriented matrix storage schemes.
• scattered_vector.h: Implements vectors that offer a sparse interface to what is internally a dense storage, which can be useful for certain computations.

LP Solvers and Utilities

A collection of tools for preprocessing, analyzing, and manipulating linear programs.

• matrix_scaler.h: Provides the SparseMatrixScaler class, which scales a SparseMatrix to improve numerical stability during the solving process.
• lp_decomposer.h: Implements a tool to decompose a large LinearProgram into several smaller, independent subproblems by identifying disconnected components in the constraint matrix.
• permutation.h: Contains utilities for handling row and column permutations on LP data structures.

Parsers and I/O Utilities

This group of libraries handles reading and writing LP data in various formats.

• lp_parser.h: A simple parser for creating a linear program from a string representation.
• mps_reader.h: A reader for the industry-standard MPS file format for mathematical programming problems.
• sol_reader.h: A reader for .sol files, which are used to specify solution values for a given model.
• proto_utils.h: Provides utilities to convert LinearProgram objects to and from the MPModelProto protobuf format.
• lp_print_utils.h: Contains utilities to display linear expressions in a human-readable way, including rational approximations.