CS Paper Radar

Fast and Accurate Hydro Unit Commitment

Shaked Regev, Evan J. R. Brody

cs.MS math.OCeess.SY ·submitted 2026-10-29 19:43 UTC · v1
theory

Abstract

We introduce a fast novel algorithm to commit hydro-generators. We show that our algorithm can commit 56 generators for 200 days 10,000 times faster than Hexaly, the leading commercial solver for scheduling problems, without sacrificing solution quality. Our method can commit 1792 generators for an entire year in approximately 20 seconds on commodity hardware. Hexaly is unable to solve problems of this size in reasonable time. We attain this runtime improvement by introducing a greedy-heuristic tailored for hydro units. We provide a direction for a possible proof that the error our solver makes decreases with the problem size. This is supported by our experimental results. We prove that our solver's runtime scales log-linearly in the number of generators and time periods.

Comment
5 pages (Conference limit), 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Presolve heuristics in HiGHS: implementation and computational study

cs.MS math.OC ·2026-09-19 ·Simon Spoorendonk
benchmarkcode/data similarity 0.59
Abstract

We present reference implementations of four published primal heuristics for mixed-integer programming inside the open-source solver HiGHS (Huangfu and Hall, 2018): Feasibility Jump (Luteberget and Sartor, 2023), fix-propagate-repair (FPR; Salvagnin, Roberti and Fischetti, 2025) with its LP-guided dive-time variant, LocalMIP (Lin, Zou and Cai, 2024), and the first-order-LP feasibility pump Scylla (Mexi et al., 2025). They share one integration interface with per-heuristic budgets and patiences, and each runs in parallel on independently seeded workers. The evaluation is on the mipfeas benchmark (Bussieck and Dirkse, 2026), 233 instances at 600 s, against a separately built unpatched HiGHS on the same machine. The primal integral improves by 23.7% over the full set and by 12.9% on the instances not used for tuning: the patched solver reaches a good solution sooner. At the time limit it is slightly ahead. It finds a solution on 4 instances where the unpatched solver finds none, against 1 the other way, and its final gap is smaller, significantly so only over the full set. Scylla and the LP-guided dive produced no accepted incumbent in any full-limit run that carried them and ship disabled; their implementations remain. The implementation is released as open source.

0.31

Fast Relax-and-Round Unit Commitment with Topological Constraints

cs.MS math.OCeess.SY ·2026-09-11 ·Evan J. R. Brody, Charles Foltz, Eve Tsybina, Slaven Peles, Shaked Regev
similarity 0.58
Abstract · 10 pages, 12 figures

Recent developments in the US knowledge economy have created a significant growth in datacenter loads, with two major consequences for power generation. First, to compensate for growth in load, datacenters are encouraged to bring their own generating units. Second, in search of the remaining pools of dispatchable generation, utilities are increasingly turning to subtransmission and distribution level generating assets. Coupled with increasing loads and the resulting tighter grid conditions, both trends are likely to create a need to commit a large number of localized generating units under grid constraints. We propose an extension of Relax-and- Round Unit Commitment (RRUC) that is capable of committing generating units for larger problems faster than conventional methods, while staying within intertemporal and spatial MVA constraints. We demonstrate the performance of RRUC using synthetic congestible test systems ranging from 100 to 20,000 buses. RRUC consistently finds low cost solutions, independent of the problem size, and its run time increases sub-quadratically in the number of buses. RRUC can solve the 100 bus system in less than a second and the 20,000 bus system 7 minutes. In contrast, a leading state of the art solver cannot find a feasible solution to the 100 bus system in 15 minutes.

0.35

To Race or Not to Race? Exploiting Performance Variability in Mixed-Integer Programming via Root-Gated Resource Allocation

cs.PF math.OC ·2026-11-12 ·Mourchid Adegbindin, Brenda Dietrich, Jamol Pender
similarity 0.57
Abstract · 17 pages, 4 figures, 2 tables

Mixed-integer programming (MIP) solver runtimes vary substantially across random seeds. Parallel replication exploits this variability but can waste computational resources when applied indiscriminately. We investigate whether information from an ordinary solve can guide this allocation decision. We formulate replication under a finite deadline, establish an exact relationship between runtime dispersion and the value of independent searches, and analyze delayed replication and imperfect allocation decisions. Using 101,615 seeded SCIP runs, we examine the association between root-LP dual degeneracy and replication value. We then introduce a non-invasive root-gated policy that preserves the original solver trajectory and launches three additional seeded processes when a root dual-degeneracy indicator reaches a fixed threshold. In a prospective two-hour experiment on 130 paired instances, root-gated racing proves optimality on 77 instances (59.23%), versus 73 (56.15%) for both Single and unconditional Race-4, while reducing active worker-process occupancy by 43.00% relative to unconditional racing. These findings demonstrate the promise of selective parallel resource allocation without solver-source modifications.

0.28

Race, Exchange, Improve: Finding high-quality MIP solutions quickly

cs.DC math.OC ·2026-09-05 ·Gioni Mexi, Daniel Rehfeldt
benchmarkcode/data similarity 0.57
Abstract · 10 pages, 2 figures, 3 tables

