FPTR: A Feasibility-Preserving Transactional Refinement Framework Under Deadline Constraints

In wireless schedulers, beam and resource allocation over short intervals must return a complete and feasible solution before each execution deadline; any delay or invalid output results in zero utility for the current control cycle. Extending the search may improve throughput, but it can also miss the deadline or yield only infeasible intermediate solutions. To address this, researchers propose Feasibility-Preserving Transactional Refinement (FPTR), whose core idea is to always maintain a verified feasible allocation (the incumbent solution). Each refinement stage independently constructs a candidate solution, and the incumbent is replaced only when the candidate is complete, passes feasibility verification before the stage deadline, and strictly improves the objective.

How FPTR Works: Transactional Refinement and Feasibility Guarantees

FPTR separates mandatory output construction from optional refinement. First, a Base constructor generates an initial feasible solution, followed by four refinement stages executed in sequence:

• Buffer-aware resource selection: Select resources based on buffer status to reduce potential conflicts.
• Compatibility group (CG) user sharing: Allow multiple users to share resources through compatibility groups, improving efficiency.
• Beam mask reconstruction based on residual demand: Reconstruct the beam mask using residual demand to optimize coverage.
• Joint reallocation of two resources: Jointly adjust two resources to further improve the objective.

Each stage constructs a candidate solution in an isolated space and sets a stage deadline. The candidate must pass the feasibility verifier before that deadline and strictly improve the objective function; otherwise, it is discarded. This "transactional" design ensures the incumbent solution always remains feasible, avoiding infeasible states caused by search.

Beam mask is a concrete implementation of beamforming in wireless communication: it encodes the antenna array weights as a mask (typically binary or discrete-valued) to control which antenna elements are active and with what phase/amplitude combination to form a beam pointing in a specific direction. Beam mask reconstruction means recalculating and generating a new set of beam configurations based on the current user distribution and resource occupancy, so that coverage and capacity match the residual demand. In FPTR, this step uses the residual demand after processing by prior stages to reconstruct the mask, avoiding repeated resource allocation to already-satisfied users, thereby targeting coverage optimization within limited time.

Experimental Performance: Throughput Gains and Deadline Satisfaction

On 150 fixed synthetic instances, the full pipeline (Full) improves average throughput by 3.83% over a lightweight beam-first reference scheme and by 1.79% over its Base constructor. In another set of tests with matched inputs, under the constraint that output latency exceeding 100 ms yields zero utility, Full outperforms six independent search baselines (ALNS, tabu search, genetic algorithm, simulated annealing, iterated local search, and GRASP) by 6.68% to 8.35%.

All 750 Full runs in the internal suite returned feasible allocations, and none exceeded 100 ms. This shows that FPTR can reliably deliver high-quality solutions under strict deadlines without sacrificing feasibility or timeliness due to search.

ALNS (Adaptive Large Neighborhood Search) is a metaheuristic algorithm that iteratively removes and reinserts parts of a solution through multiple "destroy-repair" operators, adaptively adjusting their selection probabilities based on recent performance. Its advantage is the ability to escape local optima, but each iteration requires a full evaluation of solution quality. Tabu search uses short-term memory (a tabu list) to forbid revisiting recent solutions, exploring a broader solution space; genetic algorithms evolve a population through selection, crossover, and mutation; simulated annealing accepts worse solutions probabilistically to escape local optima; iterated local search applies perturbation after local search and restarts; GRASP (Greedy Randomized Adaptive Search Procedure) repeatedly constructs randomized greedy solutions and performs local improvement. These baselines are general-purpose search frameworks that may fail under hard deadlines because they cannot guarantee a feasible solution at every iteration, whereas FPTR avoids this flaw through transactional refinement.

Design Insight: Separating Mandatory Construction from Optional Refinement

The key contribution of FPTR is decoupling mandatory output construction from optional refinement. Mandatory construction guarantees that a feasible solution is available under all circumstances, while optional refinement uses remaining computation time to improve solution quality without jeopardizing the incumbent. This architecture is applicable to any optimization scenario that requires continuously outputting feasible solutions under hard deadlines, not just wireless scheduling.

An open-source implementation is available, supporting independent reproduction. For engineers and researchers requiring real-time decision-making, FPTR provides a practical framework that balances feasibility and performance.

One-line Summary

FPTR always maintains a feasible solution through transactional refinement, improving wireless scheduling throughput under hard deadlines.

Paragraph Summary

FPTR (Feasibility-Preserving Transactional Refinement) addresses the problem that short-interval decisions in wireless schedulers must return a feasible solution before the deadline by separating mandatory output construction from optional refinement. A base constructor first generates an initial feasible solution, and then four refinement stages (buffer-aware resource selection, compatibility group user sharing, beam mask reconstruction based on residual demand, and joint reallocation of two resources) each construct candidate solutions in isolated spaces. The incumbent is replaced only when the candidate is complete, passes feasibility verification before the stage deadline, and strictly improves the objective. Experiments show that the full pipeline improves throughput by 3.83% over a lightweight reference scheme and by 6.68% to 8.35% over six independent search baselines, and all 750 runs returned feasible allocations within 100 ms. The architecture applies to any optimization scenario requiring continuous feasible output under hard deadlines.