problemreductions/rules/
mod.rs

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

problemreductions/rules/
mod.rs
