1

I'm implementing some algorithms in C++ and I need to solve some linear programs as an intermediate step within the algorithm.

I've managed to get the linear_solver from google or-ools working, as well as glpk.

My issue is that I need to work with and solve LPs with very high precision integer types - more than 256 bits - in order for the algorithm to be correct (it's complicated but the algorithm can give very incorrect answers if less precision is used). At the moment I'm using mpz_class and mpf_class from gmp to store my numbers.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
angusjoshi
  • 11
  • 2
  • I don't know an answer to your question, but just wanted to mention that although increased precision has its uses, we typically don't see as much benefit as one might expect - it will give you a handful more orders of magnitude of correct calculations and that's it. Mileage may very, but people are typically far better off reformulating the problem, trying to scale it well, and/or using a solver with good numerics. – Nikos Kazazakis Feb 12 '24 at 10:13

2 Answers2

0

A similar question has been asked here. The answers reference a number of exact solvers. I don't know if any solver supports higher but limited precision instead of exact.

GLPK itself supports exact arithmetic. It may be more difficult to use from the C++ interface than the command line, but is documented in the API.

Ggouvine
  • 1,877
  • 7
  • 13
0

The Soplex solver is a simplex-based LP solver, available as a C++ library. It supports regular (double precision) input, quad precision computation, and can provide exact solutions using iterative refinement and rational exact arithmetic.

While I have never used it myself directly, it is the default LP solver in SCIP. I would recommend checking the documentation to see how you can use the higher-precision functionality.

mtanneau
  • 4,123
  • 11
  • 24