FPTR
A framework for optimizing real-time decision problems such as wireless scheduling under hard deadline constraints. It separates the construction of a forced feasible solution from an optional refinement phase, and uses a transactional design ensuring that each candidate solution passes feasibility verification before the deadline and is adopted only if it strictly improves the objective, thereby guaranteeing a feasible output at all times.
Timeline (last 90 days)
FPTR (Feasibility-Preserving Transactional Refinement) is an optimization framework whose core is to always maintain a verified feasible assignment (the incumbent solution), with each refinement stage independently constructing a candidate solution and replacing the incumbent only when the candidate is complete, passes feasibility verification, and strictly improves the objective.
FPTR separates mandatory output construction from optional refinement, first generating an initial feasible solution through a base constructor and then sequentially executing four refinement stages.
The four refinement stages of FPTR are, in order: buffer-aware resource selection, compatible-group user sharing, beam mask reconstruction based on residual demand, and joint reallocation of the two resources.
On 150 fixed synthetic instances, the full FPTR pipeline improves average traffic by 3.83% over the lightweight beam-first reference scheme and by 1.79% over its Base constructor.
In another set of tests with matching inputs, under the constraint that output latency exceeding 100 milliseconds yields zero utility, the full FPTR pipeline outperforms six independent search baselines (ALNS, tabu search, genetic algorithm, simulated annealing, iterated local search, and GRASP) by 6.68% to 8.35%.
Across all 750 runs of the full FPTR pipeline on the internal suite, every run returned a feasible assignment, and no run exceeded 100 milliseconds.
General search frameworks (such as ALNS, tabu search, genetic algorithm, simulated annealing, iterated local search, and GRASP) may fail under hard deadlines because they cannot guarantee a feasible solution at every iteration, whereas FPTR avoids this deficiency through transactional refinement.
FPTR's architecture is applicable to any optimization scenario that needs to continuously output feasible solutions under hard deadlines, not only wireless scheduling.
An open-source implementation of FPTR is available, supporting independent reproduction.
All Facts (9)
FPTR (Feasibility-Preserving Transactional Refinement) is an optimization framework whose core is to always maintain a verified feasible assignment (the incumbent solution), with each refinement stage independently constructing a candidate solution and replacing the incumbent only when the candidate is complete, passes feasibility verification, and strictly improves the objective.
50%UnverifiedFPTR separates mandatory output construction from optional refinement, first generating an initial feasible solution through a base constructor and then sequentially executing four refinement stages.
50%UnverifiedThe four refinement stages of FPTR are, in order: buffer-aware resource selection, compatible-group user sharing, beam mask reconstruction based on residual demand, and joint reallocation of the two resources.
50%UnverifiedOn 150 fixed synthetic instances, the full FPTR pipeline improves average traffic by 3.83% over the lightweight beam-first reference scheme and by 1.79% over its Base constructor.
50%UnverifiedIn another set of tests with matching inputs, under the constraint that output latency exceeding 100 milliseconds yields zero utility, the full FPTR pipeline outperforms six independent search baselines (ALNS, tabu search, genetic algorithm, simulated annealing, iterated local search, and GRASP) by 6.68% to 8.35%.
50%UnverifiedAcross all 750 runs of the full FPTR pipeline on the internal suite, every run returned a feasible assignment, and no run exceeded 100 milliseconds.
50%UnverifiedGeneral search frameworks (such as ALNS, tabu search, genetic algorithm, simulated annealing, iterated local search, and GRASP) may fail under hard deadlines because they cannot guarantee a feasible solution at every iteration, whereas FPTR avoids this deficiency through transactional refinement.
50%UnverifiedFPTR's architecture is applicable to any optimization scenario that needs to continuously output feasible solutions under hard deadlines, not only wireless scheduling.
50%UnverifiedAn open-source implementation of FPTR is available, supporting independent reproduction.
50%