Rational Conversion Guide

This guide covers the LXRationalConverter for converting floating-point coefficients to rational numbers, essential for integer-only solvers and exact arithmetic.

Overview

Many optimization solvers, particularly integer-only modes of solvers like GLPK, require exact rational arithmetic instead of floating-point numbers. The LXRationalConverter provides efficient algorithms to approximate floats as fractions with configurable precision.

Why Rational Conversion?

  • Integer-only solvers (GLPK, some CPLEX modes) require rational coefficients

  • Avoid floating-point precision errors in sensitive problems

  • Enable symbolic computation integration

  • Ensure reproducible results across platforms

Key Features:

  • Three approximation algorithms (Farey, Continued Fraction, Stern-Brocot)

  • Configurable maximum denominator for precision control

  • Batch conversion for coefficient dictionaries

  • Error tracking and algorithm comparison

  • Tolerance handling for float comparisons

Quick Start

Basic Conversion

from lumix.utils import LXRationalConverter

# Create converter
converter = LXRationalConverter(max_denominator=10000)

# Convert float to fraction
frac = converter.to_rational(3.14159)
print(frac)  # Fraction(355, 113)
print(f"Approximation: {float(frac):.6f}")  # 3.141593

Batch Conversion

# Convert multiple coefficients
coeffs = {
    "x1": 3.5,
    "x2": 2.333,
    "x3": 1.25,
    "x4": 0.666
}

int_coeffs, common_denom = converter.convert_coefficients(coeffs)

print(f"Integer coefficients: {int_coeffs}")
# {'x1': 42, 'x2': 28, 'x3': 15, 'x4': 8}

print(f"Common denominator: {common_denom}")
# 12

# Verify: int_coeffs[key] / common_denom ≈ coeffs[key]

Configuration Options

Maximum Denominator

Controls the trade-off between approximation accuracy and denominator size:

# Smaller denominator - faster, less accurate
converter = LXRationalConverter(max_denominator=100)
frac = converter.to_rational(3.14159)
print(frac)  # Fraction(22, 7) = 3.142857...

# Larger denominator - slower, more accurate
converter = LXRationalConverter(max_denominator=100000)
frac = converter.to_rational(3.14159)
print(frac)  # Fraction(355, 113) = 3.141593...

Guidelines:

  • Small denominators (< 1000): Fast, suitable for rough approximations

  • Medium denominators (1000-10000): Good balance (recommended default)

  • Large denominators (> 10000): High accuracy, slower computation

Approximation Method

Choose between three algorithms:

# Farey sequence (default, recommended)
converter = LXRationalConverter(method="farey")

# Continued fractions
converter = LXRationalConverter(method="continued_fraction")

# Stern-Brocot tree
converter = LXRationalConverter(method="stern_brocot")

Algorithm Comparison:

Method

Speed

Accuracy

Notes

Farey

⚡⚡⚡ Fastest

✓✓✓ Best

Recommended default

Continued Fraction

⚡⚡ Fast

✓✓✓ Best

Classic algorithm

Stern-Brocot

⚡⚡ Fast

✓✓✓ Best

Equivalent to Farey

Float Tolerance

Control tolerance for float comparisons:

# Default tolerance
converter = LXRationalConverter(float_tolerance=1e-9)

# Stricter tolerance
converter = LXRationalConverter(float_tolerance=1e-12)

# Looser tolerance
converter = LXRationalConverter(float_tolerance=1e-6)

Approximation Algorithms

Farey Sequence Method

The Farey method uses mediant approximation with floor/ceil optimization. It’s the fastest and recommended default.

Algorithm Overview:

  1. Initialize bounds with floor and ceiling of the target value

  2. Compute mediant: (n₁ + n₂) / (d₁ + d₂)

  3. Update bounds based on mediant position

  4. Repeat until denominator exceeds maximum

Example:

converter = LXRationalConverter(max_denominator=20, method="farey")
frac, error = converter.to_rational(3.14159, return_error=True)

