problemreductions/rules/
mod.rs

1//! Reduction rules between NP-hard problems.
2
3pub mod analysis;
4pub mod cost;
5pub mod registry;
6pub use cost::{
7    CustomCost, Minimize, MinimizeOutputSize, MinimizeSteps, MinimizeStepsThenOverhead, PathCostFn,
8};
9pub use registry::{EdgeCapabilities, ReductionEntry, ReductionOverhead};
10
11pub(crate) mod bicliquecover_bmf;
12pub(crate) mod bmf_bicliquecover;
13pub(crate) mod circuit_sat;
14pub(crate) mod circuit_spinglass;
15mod closestvectorproblem_qubo;
16pub(crate) mod coloring_qubo;
17pub(crate) mod decisionminimumdominatingset_minimumsummulticenter;
18pub(crate) mod decisionminimumdominatingset_minmaxmulticenter;
19pub(crate) mod decisionminimumvertexcover_hamiltoniancircuit;
20pub(crate) mod exactcoverby3sets_algebraicequationsovergf2;
21pub(crate) mod exactcoverby3sets_maximumsetpacking;
22pub(crate) mod exactcoverby3sets_minimumaxiomset;
23pub(crate) mod exactcoverby3sets_minimumfaultdetectiontestset;
24pub(crate) mod exactcoverby3sets_staffscheduling;
25pub(crate) mod exactcoverby3sets_subsetproduct;
26pub(crate) mod factoring_circuit;
27mod graph;
28pub(crate) mod graph_helpers;
29pub(crate) mod graphpartitioning_maxcut;
30pub(crate) mod graphpartitioning_qubo;
31pub(crate) mod hamiltoniancircuit_biconnectivityaugmentation;
32pub(crate) mod hamiltoniancircuit_bottlenecktravelingsalesman;
33pub(crate) mod hamiltoniancircuit_hamiltonianpath;
34pub(crate) mod hamiltoniancircuit_longestcircuit;
35pub(crate) mod hamiltoniancircuit_quadraticassignment;
36pub(crate) mod hamiltoniancircuit_ruralpostman;
37pub(crate) mod hamiltoniancircuit_stackercrane;
38pub(crate) mod hamiltoniancircuit_strongconnectivityaugmentation;
39pub(crate) mod hamiltoniancircuit_travelingsalesman;
40pub(crate) mod hamiltonianpath_degreeconstrainedspanningtree;
41pub(crate) mod hamiltonianpath_isomorphicspanningtree;
42pub(crate) mod hamiltonianpathbetweentwovertices_longestpath;
43pub(crate) mod ilp_i32_ilp_bool;
44#[cfg(feature = "ilp-solver")]
45pub(crate) mod integerknapsack_ilp;
46pub(crate) mod kclique_balancedcompletebipartitesubgraph;
47pub(crate) mod kclique_conjunctivebooleanquery;
48pub(crate) mod kclique_subgraphisomorphism;
49mod kcoloring_casts;
50pub(crate) mod kcoloring_clustering;
51pub(crate) mod kcoloring_partitionintocliques;
52pub(crate) mod kcoloring_twodimensionalconsecutivesets;
53mod knapsack_qubo;
54pub(crate) mod ksatisfiability_acyclicpartition;
55mod ksatisfiability_casts;
56pub(crate) mod ksatisfiability_cyclicordering;
57pub(crate) mod ksatisfiability_decisionminimumvertexcover;
58pub(crate) mod ksatisfiability_directedtwocommodityintegralflow;
59pub(crate) mod ksatisfiability_feasibleregisterassignment;
60pub(crate) mod ksatisfiability_kclique;
61pub(crate) mod ksatisfiability_kernel;
62pub(crate) mod ksatisfiability_minimumvertexcover;
63pub(crate) mod ksatisfiability_monochromatictriangle;
64pub(crate) mod ksatisfiability_oneinthreesatisfiability;
65pub(crate) mod ksatisfiability_preemptivescheduling;
66pub(crate) mod ksatisfiability_quadraticcongruences;
67pub(crate) mod ksatisfiability_quadraticdiophantineequations;
68pub(crate) mod ksatisfiability_qubo;
69pub(crate) mod ksatisfiability_registersufficiency;
70pub(crate) mod ksatisfiability_simultaneousincongruences;
71pub(crate) mod ksatisfiability_subsetsum;
72pub(crate) mod ksatisfiability_timetabledesign;
73pub(crate) mod longestcommonsubsequence_maximumindependentset;
74pub(crate) mod maxcut_minimumcutintoboundedsets;
75pub(crate) mod maximum2satisfiability_maxcut;
76pub(crate) mod maximumclique_maximumindependentset;
77mod maximumindependentset_casts;
78mod maximumindependentset_gridgraph;
79pub(crate) mod maximumindependentset_integralflowbundles;
80pub(crate) mod maximumindependentset_maximumclique;
81pub(crate) mod maximumindependentset_maximumsetpacking;
82mod maximumindependentset_triangular;
83pub(crate) mod maximummatching_maximumsetpacking;
84mod maximumsetpacking_casts;
85pub(crate) mod maximumsetpacking_qubo;
86pub(crate) mod minimumfeedbackarcset_maximumlikelihoodranking;
87pub(crate) mod minimumfeedbackvertexset_minimumcodegenerationunlimitedregisters;
88pub(crate) mod minimummultiwaycut_qubo;
89pub(crate) mod minimumvertexcover_ensemblecomputation;
90pub(crate) mod minimumvertexcover_longestcommonsubsequence;
91pub(crate) mod minimumvertexcover_maximumindependentset;
92pub(crate) mod minimumvertexcover_minimumfeedbackarcset;
93pub(crate) mod minimumvertexcover_minimumfeedbackvertexset;
94pub(crate) mod minimumvertexcover_minimumhittingset;
95pub(crate) mod minimumvertexcover_minimummaximalmatching;
96pub(crate) mod minimumvertexcover_minimumsetcovering;
97pub(crate) mod minimumvertexcover_minimumweightandorgraph;
98pub(crate) mod naesatisfiability_maxcut;
99pub(crate) mod naesatisfiability_partitionintoperfectmatchings;
100pub(crate) mod naesatisfiability_setsplitting;
101pub(crate) mod paintshop_qubo;
102pub(crate) mod partition_binpacking;
103pub(crate) mod partition_cosineproductintegration;
104pub(crate) mod partition_knapsack;
105pub(crate) mod partition_multiprocessorscheduling;
106pub(crate) mod partition_openshopscheduling;
107pub(crate) mod partition_productionplanning;
108pub(crate) mod partition_sequencingtominimizetardytaskweight;
109pub(crate) mod partition_subsetsum;
110pub(crate) mod partitionintocliques_minimumcoveringbycliques;
111pub(crate) mod partitionintopathsoflength2_boundedcomponentspanningforest;
112pub(crate) mod rootedtreearrangement_rootedtreestorageassignment;
113pub(crate) mod sat_circuitsat;
114pub(crate) mod sat_coloring;
115pub(crate) mod sat_ksat;
116pub(crate) mod sat_maximumindependentset;
117pub(crate) mod sat_minimumdominatingset;
118pub(crate) mod satisfiability_integralflowhomologousarcs;
119pub(crate) mod satisfiability_maximum2satisfiability;
120pub(crate) mod satisfiability_naesatisfiability;
121pub(crate) mod satisfiability_nontautology;
122pub(crate) mod setsplitting_betweenness;
123mod spinglass_casts;
124pub(crate) mod spinglass_maxcut;
125pub(crate) mod spinglass_qubo;
126pub(crate) mod subsetsum_closestvectorproblem;
127pub(crate) mod subsetsum_integerexpressionmembership;
128pub(crate) mod subsetsum_integerknapsack;
129pub(crate) mod subsetsum_partition;
130#[cfg(test)]
131pub(crate) mod test_helpers;
132pub(crate) mod threedimensionalmatching_threepartition;
133pub(crate) mod threepartition_resourceconstrainedscheduling;
134pub(crate) mod threepartition_sequencingwithreleasetimesanddeadlines;
135mod traits;
136pub(crate) mod travelingsalesman_qubo;
137
138pub mod unitdiskmapping;
139
140#[cfg(feature = "ilp-solver")]
141pub(crate) mod acyclicpartition_ilp;
142#[cfg(feature = "ilp-solver")]
143pub(crate) mod balancedcompletebipartitesubgraph_ilp;
144#[cfg(feature = "ilp-solver")]
145pub(crate) mod biconnectivityaugmentation_ilp;
146#[cfg(feature = "ilp-solver")]
147pub(crate) mod binpacking_ilp;
148#[cfg(feature = "ilp-solver")]
149pub(crate) mod bmf_ilp;
150#[cfg(feature = "ilp-solver")]
151pub(crate) mod bottlenecktravelingsalesman_ilp;
152#[cfg(feature = "ilp-solver")]
153pub(crate) mod boundedcomponentspanningforest_ilp;
154#[cfg(feature = "ilp-solver")]
155pub(crate) mod capacityassignment_ilp;
156#[cfg(feature = "ilp-solver")]
157pub(crate) mod circuit_ilp;
158#[cfg(feature = "ilp-solver")]
159pub(crate) mod clustering_ilp;
160#[cfg(feature = "ilp-solver")]
161pub(crate) mod coloring_ilp;
162#[cfg(feature = "ilp-solver")]
163pub(crate) mod consecutiveblockminimization_ilp;
164#[cfg(feature = "ilp-solver")]
165pub(crate) mod consecutiveonesmatrixaugmentation_ilp;
166#[cfg(feature = "ilp-solver")]
167pub(crate) mod consecutiveonessubmatrix_ilp;
168#[cfg(feature = "ilp-solver")]
169pub(crate) mod consistencyofdatabasefrequencytables_ilp;
170#[cfg(feature = "ilp-solver")]
171pub(crate) mod directedhamiltonianpath_ilp;
172#[cfg(feature = "ilp-solver")]
173pub(crate) mod directedtwocommodityintegralflow_ilp;
174#[cfg(feature = "ilp-solver")]
175pub(crate) mod disjointconnectingpaths_ilp;
176#[cfg(feature = "ilp-solver")]
177pub(crate) mod exactcoverby3sets_ilp;
178#[cfg(feature = "ilp-solver")]
179pub(crate) mod expectedretrievalcost_ilp;
180#[cfg(feature = "ilp-solver")]
181pub(crate) mod factoring_ilp;
182#[cfg(feature = "ilp-solver")]
183pub(crate) mod feasibleregisterassignment_ilp;
184#[cfg(feature = "ilp-solver")]
185pub(crate) mod flowshopscheduling_ilp;
186#[cfg(feature = "ilp-solver")]
187pub(crate) mod graphpartitioning_ilp;
188#[cfg(feature = "ilp-solver")]
189pub(crate) mod hamiltonianpath_ilp;
190#[cfg(feature = "ilp-solver")]
191mod ilp_bool_ilp_i32;
192#[cfg(feature = "ilp-solver")]
193pub(crate) mod ilp_helpers;
194#[cfg(feature = "ilp-solver")]
195pub(crate) mod ilp_qubo;
196#[cfg(feature = "ilp-solver")]
197pub(crate) mod integralflowbundles_ilp;
198#[cfg(feature = "ilp-solver")]
199pub(crate) mod integralflowhomologousarcs_ilp;
200#[cfg(feature = "ilp-solver")]
201pub(crate) mod integralflowwithmultipliers_ilp;
202#[cfg(feature = "ilp-solver")]
203pub(crate) mod isomorphicspanningtree_ilp;
204#[cfg(feature = "ilp-solver")]
205pub(crate) mod kclique_ilp;
206#[cfg(feature = "ilp-solver")]
207pub(crate) mod knapsack_ilp;
208#[cfg(feature = "ilp-solver")]
209pub(crate) mod lengthboundeddisjointpaths_ilp;
210#[cfg(feature = "ilp-solver")]
211pub(crate) mod longestcircuit_ilp;
212#[cfg(feature = "ilp-solver")]
213pub(crate) mod longestcommonsubsequence_ilp;
214#[cfg(feature = "ilp-solver")]
215pub(crate) mod longestpath_ilp;
216#[cfg(feature = "ilp-solver")]
217pub(crate) mod maximalis_ilp;
218#[cfg(feature = "ilp-solver")]
219pub(crate) mod maximum2satisfiability_ilp;
220#[cfg(feature = "ilp-solver")]
221pub(crate) mod maximumclique_ilp;
222#[cfg(feature = "ilp-solver")]
223pub(crate) mod maximumdomaticnumber_ilp;
224#[cfg(feature = "ilp-solver")]
225pub(crate) mod maximumleafspanningtree_ilp;
226#[cfg(feature = "ilp-solver")]
227pub(crate) mod maximumlikelihoodranking_ilp;
228#[cfg(feature = "ilp-solver")]
229pub(crate) mod maximummatching_ilp;
230#[cfg(feature = "ilp-solver")]
231pub(crate) mod maximumsetpacking_ilp;
232#[cfg(feature = "ilp-solver")]
233pub(crate) mod minimumcapacitatedspanningtree_ilp;
234#[cfg(feature = "ilp-solver")]
235pub(crate) mod minimumcoveringbycliques_ilp;
236#[cfg(feature = "ilp-solver")]
237pub(crate) mod minimumcutintoboundedsets_ilp;
238#[cfg(feature = "ilp-solver")]
239pub(crate) mod minimumdominatingset_ilp;
240#[cfg(feature = "ilp-solver")]
241pub(crate) mod minimumedgecostflow_ilp;
242#[cfg(feature = "ilp-solver")]
243pub(crate) mod minimumexternalmacrodatacompression_ilp;
244#[cfg(feature = "ilp-solver")]
245pub(crate) mod minimumfaultdetectiontestset_ilp;
246#[cfg(feature = "ilp-solver")]
247pub(crate) mod minimumfeedbackarcset_ilp;
248#[cfg(feature = "ilp-solver")]
249pub(crate) mod minimumfeedbackvertexset_ilp;
250#[cfg(feature = "ilp-solver")]
251pub(crate) mod minimumgraphbandwidth_ilp;
252#[cfg(feature = "ilp-solver")]
253pub(crate) mod minimumhittingset_ilp;
254#[cfg(feature = "ilp-solver")]
255pub(crate) mod minimuminternalmacrodatacompression_ilp;
256#[cfg(feature = "ilp-solver")]
257pub(crate) mod minimummatrixcover_ilp;
258#[cfg(feature = "ilp-solver")]
259pub(crate) mod minimummaximalmatching_ilp;
260#[cfg(feature = "ilp-solver")]
261pub(crate) mod minimummetricdimension_ilp;
262#[cfg(feature = "ilp-solver")]
263pub(crate) mod minimummultiwaycut_ilp;
264#[cfg(feature = "ilp-solver")]
265pub(crate) mod minimumsetcovering_ilp;
266#[cfg(feature = "ilp-solver")]
267pub(crate) mod minimumsummulticenter_ilp;
268#[cfg(feature = "ilp-solver")]
269pub(crate) mod minimumtardinesssequencing_ilp;
270#[cfg(feature = "ilp-solver")]
271pub(crate) mod minimumweightdecoding_ilp;
272#[cfg(feature = "ilp-solver")]
273pub(crate) mod minmaxmulticenter_ilp;
274#[cfg(feature = "ilp-solver")]
275pub(crate) mod mixedchinesepostman_ilp;
276#[cfg(feature = "ilp-solver")]
277pub(crate) mod monochromatictriangle_ilp;
278#[cfg(feature = "ilp-solver")]
279pub(crate) mod multiplecopyfileallocation_ilp;
280#[cfg(feature = "ilp-solver")]
281pub(crate) mod multiprocessorscheduling_ilp;
282#[cfg(feature = "ilp-solver")]
283pub(crate) mod naesatisfiability_ilp;
284#[cfg(feature = "ilp-solver")]
285pub(crate) mod numericalmatchingwithtargetsums_ilp;
286#[cfg(feature = "ilp-solver")]
287pub(crate) mod openshopscheduling_ilp;
288#[cfg(feature = "ilp-solver")]
289pub(crate) mod optimallineararrangement_ilp;
290#[cfg(feature = "ilp-solver")]
291pub(crate) mod optimumcommunicationspanningtree_ilp;
292#[cfg(feature = "ilp-solver")]
293pub(crate) mod paintshop_ilp;
294#[cfg(feature = "ilp-solver")]
295pub(crate) mod partiallyorderedknapsack_ilp;
296#[cfg(feature = "ilp-solver")]
297pub(crate) mod partitionintopathsoflength2_ilp;
298#[cfg(feature = "ilp-solver")]
299pub(crate) mod partitionintotriangles_ilp;
300#[cfg(feature = "ilp-solver")]
301pub(crate) mod pathconstrainednetworkflow_ilp;
302#[cfg(feature = "ilp-solver")]
303pub(crate) mod precedenceconstrainedscheduling_ilp;
304#[cfg(feature = "ilp-solver")]
305pub(crate) mod preemptivescheduling_ilp;
306#[cfg(feature = "ilp-solver")]
307pub(crate) mod quadraticassignment_ilp;
308#[cfg(feature = "ilp-solver")]
309pub(crate) mod qubo_ilp;
310#[cfg(feature = "ilp-solver")]
311pub(crate) mod rectilinearpicturecompression_ilp;
312#[cfg(feature = "ilp-solver")]
313pub(crate) mod registersufficiency_ilp;
314#[cfg(feature = "ilp-solver")]
315pub(crate) mod resourceconstrainedscheduling_ilp;
316#[cfg(feature = "ilp-solver")]
317pub(crate) mod rootedtreestorageassignment_ilp;
318#[cfg(feature = "ilp-solver")]
319pub(crate) mod ruralpostman_ilp;
320#[cfg(feature = "ilp-solver")]
321pub(crate) mod schedulingtominimizeweightedcompletiontime_ilp;
322#[cfg(feature = "ilp-solver")]
323pub(crate) mod schedulingwithindividualdeadlines_ilp;
324#[cfg(feature = "ilp-solver")]
325pub(crate) mod sequencingtominimizemaximumcumulativecost_ilp;
326#[cfg(feature = "ilp-solver")]
327pub(crate) mod sequencingtominimizetardytaskweight_ilp;
328#[cfg(feature = "ilp-solver")]
329pub(crate) mod sequencingtominimizeweightedcompletiontime_ilp;
330#[cfg(feature = "ilp-solver")]
331pub(crate) mod sequencingtominimizeweightedtardiness_ilp;
332#[cfg(feature = "ilp-solver")]
333pub(crate) mod sequencingwithdeadlinesandsetuptimes_ilp;
334#[cfg(feature = "ilp-solver")]
335pub(crate) mod sequencingwithinintervals_ilp;
336#[cfg(feature = "ilp-solver")]
337pub(crate) mod sequencingwithreleasetimesanddeadlines_ilp;
338#[cfg(feature = "ilp-solver")]
339pub(crate) mod setsplitting_ilp;
340#[cfg(feature = "ilp-solver")]
341pub(crate) mod shortestcommonsupersequence_ilp;
342#[cfg(feature = "ilp-solver")]
343pub(crate) mod shortestweightconstrainedpath_ilp;
344#[cfg(feature = "ilp-solver")]
345pub(crate) mod sparsematrixcompression_ilp;
346#[cfg(feature = "ilp-solver")]
347pub(crate) mod stackercrane_ilp;
348#[cfg(feature = "ilp-solver")]
349pub(crate) mod steinertree_ilp;
350#[cfg(feature = "ilp-solver")]
351pub(crate) mod steinertreeingraphs_ilp;
352#[cfg(feature = "ilp-solver")]
353pub(crate) mod stringtostringcorrection_ilp;
354#[cfg(feature = "ilp-solver")]
355pub(crate) mod strongconnectivityaugmentation_ilp;
356#[cfg(feature = "ilp-solver")]
357pub(crate) mod subgraphisomorphism_ilp;
358#[cfg(feature = "ilp-solver")]
359pub(crate) mod sumofsquarespartition_ilp;
360#[cfg(feature = "ilp-solver")]
361pub(crate) mod threedimensionalmatching_ilp;
362#[cfg(feature = "ilp-solver")]
363pub(crate) mod timetabledesign_ilp;
364#[cfg(feature = "ilp-solver")]
365pub(crate) mod travelingsalesman_ilp;
366#[cfg(feature = "ilp-solver")]
367pub(crate) mod undirectedflowlowerbounds_ilp;
368#[cfg(feature = "ilp-solver")]
369pub(crate) mod undirectedtwocommodityintegralflow_ilp;
370
371pub use graph::{
372    AggregateReductionChain, NeighborInfo, NeighborTree, ReductionChain, ReductionEdgeInfo,
373    ReductionGraph, ReductionMode, ReductionPath, ReductionStep, TraversalFlow,
374};
375pub use traits::{
376    AggregateReductionResult, ReduceTo, ReduceToAggregate, ReductionAutoCast, ReductionResult,
377};
378
379#[cfg(feature = "example-db")]
380pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
381    let mut specs = Vec::new();
382    specs.extend(bicliquecover_bmf::canonical_rule_example_specs());
383    specs.extend(bmf_bicliquecover::canonical_rule_example_specs());
384    specs.extend(circuit_sat::canonical_rule_example_specs());
385    specs.extend(circuit_spinglass::canonical_rule_example_specs());
386    specs.extend(decisionminimumdominatingset_minmaxmulticenter::canonical_rule_example_specs());
387    specs
388        .extend(decisionminimumdominatingset_minimumsummulticenter::canonical_rule_example_specs());
389    specs.extend(decisionminimumvertexcover_hamiltoniancircuit::canonical_rule_example_specs());
390    specs.extend(exactcoverby3sets_staffscheduling::canonical_rule_example_specs());
391    specs.extend(closestvectorproblem_qubo::canonical_rule_example_specs());
392    specs.extend(coloring_qubo::canonical_rule_example_specs());
393    specs.extend(exactcoverby3sets_algebraicequationsovergf2::canonical_rule_example_specs());
394    specs.extend(exactcoverby3sets_minimumfaultdetectiontestset::canonical_rule_example_specs());
395    specs.extend(exactcoverby3sets_minimumaxiomset::canonical_rule_example_specs());
396    specs.extend(exactcoverby3sets_subsetproduct::canonical_rule_example_specs());
397    specs.extend(factoring_circuit::canonical_rule_example_specs());
398    specs.extend(hamiltoniancircuit_biconnectivityaugmentation::canonical_rule_example_specs());
399    specs.extend(hamiltoniancircuit_bottlenecktravelingsalesman::canonical_rule_example_specs());
400    specs.extend(hamiltoniancircuit_hamiltonianpath::canonical_rule_example_specs());
401    specs.extend(hamiltoniancircuit_longestcircuit::canonical_rule_example_specs());
402    specs.extend(hamiltoniancircuit_quadraticassignment::canonical_rule_example_specs());
403    specs.extend(hamiltoniancircuit_ruralpostman::canonical_rule_example_specs());
404    specs.extend(hamiltoniancircuit_stackercrane::canonical_rule_example_specs());
405    specs.extend(hamiltoniancircuit_strongconnectivityaugmentation::canonical_rule_example_specs());
406    specs.extend(hamiltoniancircuit_travelingsalesman::canonical_rule_example_specs());
407    specs.extend(hamiltonianpath_degreeconstrainedspanningtree::canonical_rule_example_specs());
408    specs.extend(graphpartitioning_maxcut::canonical_rule_example_specs());
409    specs.extend(graphpartitioning_qubo::canonical_rule_example_specs());
410    specs.extend(hamiltonianpathbetweentwovertices_longestpath::canonical_rule_example_specs());
411    specs.extend(hamiltonianpath_isomorphicspanningtree::canonical_rule_example_specs());
412    #[cfg(feature = "ilp-solver")]
413    specs.extend(integerknapsack_ilp::canonical_rule_example_specs());
414    specs.extend(kclique_balancedcompletebipartitesubgraph::canonical_rule_example_specs());
415    specs.extend(kclique_conjunctivebooleanquery::canonical_rule_example_specs());
416    specs.extend(kclique_subgraphisomorphism::canonical_rule_example_specs());
417    specs.extend(kcoloring_clustering::canonical_rule_example_specs());
418    specs.extend(kcoloring_partitionintocliques::canonical_rule_example_specs());
419    specs.extend(kcoloring_twodimensionalconsecutivesets::canonical_rule_example_specs());
420    specs.extend(knapsack_qubo::canonical_rule_example_specs());
421    specs.extend(longestcommonsubsequence_maximumindependentset::canonical_rule_example_specs());
422    specs.extend(ksatisfiability_cyclicordering::canonical_rule_example_specs());
423    specs.extend(ksatisfiability_acyclicpartition::canonical_rule_example_specs());
424    specs.extend(ksatisfiability_decisionminimumvertexcover::canonical_rule_example_specs());
425    specs.extend(ksatisfiability_directedtwocommodityintegralflow::canonical_rule_example_specs());
426    specs.extend(ksatisfiability_feasibleregisterassignment::canonical_rule_example_specs());
427    specs.extend(ksatisfiability_kclique::canonical_rule_example_specs());
428    specs.extend(ksatisfiability_kernel::canonical_rule_example_specs());
429    specs.extend(ksatisfiability_minimumvertexcover::canonical_rule_example_specs());
430    specs.extend(ksatisfiability_monochromatictriangle::canonical_rule_example_specs());
431    specs.extend(ksatisfiability_oneinthreesatisfiability::canonical_rule_example_specs());
432    specs.extend(ksatisfiability_preemptivescheduling::canonical_rule_example_specs());
433    specs.extend(ksatisfiability_quadraticcongruences::canonical_rule_example_specs());
434    specs.extend(ksatisfiability_quadraticdiophantineequations::canonical_rule_example_specs());
435    specs.extend(ksatisfiability_qubo::canonical_rule_example_specs());
436    specs.extend(ksatisfiability_registersufficiency::canonical_rule_example_specs());
437    specs.extend(ksatisfiability_simultaneousincongruences::canonical_rule_example_specs());
438    specs.extend(ksatisfiability_subsetsum::canonical_rule_example_specs());
439    specs.extend(ksatisfiability_timetabledesign::canonical_rule_example_specs());
440    specs.extend(maximum2satisfiability_maxcut::canonical_rule_example_specs());
441    specs.extend(maximumclique_maximumindependentset::canonical_rule_example_specs());
442    specs.extend(maximumindependentset_integralflowbundles::canonical_rule_example_specs());
443    specs.extend(maximumindependentset_maximumclique::canonical_rule_example_specs());
444    specs.extend(maximumindependentset_maximumsetpacking::canonical_rule_example_specs());
445    specs.extend(maximummatching_maximumsetpacking::canonical_rule_example_specs());
446    specs.extend(maximumsetpacking_qubo::canonical_rule_example_specs());
447    specs.extend(minimummultiwaycut_qubo::canonical_rule_example_specs());
448    specs.extend(paintshop_qubo::canonical_rule_example_specs());
449    specs.extend(partition_cosineproductintegration::canonical_rule_example_specs());
450    specs.extend(partition_knapsack::canonical_rule_example_specs());
451    specs.extend(partition_openshopscheduling::canonical_rule_example_specs());
452    specs.extend(partition_productionplanning::canonical_rule_example_specs());
453    specs.extend(partition_sequencingtominimizetardytaskweight::canonical_rule_example_specs());
454    specs.extend(
455        partitionintopathsoflength2_boundedcomponentspanningforest::canonical_rule_example_specs(),
456    );
457    specs.extend(partition_multiprocessorscheduling::canonical_rule_example_specs());
458    specs.extend(partitionintocliques_minimumcoveringbycliques::canonical_rule_example_specs());
459    specs.extend(partition_subsetsum::canonical_rule_example_specs());
460    specs.extend(rootedtreearrangement_rootedtreestorageassignment::canonical_rule_example_specs());
461    specs.extend(naesatisfiability_maxcut::canonical_rule_example_specs());
462    specs.extend(naesatisfiability_partitionintoperfectmatchings::canonical_rule_example_specs());
463    specs.extend(satisfiability_maximum2satisfiability::canonical_rule_example_specs());
464    specs.extend(exactcoverby3sets_maximumsetpacking::canonical_rule_example_specs());
465    specs.extend(maxcut_minimumcutintoboundedsets::canonical_rule_example_specs());
466    specs.extend(partition_binpacking::canonical_rule_example_specs());
467    specs.extend(threedimensionalmatching_threepartition::canonical_rule_example_specs());
468    specs.extend(threepartition_resourceconstrainedscheduling::canonical_rule_example_specs());
469    specs.extend(
470        threepartition_sequencingwithreleasetimesanddeadlines::canonical_rule_example_specs(),
471    );
472    specs.extend(minimumvertexcover_ensemblecomputation::canonical_rule_example_specs());
473    specs.extend(minimumfeedbackarcset_maximumlikelihoodranking::canonical_rule_example_specs());
474    specs.extend(
475        minimumfeedbackvertexset_minimumcodegenerationunlimitedregisters::canonical_rule_example_specs(),
476    );
477    specs.extend(minimumvertexcover_longestcommonsubsequence::canonical_rule_example_specs());
478    specs.extend(minimumvertexcover_maximumindependentset::canonical_rule_example_specs());
479    specs.extend(minimumvertexcover_minimummaximalmatching::canonical_rule_example_specs());
480    specs.extend(minimumvertexcover_minimumfeedbackarcset::canonical_rule_example_specs());
481    specs.extend(minimumvertexcover_minimumfeedbackvertexset::canonical_rule_example_specs());
482    specs.extend(minimumvertexcover_minimumhittingset::canonical_rule_example_specs());
483    specs.extend(minimumvertexcover_minimumsetcovering::canonical_rule_example_specs());
484    specs.extend(minimumvertexcover_minimumweightandorgraph::canonical_rule_example_specs());
485    specs.extend(naesatisfiability_setsplitting::canonical_rule_example_specs());
486    specs.extend(setsplitting_betweenness::canonical_rule_example_specs());
487    specs.extend(satisfiability_integralflowhomologousarcs::canonical_rule_example_specs());
488    specs.extend(satisfiability_naesatisfiability::canonical_rule_example_specs());
489    specs.extend(sat_circuitsat::canonical_rule_example_specs());
490    specs.extend(sat_coloring::canonical_rule_example_specs());
491    specs.extend(sat_ksat::canonical_rule_example_specs());
492    specs.extend(sat_maximumindependentset::canonical_rule_example_specs());
493    specs.extend(sat_minimumdominatingset::canonical_rule_example_specs());
494    specs.extend(satisfiability_nontautology::canonical_rule_example_specs());
495    specs.extend(spinglass_maxcut::canonical_rule_example_specs());
496    specs.extend(spinglass_qubo::canonical_rule_example_specs());
497    specs.extend(subsetsum_closestvectorproblem::canonical_rule_example_specs());
498    specs.extend(subsetsum_integerknapsack::canonical_rule_example_specs());
499    specs.extend(subsetsum_integerexpressionmembership::canonical_rule_example_specs());
500    specs.extend(subsetsum_partition::canonical_rule_example_specs());
501    specs.extend(travelingsalesman_qubo::canonical_rule_example_specs());
502    specs.extend(
503        crate::models::graph::minimum_vertex_cover::decision_canonical_rule_example_specs(),
504    );
505    specs.extend(
506        crate::models::graph::minimum_dominating_set::decision_canonical_rule_example_specs(),
507    );
508    #[cfg(feature = "ilp-solver")]
509    {
510        specs.extend(acyclicpartition_ilp::canonical_rule_example_specs());
511        specs.extend(balancedcompletebipartitesubgraph_ilp::canonical_rule_example_specs());
512        specs.extend(biconnectivityaugmentation_ilp::canonical_rule_example_specs());
513        specs.extend(binpacking_ilp::canonical_rule_example_specs());
514        specs.extend(bmf_ilp::canonical_rule_example_specs());
515        specs.extend(bottlenecktravelingsalesman_ilp::canonical_rule_example_specs());
516        specs.extend(boundedcomponentspanningforest_ilp::canonical_rule_example_specs());
517        specs.extend(capacityassignment_ilp::canonical_rule_example_specs());
518        specs.extend(circuit_ilp::canonical_rule_example_specs());
519        specs.extend(clustering_ilp::canonical_rule_example_specs());
520        specs.extend(coloring_ilp::canonical_rule_example_specs());
521        specs.extend(consecutiveblockminimization_ilp::canonical_rule_example_specs());
522        specs.extend(consecutiveonesmatrixaugmentation_ilp::canonical_rule_example_specs());
523        specs.extend(consecutiveonessubmatrix_ilp::canonical_rule_example_specs());
524        specs.extend(consistencyofdatabasefrequencytables_ilp::canonical_rule_example_specs());
525        specs.extend(directedhamiltonianpath_ilp::canonical_rule_example_specs());
526        specs.extend(directedtwocommodityintegralflow_ilp::canonical_rule_example_specs());
527        specs.extend(disjointconnectingpaths_ilp::canonical_rule_example_specs());
528        specs.extend(exactcoverby3sets_ilp::canonical_rule_example_specs());
529        specs.extend(expectedretrievalcost_ilp::canonical_rule_example_specs());
530        specs.extend(feasibleregisterassignment_ilp::canonical_rule_example_specs());
531        specs.extend(factoring_ilp::canonical_rule_example_specs());
532        specs.extend(flowshopscheduling_ilp::canonical_rule_example_specs());
533        specs.extend(graphpartitioning_ilp::canonical_rule_example_specs());
534        specs.extend(hamiltonianpath_ilp::canonical_rule_example_specs());
535        specs.extend(ilp_qubo::canonical_rule_example_specs());
536        specs.extend(integralflowbundles_ilp::canonical_rule_example_specs());
537        specs.extend(integralflowhomologousarcs_ilp::canonical_rule_example_specs());
538        specs.extend(integralflowwithmultipliers_ilp::canonical_rule_example_specs());
539        specs.extend(isomorphicspanningtree_ilp::canonical_rule_example_specs());
540        specs.extend(kclique_ilp::canonical_rule_example_specs());
541        specs.extend(knapsack_ilp::canonical_rule_example_specs());
542        specs.extend(maximumlikelihoodranking_ilp::canonical_rule_example_specs());
543        specs.extend(lengthboundeddisjointpaths_ilp::canonical_rule_example_specs());
544        specs.extend(longestcircuit_ilp::canonical_rule_example_specs());
545        specs.extend(longestcommonsubsequence_ilp::canonical_rule_example_specs());
546        specs.extend(longestpath_ilp::canonical_rule_example_specs());
547        specs.extend(maximalis_ilp::canonical_rule_example_specs());
548        specs.extend(maximum2satisfiability_ilp::canonical_rule_example_specs());
549        specs.extend(maximumclique_ilp::canonical_rule_example_specs());
550        specs.extend(maximumdomaticnumber_ilp::canonical_rule_example_specs());
551        specs.extend(maximumleafspanningtree_ilp::canonical_rule_example_specs());
552        specs.extend(maximummatching_ilp::canonical_rule_example_specs());
553        specs.extend(maximumsetpacking_ilp::canonical_rule_example_specs());
554        specs.extend(minimumcutintoboundedsets_ilp::canonical_rule_example_specs());
555        specs.extend(minimumdominatingset_ilp::canonical_rule_example_specs());
556        specs.extend(minimummetricdimension_ilp::canonical_rule_example_specs());
557        specs.extend(minimummatrixcover_ilp::canonical_rule_example_specs());
558        specs.extend(minimummaximalmatching_ilp::canonical_rule_example_specs());
559        specs.extend(minimumcapacitatedspanningtree_ilp::canonical_rule_example_specs());
560        specs.extend(minimumcoveringbycliques_ilp::canonical_rule_example_specs());
561        specs.extend(minimumedgecostflow_ilp::canonical_rule_example_specs());
562        specs.extend(minimumexternalmacrodatacompression_ilp::canonical_rule_example_specs());
563        specs.extend(minimumfaultdetectiontestset_ilp::canonical_rule_example_specs());
564        specs.extend(minimuminternalmacrodatacompression_ilp::canonical_rule_example_specs());
565        specs.extend(minimumfeedbackarcset_ilp::canonical_rule_example_specs());
566        specs.extend(minimumfeedbackvertexset_ilp::canonical_rule_example_specs());
567        specs.extend(minimumgraphbandwidth_ilp::canonical_rule_example_specs());
568        specs.extend(minimumhittingset_ilp::canonical_rule_example_specs());
569        specs.extend(minimummultiwaycut_ilp::canonical_rule_example_specs());
570        specs.extend(minimumsetcovering_ilp::canonical_rule_example_specs());
571        specs.extend(minimumweightdecoding_ilp::canonical_rule_example_specs());
572        specs.extend(minimumtardinesssequencing_ilp::canonical_rule_example_specs());
573        specs.extend(minimumsummulticenter_ilp::canonical_rule_example_specs());
574        specs.extend(minmaxmulticenter_ilp::canonical_rule_example_specs());
575        specs.extend(mixedchinesepostman_ilp::canonical_rule_example_specs());
576        specs.extend(monochromatictriangle_ilp::canonical_rule_example_specs());
577        specs.extend(multiplecopyfileallocation_ilp::canonical_rule_example_specs());
578        specs.extend(multiprocessorscheduling_ilp::canonical_rule_example_specs());
579        specs.extend(naesatisfiability_ilp::canonical_rule_example_specs());
580        specs.extend(numericalmatchingwithtargetsums_ilp::canonical_rule_example_specs());
581        specs.extend(openshopscheduling_ilp::canonical_rule_example_specs());
582        specs.extend(optimumcommunicationspanningtree_ilp::canonical_rule_example_specs());
583        specs.extend(optimallineararrangement_ilp::canonical_rule_example_specs());
584        specs.extend(paintshop_ilp::canonical_rule_example_specs());
585        specs.extend(partiallyorderedknapsack_ilp::canonical_rule_example_specs());
586        specs.extend(partitionintopathsoflength2_ilp::canonical_rule_example_specs());
587        specs.extend(partitionintotriangles_ilp::canonical_rule_example_specs());
588        specs.extend(pathconstrainednetworkflow_ilp::canonical_rule_example_specs());
589        specs.extend(precedenceconstrainedscheduling_ilp::canonical_rule_example_specs());
590        specs.extend(preemptivescheduling_ilp::canonical_rule_example_specs());
591        specs.extend(quadraticassignment_ilp::canonical_rule_example_specs());
592        specs.extend(qubo_ilp::canonical_rule_example_specs());
593        specs.extend(rectilinearpicturecompression_ilp::canonical_rule_example_specs());
594        specs.extend(registersufficiency_ilp::canonical_rule_example_specs());
595        specs.extend(resourceconstrainedscheduling_ilp::canonical_rule_example_specs());
596        specs.extend(rootedtreestorageassignment_ilp::canonical_rule_example_specs());
597        specs.extend(ruralpostman_ilp::canonical_rule_example_specs());
598        specs
599            .extend(schedulingtominimizeweightedcompletiontime_ilp::canonical_rule_example_specs());
600        specs.extend(schedulingwithindividualdeadlines_ilp::canonical_rule_example_specs());
601        specs.extend(sequencingtominimizemaximumcumulativecost_ilp::canonical_rule_example_specs());
602        specs.extend(sequencingtominimizetardytaskweight_ilp::canonical_rule_example_specs());
603        specs.extend(sequencingwithdeadlinesandsetuptimes_ilp::canonical_rule_example_specs());
604        specs
605            .extend(sequencingtominimizeweightedcompletiontime_ilp::canonical_rule_example_specs());
606        specs.extend(sequencingtominimizeweightedtardiness_ilp::canonical_rule_example_specs());
607        specs.extend(sequencingwithinintervals_ilp::canonical_rule_example_specs());
608        specs.extend(sequencingwithreleasetimesanddeadlines_ilp::canonical_rule_example_specs());
609        specs.extend(shortestcommonsupersequence_ilp::canonical_rule_example_specs());
610        specs.extend(setsplitting_ilp::canonical_rule_example_specs());
611        specs.extend(shortestweightconstrainedpath_ilp::canonical_rule_example_specs());
612        specs.extend(sparsematrixcompression_ilp::canonical_rule_example_specs());
613        specs.extend(stackercrane_ilp::canonical_rule_example_specs());
614        specs.extend(steinertree_ilp::canonical_rule_example_specs());
615        specs.extend(steinertreeingraphs_ilp::canonical_rule_example_specs());
616        specs.extend(stringtostringcorrection_ilp::canonical_rule_example_specs());
617        specs.extend(strongconnectivityaugmentation_ilp::canonical_rule_example_specs());
618        specs.extend(subgraphisomorphism_ilp::canonical_rule_example_specs());
619        specs.extend(sumofsquarespartition_ilp::canonical_rule_example_specs());
620        specs.extend(timetabledesign_ilp::canonical_rule_example_specs());
621        specs.extend(threedimensionalmatching_ilp::canonical_rule_example_specs());
622        specs.extend(travelingsalesman_ilp::canonical_rule_example_specs());
623        specs.extend(undirectedflowlowerbounds_ilp::canonical_rule_example_specs());
624        specs.extend(undirectedtwocommodityintegralflow_ilp::canonical_rule_example_specs());
625    }
626    specs
627}
628
629/// Generates a variant-cast `ReduceTo` impl with `#[reduction]` registration.
630///
631/// Variant casts convert a problem from one variant to another (e.g.,
632/// `MIS<KingsSubgraph, i32>` -> `MIS<UnitDiskGraph, i32>`). The solution
633/// mapping is identity -- vertex/element indices are preserved.
634///
635/// The problem name is specified once, followed by `<SourceParams> => <TargetParams>`.
636/// This works with any number of type parameters.
637///
638/// # Example
639///
640/// ```text
641/// impl_variant_reduction!(
642///     MaximumIndependentSet,
643///     <KingsSubgraph, i32> => <UnitDiskGraph, i32>,
644///     fields: [num_vertices, num_edges],
645///     |src| MaximumIndependentSet::new(
646///         src.graph().cast_to_parent(), src.weights())
647/// );
648/// ```
649#[macro_export]
650macro_rules! impl_variant_reduction {
651    ($problem:ident,
652     < $($src_param:ty),+ > => < $($dst_param:ty),+ >,
653     fields: [$($field:ident),+],
654     |$src:ident| $body:expr) => {
655        #[$crate::reduction(
656            overhead = {
657                $crate::rules::registry::ReductionOverhead::identity(
658                    &[$(stringify!($field)),+]
659                )
660            }
661        )]
662        impl $crate::rules::ReduceTo<$problem<$($dst_param),+>>
663            for $problem<$($src_param),+>
664        {
665            type Result = $crate::rules::ReductionAutoCast<
666                $problem<$($src_param),+>,
667                $problem<$($dst_param),+>,
668            >;
669            fn reduce_to(&self) -> Self::Result {
670                let $src = self;
671                $crate::rules::ReductionAutoCast::new($body)
672            }
673        }
674    };
675}
problemreductions/rules/mod.rs

problemreductions/rules/
mod.rs
