Fix-and-Propagate Heuristics Using Low-Precision First-Order LP Solutions for Large-Scale Mixed-Integer Linear Optimization

This paper proposes a fix-and-propagate heuristic that leverages low-precision, GPU-accelerated first-order LP solutions to efficiently solve large-scale mixed-integer linear optimization problems, demonstrating superior performance over state-of-the-art commercial solvers on massive unit commitment instances.

The Gist

Imagine you are trying to organize a massive, chaotic warehouse (a Mixed-Integer Linear Program, or MIP) to ship goods as cheaply as possible. You have millions of boxes (variables), some of which must be whole numbers (you can't ship half a truck), and others can be split. The rules are strict, and the warehouse is so big that even the smartest computers get overwhelmed trying to find the perfect arrangement.

This paper is about a new, clever way to tackle this problem by using a "good enough" guess to jumpstart the search, rather than waiting for a "perfect" calculation that might take forever.

Here is the breakdown using simple analogies:

1. The Problem: The Perfect Map vs. The Quick Sketch

Traditionally, to solve these huge problems, computers use Interior Point Methods (IPMs). Think of this as a cartographer trying to draw a map with laser precision. They measure every inch, every curve, and every tree. It's incredibly accurate, but it takes a long time and requires a massive amount of memory (like trying to carry the entire library of Alexandria in your backpack).

The authors propose using First-Order Methods (FOMs), specifically a tool called PDLP. Think of this as a quick sketch or a rough draft. It doesn't measure every single leaf on every tree; it just gets the general shape of the forest right. It's fast, it runs on powerful graphics cards (GPUs) like the ones in gaming PCs, and it uses very little memory.

2. The Strategy: "Fix-and-Propagate" (The Detective's Trick)

The paper introduces a method called Fix-and-Propagate. Imagine you are a detective trying to solve a mystery with a million suspects.

• The Old Way: You interview every single suspect perfectly before making a move. This takes years.
• The New Way (Fix-and-Propagate): You look at your rough sketch (the low-precision solution). You see that 90% of the suspects are clearly innocent. You say, "Okay, let's fix these 90% as innocent immediately."
• Propagate: Once you lock those 90% down, the rules of the mystery force the remaining 10% to behave in specific ways. You don't need to interview them all; the logic of the case does the work for you.

The authors found that even if your "rough sketch" isn't 100% perfect, it's good enough to tell you which suspects to lock up immediately. This saves a massive amount of time.

3. The Experiment: The "Energy Grid" Challenge

To test this, the authors didn't just use small puzzles; they used Energy System Optimization Models (ESOMs).

• The Analogy: Imagine trying to schedule every power plant, wind turbine, and battery in Germany and its neighbors for an entire year, hour by hour. You have to decide when to turn them on, when to store energy, and how to move it across borders.
• The Scale: This is a problem with 243 million moving parts. It's like trying to solve a Sudoku puzzle that is the size of a football field.

4. The Results: Speed vs. Perfection

The authors compared their "Quick Sketch" method against the "Laser Precision" method and even against top-tier commercial software (like Gurobi).

• On Standard Puzzles (MIPLIB): They found that using the "rough sketch" didn't hurt the quality of the answer. The final solution was just as good, but they got there faster on big problems.
• On the Giant Energy Grid: This is where the magic happened.
  • The Competitors: The best commercial software tried to draw the "laser-precise map" first. It ran out of memory and time. After two days, it still couldn't find a single working schedule for the biggest grids.
  • The Authors' Method: They used the "quick sketch" to make the first moves. They found a working schedule with a tiny error margin (less than 2% off the theoretical best) in under 4 hours.

5. The Takeaway

The paper proves that you don't always need a perfect map to navigate a forest. Sometimes, a fast, rough sketch drawn on a GPU is enough to point you in the right direction.

By combining a fast, low-accuracy guess with a smart logic system (Fix-and-Propagate), they can solve problems that were previously considered impossible to solve in a reasonable time. It's like realizing that to get to the other side of the ocean, you don't need to calculate the exact path of every wave; you just need a good compass and a fast boat.

In short: They taught computers to stop obsessing over tiny details at the start of a massive problem, allowing them to solve "impossible" energy planning tasks in hours instead of days.

Technical Summary

Here is a detailed technical summary of the paper "Fix-and-Propagate Heuristics Using Low-Precision First-Order LP Solutions for Large-Scale Mixed-Integer Linear Optimization."

1. Problem Statement

The paper addresses the computational challenges of solving Large-Scale Mixed-Integer Linear Programming (MIP) problems, specifically in the context of energy system optimization.

• The Bottleneck: Traditional MIP solvers rely heavily on Interior-Point Methods (IPMs) and Simplex algorithms to solve Linear Programming (LP) relaxations. While accurate, these methods are computationally expensive, memory-intensive (scaling quadratically with matrix size), and difficult to accelerate on modern hardware like GPUs.
• The Gap: For massive problems (e.g., unit commitment with millions of variables), commercial solvers often fail to find feasible solutions within reasonable timeframes (e.g., 2 days) or cannot solve the initial LP relaxation at all due to memory constraints.
• The Opportunity: First-Order Methods (FOMs), such as the Primal-Dual Hybrid Gradient (PDHG) method (specifically PDLP), are highly efficient on GPUs and scale linearly with matrix size. However, they typically provide solutions with lower precision (relative feasibility) compared to IPMs. The core research question is: Can low-precision, GPU-accelerated LP solutions be effectively integrated into MIP heuristics without sacrificing solution quality?

2. Methodology

The authors propose a Fix-and-Propagate (FP) heuristic framework that leverages low-precision LP solutions to guide the search for integer-feasible solutions.

A. The Fix-and-Propagate Framework

The implementation builds upon a depth-first-search (DFS) based FP scheme (derived from [16]) with three key modifications:

1. LP-Based Variable Strategies: Instead of relying solely on structural properties, the framework uses LP solution values to prioritize variables for fixing. Strategies include:
   • Frac: Sorts by fractional distance to the nearest integer.
   • RedCost: Sorts by reduced costs (variables with high reduced costs are less likely to change in the optimal solution).
   • Dual: Combines dual constraint values with reduced costs to prioritize variables in tight constraints.
   • Type: A stable sort (binaries first, then integers).
2. LP-Based Fixing Strategy: When fixing an integer variable $x_i$ based on its LP value $x^{LP}_i$, the method does not simply round to the nearest integer (which often causes infeasibility). Instead, it uses a probabilistic approach:
   • Calculate fractional distance $d_i = x^{LP}_i - \lfloor x^{LP}_i \rfloor$.
   • Sample $d \sim U(0,1)$.
   • Fix to the lower bound if $d > d_i$, otherwise to the upper bound. This introduces diversification while staying close to the LP solution.
3. Integer-Aware Branching: A custom branching algorithm (Algorithm 1) generates 2 or 3 child nodes based on the variable's domain and the suggested fixing value, ensuring the search explores regions around the LP solution effectively.

B. Solver Integration

• Initial LP Relaxation: Solved using PDLP (GPU-accelerated) or IPM (CPU-based) with varying tolerances ($10^{-4}$to$10^{-6}$).
• Final LP Relaxation: Once a partial integer assignment is found, the final LP is solved with a high-precision IPM to generate a feasible MIP solution.
• Hardware: Experiments utilized NVIDIA A100 and H200 GPUs, leveraging the linear memory scaling of PDLP.

3. Key Contributions

1. Framework Development: A novel FP framework that systematically integrates low-accuracy LP solutions (from FOMs) into MIP heuristics.
2. MIPLIB Evaluation: Demonstration that solution quality is largely insensitive to LP precision on standard benchmarks (MIPLIB 2017), proving that low-accuracy solutions do not degrade heuristic performance.
3. Large-Scale Application: Successful application to Energy System Optimization Models (ESOMs) with up to 243 million non-zeros and 8 million variables. The approach achieves primal-dual gaps < 2% in under 4 hours, a feat where state-of-the-art commercial solvers (Gurobi) fail to find feasible solutions within 2 days.

4. Experimental Results

A. MIPLIB 2017 Benchmarks

• Performance: LP-based strategies found solutions with gaps averaging 16.33% (vs. 24.44% for presets) but required slightly more time due to the initial LP solve.
• Precision Impact: Reducing LP precision from $10^{-6}$to$10^{-4}$ yielded a 1.5x speedup for PDLP with negligible impact on the final MIP gap (variation < 0.2%).
• Solver Comparison: On small/medium MIPLIB instances, IPM remains faster in absolute terms. However, PDLP outperforms IPM on larger, denser instances (18.2% of runs were faster with PDLP on instances with >790k non-zeros).

B. Large-Scale ESOMs (UNSEEN Project)

• Scalability:
  • Memory: PDLP memory usage scales linearly (staying under 50 GB GPU memory even for the 243M instance), whereas IPM requires >600 GB RAM and times out.
  • Speed: For the largest instance (remix 243M), PDLP solved the initial LP in ~437 seconds (at $10^{-4}$ tolerance), while IPM timed out after 12 hours.
• Heuristic Effectiveness:
  • The "Type" strategy combined with PDLP and repair mechanisms solved 87–100% of instances across all sets.
  • Gaps: Achieved gaps < 1% for smaller sets and < 2% for the largest sets (remix 243M).
  • Comparison: Gurobi (commercial solver) failed to find any feasible solution for the remix 105M and remix 243M sets within a 2-day limit, whereas the proposed heuristic solved them in hours.

5. Significance and Conclusion

• Hardware Efficiency: The paper validates that GPU-accelerated FOMs are not just theoretical alternatives but practical tools for massive-scale optimization, overcoming the memory bottlenecks of traditional IPMs.
• Heuristic Robustness: It proves that "good enough" LP solutions (low precision) are sufficient to guide high-quality MIP heuristics. The stochastic nature of the fixing strategy compensates for the lower accuracy of the LP solution.
• Real-World Impact: The methodology enables the optimization of national-scale power grids (e.g., Germany and neighbors) with hourly resolution over a full year, a problem class previously intractable for standard solvers.
• Future Directions: The authors suggest exploring hybrid LP variants and utilizing the cycling behavior of PDLP to generate multiple reference solutions for diversification.

In summary, this work bridges the gap between high-performance computing (GPUs/FOMs) and combinatorial optimization, offering a viable path to solve previously unsolvable large-scale MIPs in the energy sector.