print(f"Fraction: {frac}")        # 22/7
print(f"Value: {float(frac):.6f}") # 3.142857
print(f"Error: {error:.2e}")       # 1.27e-03

Continued Fraction Method

Classic continued fraction expansion algorithm. Good balance of speed and accuracy.

Algorithm Overview:

  1. Extract integer part and fractional part

  2. Build continued fraction representation

  3. Compute convergents until max denominator

Example:

converter = LXRationalConverter(method="continued_fraction")
frac = converter.to_rational(3.14159)
print(frac)  # Fraction(355, 113)

Stern-Brocot Tree Method

Binary search through the Stern-Brocot tree. Mathematically equivalent to Farey but offers alternative algorithmic framing.

Example:

converter = LXRationalConverter(method="stern_brocot")
frac = converter.to_rational(3.14159)
print(frac)  # Fraction(355, 113)

Error Tracking

Return Approximation Error

converter = LXRationalConverter(max_denominator=10000)

# Get fraction and error
frac, error = converter.to_rational(3.14159, return_error=True)

print(f"Fraction: {frac}")
print(f"Approximation: {float(frac):.8f}")
print(f"Target: 3.14159000")
print(f"Error: {error:.2e}")

Compare Methods

Compare all three methods for a given value:

converter = LXRationalConverter(max_denominator=10000)

results = converter.compare_methods(3.14159)

for method, (frac, error, time) in results.items():
    print(f"{method:20} : {frac:10} | Error: {error:.2e} | Time: {time*1e6:.2f}μs")

# Output:
# farey                : 355/113    | Error: 2.67e-07 | Time: 15.23μs
# continued_fraction   : 355/113    | Error: 2.67e-07 | Time: 18.45μs
# stern_brocot         : 355/113    | Error: 2.67e-07 | Time: 16.78μs

Practical Applications

GLPK Integer Solver

Convert model coefficients for GLPK’s exact rational mode:

from lumix import LXModel, LXVariable, LXLinearExpression
from lumix.utils import LXRationalConverter

# Build model with float coefficients
products = [
    Product(id=1, profit=12.5),
    Product(id=2, profit=8.333),
    Product(id=3, profit=15.75)
]

model = LXModel("production")
production = LXVariable[Product, float]("x").from_data(products)
model.add_variable(production)

# Extract coefficients
obj_coeffs = {p.id: p.profit for p in products}

# Convert to rationals
converter = LXRationalConverter(max_denominator=10000)
int_coeffs, denom = converter.convert_coefficients(obj_coeffs)

print(f"Original: {obj_coeffs}")
print(f"Integer:  {int_coeffs}")
print(f"Denominator: {denom}")

# Use int_coeffs with GLPK
# ... GLPK-specific solver code ...

Constraint Coefficient Conversion

Convert constraint coefficients:

# Resource usage coefficients
usage_coeffs = {
    ("Product_1", "Resource_A"): 2.5,
    ("Product_1", "Resource_B"): 1.333,
    ("Product_2", "Resource_A"): 3.75,
    ("Product_2", "Resource_B"): 0.666,
}

converter = LXRationalConverter(max_denominator=10000)
int_usage, denom = converter.convert_coefficients(usage_coeffs)

print(f"Integer usage coefficients: {int_usage}")
print(f"Common denominator: {denom}")

Exact Arithmetic

Ensure exact arithmetic for sensitive calculations:

from fractions import Fraction

converter = LXRationalConverter(max_denominator=1000000)

# Convert all coefficients to exact rationals
values = [0.1, 0.2, 0.3, 0.4, 0.5]
fractions = [converter.to_rational(v) for v in values]

# Sum with exact arithmetic (no rounding errors)
exact_sum = sum(fractions, start=Fraction(0))
print(f"Exact sum: {exact_sum}")  # Fraction(3, 2) = 1.5
print(f"Float sum: {sum(values)}")  # Might have rounding error

Advanced Techniques

Custom Tolerance Handling

Fine-tune tolerance for specific use cases:

# Very strict tolerance for financial calculations
converter = LXRationalConverter(
    max_denominator=1000000,
    float_tolerance=1e-15
)

