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

problemreductions/rules/
mod.rs
