[Meta] Direct QUBO encodings: prioritized scheduling, sequencing, and related-model roadmap #1213

Problem and intended outcome

Many scheduling, sequencing and related assignment problems reach QUBO through ILP. Generic conversion introduces binary encodings, inequality slack and squared row penalties; in some cases it first linearizes a quadratic objective and then converts it back to QUBO. Add source-specific rules where they reduce actual logical variables/couplings or connect a currently disconnected model.

This is a prioritized tracking issue, not a claim that all listed formulations are verified or ready to implement. It contains all 47 model/variant candidates from the scheduling/sequencing and neighboring-model scan, plus a broader ILP-entry inventory. Split verified constructions into individual rule tasks/PRs and link them here; check for existing issues before creating children.

Priority order: identifiable auxiliary-variable savings and proof readiness first, then benefit to existing incoming chains, then conditional improvements and dedicated formulation research. Ordering is provisional until exact-variant path comparisons and measured target sizes are available. P1 is implementation priority, not an incident severity.

Baseline and how to measure improvement

Scan baseline: checkout commit 55823fbc894647fa83cfc70b7c60bca6bcba673e (2026-10-22). Recheck current main before implementation.

The current binary ILP → QUBO rule declares:

N_Q <= v + c*(v+h)
E_Q <= (v + c*(v+h))^2

Here v is the binary ILP variable count, c the constraint count and h the constraint-magnitude bit parameter. The often-quoted degree-d → degree-4d effect is a conservative composed-size bound under appropriate scaling assumptions, not a universal count of actual variables. Actual slack bits depend logarithmically on individual constraint ranges. QUBO objective degree remains two.

For every candidate, compare actual variables, nonzero couplings, coefficient magnitude/bit length, construction cost and composed parameter bounds against existing routes. Numeric time horizons must remain explicit: O(nT) is pseudopolynomial when T is binary encoded. Logical size alone does not establish physical annealer fit or speedup.

Notation below: n = tasks/items/vertices as appropriate; m = processors; k = groups; f/l = facilities/locations; S = total admissible start choices; A = available timetable assignments. Counts are proposed construction bounds pending full-domain proof, not measured benchmark results.

Existing incoming connections motivating scheduling coverage

• OptimalLinearArrangement → weighted-completion sequencing.
• Partition → multiprocessor scheduling, Decision, Decision.
• ThreePartition → resource-constrained scheduling and release-time/deadline sequencing.
• KSatisfiability → preemptive scheduling and timetable design.
• ExactCoverBy3Sets → staff scheduling.

Most other scheduling models are not currently large incoming hubs. Avoid assuming that every new rule shortens a large subtree.

P1 — Implement and validate first

• 1. SequencingToMinimizeWeightedCompletionTime → QUBO: Pairwise ordering, quadratic transitivity, linear precedence penalties and weighted-completion objective. Target: n(n−1)/2 bits and at most 3·C(n,3) couplings; removes completion-time and triangle-slack variables. Benefits the OptimalLinearArrangement chain.
• 2. MinimumTardinessSequencing<One> → QUBO: Task-position assignment with linear position-dependent tardy-task costs and direct precedence-conflict penalties. Target: n² bits without separate tardiness indicators.
• 3. SequencingWithinIntervals → QUBO: One-hot admissible starts and direct overlap penalties. Target: S bits, where S is the total number of admissible starts; removes one slack bit per current overlap constraint.
• 4. TimetableDesign → QUBO: Available-assignment bits, squared exact work requirements and pairwise exclusivity penalties. Target: A bits, where A is num_available_assignments; removes exclusivity slack and serves an existing 3SAT incoming rule.
• 5. MaximumLikelihoodRanking → QUBO: Pairwise ordering and quadratic transitivity with linear disagreement costs. Target: C(n,2) bits and O(n³) couplings; removes triangle-inequality slack.
• 6. QuadraticAssignment → QUBO: Retain facility-location assignment bits and the original quadratic objective, with assignment penalties. Target: f·l bits; removes the current f(f−1)l² product-linearization variables.
• 7. SumOfSquaresPartition → QUBO: Item-group assignment bits, one-hot penalties and squared group sums. Target: n·k bits; removes current n²k product variables.
• 8. OptimalLinearArrangement<SimpleGraph> → QUBO: Vertex-position assignment and distance-weighted pair interactions. Target: n² bits; compare against the new weighted-completion sequencing route, especially for dense graphs.

