Anytime Predict-and-Optimize with Soft Primal Guidance

In contextual combinatorial optimization, decision cost is a primary concern, but computation time can also be important, particularly in applications with operational deadlines. Conventional predict-and-optimize formulations focus on coefficient accuracy or terminal decision quality, but do not explicitly account for how prediction overhead and incomplete search jointly affect decisions before a deadline. We propose Soft Primal Prior (SPP), which combines coefficient regression with solution-membership supervision from cached feasible decisions. The predicted memberships define variable-level preferences that shape a linear surrogate objective and its feasible initialization, while an unmodified solver enforces the original constraints. This construction leaves every feasible decision admissible and uses one trained model across deadlines. After offline label construction, gradient updates require no optimizer calls. Our analysis relates budgeted regret to objective mismatch, membership-estimation error, and incomplete optimization, and identifies when later decision gains compensate for guidance latency. Across three contextual benchmarks and a retrospective energy-scheduling case, SPP achieves competitive budgeted decision quality and reduces end-to-end Area Under the Regret Curve (AURC) by up to approximately 19.3% relative to coefficient-only predict-then-optimize, while the energy case shows that early fallback costs can offset gains at later deadlines.