price = 123.456789012345
frac = converter.to_rational(price)
print(f"Exact fraction: {frac}")

Iterative Refinement

Progressively increase denominator until error threshold is met:

def convert_with_error_bound(value: float, max_error: float = 1e-6):
    """Convert to rational with guaranteed error bound."""
    max_denom = 10
    while max_denom <= 1000000:
        converter = LXRationalConverter(max_denominator=max_denom)
        frac, error = converter.to_rational(value, return_error=True)

        if error <= max_error:
            return frac, max_denom

        max_denom *= 10

    raise ValueError(f"Could not meet error bound {max_error}")

# Usage
frac, denom = convert_with_error_bound(3.14159, max_error=1e-6)
print(f"Fraction: {frac} (max denom: {denom})")

Batch Optimization

Optimize denominator for batch of coefficients:

def optimize_batch_conversion(coeffs: dict, target_error: float = 1e-6):
    """Find optimal max_denominator for batch."""
    for max_denom in [100, 1000, 10000, 100000]:
        converter = LXRationalConverter(max_denominator=max_denom)

        # Convert all
        int_coeffs, common_denom = converter.convert_coefficients(coeffs)

        # Check errors
        max_error = max(
            abs(int_coeffs[k] / common_denom - v)
            for k, v in coeffs.items()
        )

        if max_error <= target_error:
            return int_coeffs, common_denom, max_denom

    raise ValueError(f"Could not meet error bound {target_error}")

# Usage
coeffs = {"x1": 3.14159, "x2": 2.71828, "x3": 1.41421}
int_coeffs, denom, max_denom = optimize_batch_conversion(coeffs)
print(f"Used max_denominator: {max_denom}")

Best Practices

  1. Choose Appropriate Max Denominator

    Balance accuracy vs. complexity:

    # For typical LP problems
converter = LXRationalConverter(max_denominator=10000)  # Good default

# For high-precision needs
converter = LXRationalConverter(max_denominator=100000)

# For quick approximations
converter = LXRationalConverter(max_denominator=1000)

  2. Use Batch Conversion

    More efficient than individual conversions:

    # Good: Batch conversion
int_coeffs, denom = converter.convert_coefficients(coeffs)

# Avoid: Individual conversions
fracs = {k: converter.to_rational(v) for k, v in coeffs.items()}

  3. Check Approximation Quality

    Always verify error for critical applications:

    frac, error = converter.to_rational(value, return_error=True)

if error > acceptable_threshold:
    # Increase max_denominator or handle error

  4. Use Farey Method

    Unless you have specific algorithmic needs:

    # Recommended
converter = LXRationalConverter(method="farey")

Performance Considerations

Computation Time

  • Farey is fastest (typically 10-20μs per conversion)

  • Time increases with max_denominator

  • Batch conversion is more efficient than individual calls

Memory Usage

  • Minimal memory footprint

  • No caching of previous results

  • Safe for large-scale conversions

Accuracy vs. Speed

Trade-off between denominator size and speed:

import time

for max_denom in [100, 1000, 10000, 100000]:
    converter = LXRationalConverter(max_denominator=max_denom)

    start = time.perf_counter()
    frac, error = converter.to_rational(3.14159, return_error=True)
    elapsed = time.perf_counter() - start

    print(f"Max denom: {max_denom:6} | Error: {error:.2e} | Time: {elapsed*1e6:.1f}μs")

Common Issues

Large Denominators

If denominators grow too large, reduce max_denominator:

# Problem: denominators too large
converter = LXRationalConverter(max_denominator=1000000)
int_coeffs, denom = converter.convert_coefficients(coeffs)
print(denom)  # Might be very large!

# Solution: Use smaller max_denominator
converter = LXRationalConverter(max_denominator=10000)

Approximation Errors

If errors are too large, increase max_denominator:

# Check error
frac, error = converter.to_rational(value, return_error=True)

if error > threshold:
    # Increase precision
    converter = LXRationalConverter(max_denominator=100000)
    frac, error = converter.to_rational(value, return_error=True)

See Also