P2 — High-value follow-ups; settle domains and path comparisons

• 9. SchedulingToMinimizeWeightedCompletionTime → QUBO: Processor-assignment bits and pair interactions under fixed Smith order can use n·m bits on the positive domain. The current constructor accepts negative nonzero inputs despite its documentation: prove compatibility with actual evaluation or explicitly resolve the model domain before adopting this formulation.
• 10. SchedulingWithIndividualDeadlines → QUBO: Use only deadline-valid task slots; encode precedence conflicts directly and processor capacities exactly. Measure both removed variables and added couplings.
• 11. PrecedenceConstrainedScheduling → QUBO: Task-slot bits, forbidden precedence-pair penalties and capacity encoding. Eliminates precedence slack, but dense conflict couplings can offset savings.
• 12. CyclicOrdering → QUBO: Pairwise total-order bits with transitivity penalties and squared orientation-count constraints for prescribed triples. Compare against the existing sparse rank formulation.
• 13. GroupingBySwapping → QUBO: Symbol-block ordering bits with pairwise inversion costs and a budget threshold. Prove exact correspondence to minimum adjacent-swap count.
• 14. MinimumFeedbackArcSet<i64> → QUBO: Total-order bits with backward-arc costs. Verify the concrete graph/weight domain, treatment of negative weights and extraction before claiming a full-domain rule.
• 15. Partition → QUBO: Square the difference between the two subset totals; one bit per element. Compare against existing short routes before claiming asymptotic improvement.
• 16. SubsetSum → QUBO: Square the selected-sum residual; one bit per element, with exact feasibility threshold and offset.
• 17. ExactCoverBy3Sets → QUBO: Subset-selection bits and squared exact-cover equations; one bit per subset.
• 18. ThreePartition → QUBO: Item-group assignments with exact cardinality and group-sum penalties. Equality constraints avoid capacity slack.
• 19. ThreeDimensionalMatching → QUBO: Triple-selection bits, intersection-conflict penalties and exact cardinality requirements. Preserve the model's exact witness requirements.
• 20. ExpectedRetrievalCost → QUBO: Record-sector assignment bits and direct quadratic latency costs; removes product linearization. Requires QUBO and a separate floating-point penalty/evaluation contract.
• 21. BottleneckTravelingSalesman → QUBO: Tour-position bits and forbidden transitions for a fixed bottleneck bound. Identify the actual endpoint semantics; optimization needs bound encoding or a separate decision-search route.
• 22. StackerCrane → QUBO: Required-arc order encoding with direct transition costs. Prove travel-cost preprocessing, connectivity and exact route reconstruction.
• 23. ShortestCommonSuperstring → QUBO: String-order assignment with overlap costs after containment preprocessing. Prove preprocessing and reconstruction for empty, duplicate and contained strings.

P3 — Conditional savings; benchmark before committing to a formulation

