Large-Number Optimization: Exact-Arithmetic Mathematical Programming with Integers and Fractions Beyond Any Bit Limits

Abstract

Mathematical optimization, in both continuous and discrete forms, is well established and widely applied. This work addresses a gap in the literature by focusing on large-number optimization, where integers or fractions with hundreds of digits occur in decision variables, objective functions, or constraints. Such problems challenge standard optimization tools, particularly when exact solutions are required. The suitability of computer algebra systems and high-precision arithmetic software for large-number optimization problems is discussed. Our first contribution is the development of Python implementations of an exact Simplex algorithm and a Branch-and-Bound algorithm for integer linear programming, capable of handling arbitrarily large integers. To test these implementations for correctness, analytic optimal solutions for nine specifically constructed linear, integer linear, and quadratic mixed-integer programming problems are derived. These examples are used to test and verify the developed software and can also serve as benchmarks for future research in large-number optimization. The second contribution concerns constructing partially increasing subsequences of the Collatz sequence. Motivated by this example, we quickly encountered the limits of commercial mixed-integer solvers and instead solved Diophantine equations or applied modular arithmetic techniques to obtain partial Collatz sequences. For any given number J, we obtain a sequence that begins at $2^J-1$ and repeats J times the pattern ud: multiply by $3x_j+1$ and then divide by 2. Further partially decreasing sequences are designed, which follow the pattern of multiplying by $3x_j+1$ and then dividing by $2^m$. The most general J-times increasing patterns (ududd, udududd, …, ududududddd) are constructed using analytic and semi-analytic methods that exploit modular arithmetic in combination with optimization techniques.