Mixed-integer programming (MIP) is a cornerstone in applied optimization, both in industry and academia. Recently, there has been increased attention to finding strong primal solutions quickly. This is reflected, for example, in the development of the NVIDIA cuOpt solver and, most recently, in the new MIPFEAS benchmark, which has a tight time limit of 600 seconds and evaluates solvers based on how quickly they find high-quality primal solutions. This article introduces a MIP portfolio parallelization scheme, focusing on efficiently exchanging information between its workers. We present two implementations of this scheme: one built directly into the open-source MIP solver SCIP, and an external one, which we call ReXi. ReXi is currently the fastest non-commercial solver in the MIPFEAS benchmark, followed by the SCIP-integrated implementation. Moreover, we present new versions of both implementations that considerably outperform their predecessors on the MIPFEAS benchmark.

0.61

Learning to Fix: Optimisation-Aware Machine Learning for Accelerated Unit Commitment

eess.SY ·2026-09-30 ·Benjamin Fritz, Andreas Makrides, Maryam Fetanat, Pierre Pinson
similarity 0.56
Abstract

Unit Commitment is a computationally demanding mixed-integer linear optimisation problem requiring many binary commitment decisions across a scheduling horizon. To reduce this computational burden, machine learning approaches can predict a subset of these decisions, thereby shrinking the search space explored by the optimisation solver. Existing confidence-based approaches determine which variables to fix based on user-defined probability thresholds, which are agnostic to the downstream optimisation problem. We address this limitation by introducing an optimisation-aware framework that yields generator-specific confidence thresholds based on the impact of fixing errors on Unit Commitment solution quality. This approach won first place in the 2025 EPRI AI-ccelerating Unit Commitment competition. The proposed framework achieves a mean optimality gap below 0.5% while also delivering an average speed-up of more than 20x. It therefore provides a general mechanism for translating probabilistic predictions into controlled reductions of mixed-integer search spaces, directly linking learning decisions to their downstream computational and economic consequences.

0.20

Two Communities, One Problem: Branch-and-Bound vs. A* for Resource-Constrained Project Scheduling

cs.AI math.OC ·2026-11-10 ·Izack Cohen, Dominik Kress, Lara Nehrke, Erwin Pesch, Shimrit Shtern
benchmarktheory similarity 0.54
Abstract

Branch-and-Bound (B&B) and $A^*$ are popular exact search methods originating from Operations Research and Artificial Intelligence, respectively. Although the two methods share fundamental search principles, their different ways of exploring the search space can lead to substantially different computational performance. We investigate these differences using the Resource-Constrained Project Scheduling Problem (RCPSP) as an exemplary problem setting. We first establish the relationships between mixed-integer linear programming, state-action, and timed Petri-net representations. Since B&B and $A^*$ admit numerous algorithmic enhancements, we focus on relatively basic implementations. This allows us to examine the fundamental differences between the methods rather than compare the performance of state-of-the-art solvers. By using the same lower bound and best-first node selection, we isolate the effects of the search mechanisms, particularly the identification of equivalent states reached through different scheduling decision sequences. Experiments on 480 benchmark RCPSP instances show that graph-based $A^*$ substantially outperforms the B&B variants considered. With additional pruning rules, $A^*$ proves optimality for all 480 instances, compared with 445 for best-first B&B under the same time and memory limits. Depth-first B&B uses less memory and can find feasible solutions even when the search does not finish within the time limit. Stronger linear programming relaxations reduce the search space but introduce considerable computational overhead. Our findings highlight the importance of duplicate-state detection and clarify the computational trade-offs between the search approaches. These insights can help researchers select an appropriate method and identify opportunities to incorporate effective mechanisms from one approach into the other.

0.27

PaNGEA: Parallel Node Generation and Exploration Algorithm on GPU

cs.DC math.OC ·2026-10-02 ·Jean Pauphilet, Yupeng Wu
similarity 0.53
Abstract

Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining linear-relaxation solves with a local-search procedure designed for efficient batched execution on GPUs. In addition, instead of relying on a single heuristic for iterative variable fixing, we leverage GPU batching capabilities to generate and explore multiple subproblems in parallel. PaNGEA leverages GPU capabilities in two ways. First, on 283 MIPcc26 and MIPLIB instances, implementing a single-node primal heuristic on the GPU reduces the average gap integral by 8-18% relative to its CPU counterpart. Second, generating and exploring multiple nodes in parallel further reduces the average gap integral by 12-19%.

0.22

Feasibility-Aware Learning for Network-Constrained Unit Commitment

eess.SY ·2026-11-08 ·Hien Thanh Doan, Yeji Lim, Hongseok Kim
similarity 0.53
Abstract

Learning-based approaches to network-constrained unit commitment (NCUC) usually still rely on an optimization solver to repair or complete their predictions, which limits the speedup they can deliver. This paper proposes FALCON-UC, a feasibility-aware graph learning framework that predicts commitment and dispatch jointly and produces final schedules without solving a mixed-integer program at inference time. It combines an LSTM--GraphSAGE predictor over a fully connected generator graph, a differentiable correction that embeds commitment-dependent dispatch bounds, power balance, and PTDF-based branch flows in training, and deterministic commitment, dispatch, and ramp-coupled reserve repairs at inference. On the 2383-bus system, FALCON-UC achieves $99.09\%$ commitment accuracy and a $0.4350\%$ mean absolute cost gap with all evaluated constraints within tolerance at $0.0562$ s per instance, a $2.27\times10^{3}$ speedup over the solver. MTLR R-SCUC-FL is slightly more accurate but still needs an optimization solver to complete each schedule, which takes $262.2$ s per instance, $4.67\times10^{3}$ times the FALCON-UC runtime. A label-only baseline without repair violates the balance and branch limits on every 2383-bus test instance, and FALCON-UC also meets all evaluated constraint tolerances on a 1354-bus system.

0.26