• 24. MinimumTardinessSequencing<i64> → QUBO: Time-indexed starts with linear tardy-task costs, or binary completion arithmetic and exact deadline indicators. Preserve signed inputs; avoid silently assuming unit or positive durations.
• 25. SequencingToMinimizeTardyTaskWeight → QUBO: Time-indexed weighted late-task costs, or order/completion bits and exact late indicators. Signed weights require exact indicator semantics.
• 26. SequencingToMinimizeWeightedTardiness → QUBO: Time-indexed weighted tardiness costs with a decision threshold, or binary completion/tardiness arithmetic. This model is feasibility with a bound, not an optimization endpoint.
• 27. SequencingWithReleaseTimesAndDeadlines → QUBO: Admissible-start conflict encoding versus compact binary start times and disjunction gadgets. A time grid may be much larger than the current binary-time route.
• 28. MultiprocessorScheduling → QUBO: Task-processor assignment and squared load equations with binary slack. Likely retains the generic route's actual variable count; a better metadata bound alone is not a physical size saving.
• 29. ResourceConstrainedScheduling → QUBO: Task-slot assignment and exact processor/resource capacity penalties. General resource capacities still need slack or equivalent gadgets; compare against the current clamped-horizon construction.
• 30. BinPacking<i64> → QUBO: Item-bin assignment, bin-use bits and capacity slack with a bin-use objective. Quantify savings against the existing assignment/capacity formulation.
• 31. CapacityAssignment → QUBO: One-hot capacity choices, linear costs and delay-budget slack. Much of the existing encoding is already suitable for QUBO.
• 32. DynamicStorageAllocation → QUBO: Admissible-address bits and direct conflicts for items overlapping in both lifetime and address range. Size depends on numeric memory capacity.
• 33. FeasibleRegisterAssignment → QUBO: Register-choice bits and direct conflict penalties where the source model permits them. First verify all model-specific assignment restrictions.
• 34. LongestCommonSubsequence → QUBO: Character-match choices and incompatibility penalties. Compare with the existing MIS route; match-tuple enumeration can grow rapidly.
• 35. ShortestCommonSupersequence → QUBO: Symbol-position and embedding choices with direct order and compatibility penalties. Quantify which generic auxiliaries actually disappear.
• 36. MinimumGraphBandwidth<SimpleGraph> → QUBO: Vertex-position assignment with forbidden distant edge placements for a fixed bandwidth bound. Optimization needs an exact bound encoding or decision-search route.
• 37. Betweenness → QUBO: Pairwise ordering/transitivity plus a local betweenness penalty or gadget. Derive the exact local quadratic representation and auxiliary count.

P4 — Dedicated formulation research and new connectivity

• 38. JobShopScheduling → QUBO: Compare time-indexed operation starts/conflicts with disjunctive order/binary timing. Currently no outgoing rule in the scanned checkout. A fixed-horizon decision formulation does not by itself implement the makespan optimization model.
• 39. StaffScheduling → QUBO: Binary worker counts per schedule, coverage surplus and worker-budget slack. Currently no outgoing rule in the scanned checkout; schedule multiplicities are integers, not Boolean choices.
• 40. OpenShopScheduling → QUBO: Operation-start choices, job/machine conflicts and exact makespan encoding. Cover optimization and the existing Decision wrapper separately.
• 41. FlowShopScheduling → QUBO: Common job-permutation choices with timing or permutation-consistent time indexing. Preserve the same job order on all machines; ordinary job-shop constraints are insufficient.
• 42. PreemptiveScheduling → QUBO: Activity bits, exact processing amounts, capacities, finish-before-start precedence and makespan. Preserve interrupted execution and zero-length/boundary cases.
• 43. SequencingWithDeadlinesAndSetUpTimes → QUBO: Position or immediate-successor choices with compiler-switch/setup logic and completion/deadline arithmetic. Setup affects all subsequent completion times.
• 44. SequencingToMinimizeMaximumCumulativeCost → QUBO: Position assignment, a maximum-prefix variable and exact prefix-bound penalties. Signed cumulative costs and objective recovery need a dedicated proof.
• 45. ProductionPlanning → QUBO: Binary production/inventory quantities, setup indicators, balance equations and cost-budget penalties. Significant arithmetic remains.
• 46. RegisterSufficiency → QUBO: Instruction-order encoding with liveness/register-count constraints. Liveness is not merely a fixed pairwise interference relation.
• 47. RootedTreeStorageAssignment → QUBO: Encoded assignments with tree-dependent storage constraints. Establish a dedicated source-specific construction and extraction proof.

Correctness and acceptance criteria for each implemented rule

