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

problemreductions/rules/
mod.rs