• Resolve exact source/target variants, witness types and value domains. Use QUBO for exact integer optimization where appropriate and Decision<QUBO> for feasibility thresholds; ExpectedRetrievalCost requires a separate f64 analysis. Do not silently turn optimization into fixed-bound feasibility.
• Specify the construction, penalty bound, omitted constant, feasibility/optimality proof and extraction map. Prove handling of infeasible sources: a QUBO always has configurations, so an arbitrary target optimum must not be reported as a valid source witness.
• Preserve the source's actual accepted domain, including signed/zero data where accepted, duplicates, empty inputs, precedence cycles and out-of-range requirements. Return typed overflow/construction/extraction errors.
• Complete repository-required mathematical verification, including independent constructor/adversary checks, before implementation.
• Write meaningful failing behavior tests first. Compare independently enumerated source solutions against all target optima on small cases; test restored values, NO cases, malformed target witnesses and arithmetic boundaries.
• Derive every exact/upper-bound parameter formula from the full construction and cover it through parameter_formula_validation. Show actual counts separately from conservative symbolic bounds.
• Exercise registered chains end to end, including affected upstream reductions. Compare existing direct/indirect alternatives by exact variants.
• Add rule registration, canonical example, tests and a theorem/proof in docs/paper/reductions.typ. Use the existing sparse QUBO::from_entries constructor; avoid a new general encoding framework unless multiple finished rules justify it.
• Run required formatting, lint, tests, paper and coverage gates under rust-dev limits. Keep tests under five seconds and satisfy the repository's new-code coverage requirement.
• Record measured size/coefficient tradeoffs. Do not claim annealer fit without an embedding/precision assessment.

Existing work and exclusions

• Related metadata/composition work: Make reduction size formulas available end-to-end (ILP → QUBO first) #1175 and Make reduction size overhead exact and verifiable before Pareto comparison #1125.
• Existing observed conversion-cost report: Timeout when using the library #1152.
• Existing graph-connectivity tracker: [Meta] Connect isolated problem types to the reduction graph #610.
• Existing direct-formulation discussion: Convert a problem to QUBO problem #18.
• Existing SAT auxiliary-sharing improvement: [Enhancement] Reduce 3SAT-to-QUBO auxiliary variables through shared literal pairs #1150.
• Existing MaxCut → QUBO proposal: [Rule] MaxCut to QUBO #168; link and compare its SpinGlass route rather than opening a duplicate.
• Existing direct rules such as SAT, coloring, TSP, knapsack, graph partitioning, multiway cut, paint shop, closest vector and inverse kinematics are baselines, not new unchecked items in this list.
• Additional MIS, vertex-cover, clique and set-packing shortcuts must be compared with already-small routes; fewer hops alone does not prove a smaller encoding.

References and limits of the evidence

1. O’Gorman et al., Bayesian Network Structure Learning Using Quantum Annealing, §3.3, Eq. (22): pairwise order variables and quadratic transitivity penalties. Applying this to scheduling/ranking objectives is a proposed adaptation.
2. Venturelli et al., job-shop QUBO formulation, §II: one-hot operation starts, machine conflicts and precedence conflicts. Its fixed-horizon decision formulation is distinct from makespan optimization.
3. Zhang, Lo Bianco and Beck, Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware (2022): direct time-indexed and disjunctive formulations and scalability tradeoffs.
4. Lucas, Ising formulations of many NP problems (2014): standard assignment, covering and partitioning penalties.
5. Glover, Kochenberger and Du, A Tutorial on Formulating and Using QUBO Models: quadratic objectives and penalty-based formulations.

The scan and literature review identify opportunities; no proposed Rust implementation, complete correctness certificate, benchmark or hardware embedding has been validated for this tracker.

P5 — Wider ILP-entry inventory for future triage

The source scan found 141 source-to-ILP declarations across 140 distinct source expressions, excluding ILP casts and QUBO → ILP. This appendix is reproducible source-level evidence, not 141 new rules: it includes P1–P4 candidates, existing direct-QUBO baselines, decision wrappers and macro placeholders. It does not expand every runtime variant or prove that a source-specific formulation improves the existing route. Floating-point targets need separate numeric treatment.