problemreductions/models/misc/
mod.rs

1//! Miscellaneous problems.
2//!
3//! Problems with unique input structures that don't fit other categories:
4//! - [`AdditionalKey`]: Determine whether a relational schema has an additional candidate key
5//! - [`Betweenness`]: Find a linear ordering satisfying betweenness constraints on triples
6//! - [`BinPacking`]: Bin Packing (minimize bins)
7//! - [`Clustering`]: Partition elements into bounded-diameter clusters
8//! - [`ClosestString`]: Find a center string minimizing the maximum Hamming distance to a set of equal-length input strings
9//! - [`ClosestSubstring`]: Find a center string and a length-ell window per input string minimizing the maximum Hamming distance
10//! - [`CyclicOrdering`]: Find a permutation satisfying cyclic ordering constraints on triples
11//! - [`BoyceCoddNormalFormViolation`]: Boyce-Codd Normal Form Violation (BCNF)
12//! - [`ConsistencyOfDatabaseFrequencyTables`]: Pairwise frequency-table consistency
13//! - [`ConjunctiveBooleanQuery`]: Evaluate a conjunctive Boolean query over relations
14//! - [`ConjunctiveQueryFoldability`]: Conjunctive Query Foldability
15//! - [`DynamicStorageAllocation`]: Assign starting addresses in bounded memory for time-varying items
16//! - [`ExpectedRetrievalCost`]: Allocate records to circular sectors within a latency bound
17//! - [`Factoring`]: Integer factorization
18//! - [`FeasibleRegisterAssignment`]: Determine if a DAG computation can be scheduled without register conflicts under a fixed assignment
19//! - [`IntegerExpressionMembership`]: Membership in a set defined by an integer expression tree
20//! - [`FlowShopScheduling`]: Flow Shop Scheduling (meet deadline on m processors)
21//! - [`GroupingBySwapping`]: Group equal symbols into contiguous blocks by adjacent swaps
22//! - [`JobShopScheduling`]: Minimize makespan with per-job processor routes
23//! - [`Knapsack`]: 0-1 Knapsack (maximize value subject to weight capacity)
24//! - [`MultiprocessorScheduling`]: Schedule tasks on processors to meet a deadline
25//! - [`Numerical3DimensionalMatching`]: Partition W∪X∪Y into m triples each summing to B
26//! - [`NumericalMatchingWithTargetSums`]: Partition X∪Y into m pairs with pair sums matching targets
27//! - [`OpenShopScheduling`]: Open Shop Scheduling (minimize makespan, free task order per job)
28//! - [`LongestCommonSubsequence`]: Longest Common Subsequence
29//! - [`MaximumLikelihoodRanking`]: Find a ranking minimizing total pairwise disagreement
30//! - [`MinimumAxiomSet`]: Find smallest axiom subset whose deductive closure covers all true sentences
31//! - [`MinimumCodeGenerationOneRegister`]: Minimize instruction count for a one-register machine
32//! - [`MinimumCodeGenerationParallelAssignments`]: Minimize backward dependencies when ordering parallel assignments
33//! - [`MinimumCodeGenerationUnlimitedRegisters`]: Minimize instruction count for an unlimited-register machine with 2-address instructions
34//! - [`MinimumDiscretePlanarInverseKinematics`]: Pick one sampled absolute orientation per planar link to reach a target point under consecutive-pair feasibility
35//! - [`MinimumExternalMacroDataCompression`]: Minimize compression cost using external dictionary
36//! - [`MinimumFaultDetectionTestSet`]: Find minimum set of input-output paths covering all internal DAG vertices
37//! - [`MinimumInternalMacroDataCompression`]: Minimize self-referencing compression cost
38//! - [`MinimumRegisterSufficiencyForLoops`]: Minimize registers for loop variable allocation (circular arc coloring)
39//! - [`MinimumWeightAndOrGraph`]: Find minimum-weight solution subgraph in a DAG with AND/OR gates
40//! - [`MinimumTardinessSequencing`]: Minimize tardy tasks in single-machine scheduling
41//! - [`OptimumCommunicationSpanningTree`]: Find spanning tree minimizing total weighted communication cost
42//! - [`PaintShop`]: Minimize color switches in paint shop scheduling
43//! - [`CosineProductIntegration`]: Balanced sign assignment for integer frequencies
44//! - [`NonLivenessFreePetriNet`]: Determine whether a free-choice Petri net is not live
45//! - [`Partition`]: Partition a multiset into two equal-sum subsets
46//! - [`PartiallyOrderedKnapsack`]: Knapsack with precedence constraints
47//! - [`PrecedenceConstrainedScheduling`]: Schedule unit tasks on processors by deadline
48//! - [`PreemptiveScheduling`]: Preemptive parallel scheduling with precedences (minimize makespan)
49//! - [`ProductionPlanning`]: Meet all period demands within capacity and total-cost bounds
50//! - [`RectilinearPictureCompression`]: Cover 1-entries with bounded rectangles
51//! - [`RegisterSufficiency`]: Evaluate DAG computation with bounded registers
52//! - [`ResourceConstrainedScheduling`]: Schedule unit-length tasks on processors with resource constraints
53//! - [`SchedulingWithIndividualDeadlines`]: Meet per-task deadlines on parallel processors
54//! - [`StackerCrane`]: Minimize the total length of a closed walk through required arcs
55//! - [`SequencingToMinimizeMaximumCumulativeCost`]: Keep every cumulative schedule cost prefix under a bound
56//! - [`SequencingToMinimizeTardyTaskWeight`]: Minimize total weight of tardy tasks
57//! - [`SequencingToMinimizeWeightedCompletionTime`]: Minimize total weighted completion time
58//! - [`SequencingToMinimizeWeightedTardiness`]: Decide whether a schedule meets a weighted tardiness bound
59//! - [`SequencingWithDeadlinesAndSetUpTimes`]: Single-machine scheduling feasibility with compiler-switch setup penalties
60//! - [`SequencingWithReleaseTimesAndDeadlines`]: Single-machine scheduling feasibility
61//! - [`SequencingWithinIntervals`]: Schedule tasks within time windows
62//! - [`ShortestCommonSupersequence`]: Find a common supersequence of bounded length
63//! - [`ShortestCommonSuperstring`]: Find a shortest string containing each input as a contiguous substring
64//! - [`SquareTiling`]: Place colored square tiles on an N x N grid with matching edge colors
65//! - [`TimetableDesign`]: Schedule craftsmen on tasks across work periods
66//! - [`StringToStringCorrection`]: String-to-String Correction (derive target via deletions and swaps)
67//! - [`SubsetProduct`]: Find a subset whose product equals exactly a target value
68//! - [`SubsetSum`]: Find a subset summing to exactly a target value
69//! - [`SumOfSquaresPartition`]: Partition integers into K groups minimizing sum of squared group sums
70
71pub(crate) mod additional_key;
72mod betweenness;
73pub(crate) mod biguint_serde;
74mod cyclic_ordering;
75
76/// Decode a Lehmer code into a permutation of `0..n`.
77///
78/// Each element of `config` selects from the remaining items:
79/// `config[i]` must be `< n - i`. Returns `None` if the config is
80/// invalid (wrong length or out-of-range digit).
81pub(crate) fn decode_lehmer(config: &[usize], n: usize) -> Option<Vec<usize>> {
82    if config.len() != n {
83        return None;
84    }
85    let mut available: Vec<usize> = (0..n).collect();
86    let mut schedule = Vec::with_capacity(n);
87    for &digit in config {
88        if digit >= available.len() {
89            return None;
90        }
91        schedule.push(available.remove(digit));
92    }
93    Some(schedule)
94}
95
96/// Decode a direct permutation configuration.
97///
98/// Returns `Some(schedule)` if `config` is a valid permutation of `0..n`,
99/// or `None` otherwise.
100pub(crate) fn decode_permutation(config: &[usize], n: usize) -> Option<Vec<usize>> {
101    if config.len() != n {
102        return None;
103    }
104    let mut seen = vec![false; n];
105    for &task in config {
106        if task >= n || seen[task] {
107            return None;
108        }
109        seen[task] = true;
110    }
111    Some(config.to_vec())
112}
113
114/// Return the Lehmer-code dimension vector `[n, n-1, ..., 1]`.
115pub(crate) fn lehmer_dims(n: usize) -> Vec<usize> {
116    (0..n).rev().map(|i| i + 1).collect()
117}
118mod bin_packing;
119mod boyce_codd_normal_form_violation;
120mod capacity_assignment;
121pub(crate) mod closest_string;
122pub(crate) mod closest_substring;
123pub(crate) mod clustering;
124pub(crate) mod conjunctive_boolean_query;
125pub(crate) mod conjunctive_query_foldability;
126mod consistency_of_database_frequency_tables;
127mod cosine_product_integration;
128mod dynamic_storage_allocation;
129mod ensemble_computation;
130pub(crate) mod expected_retrieval_cost;
131pub(crate) mod factoring;
132mod feasible_register_assignment;
133mod flow_shop_scheduling;
134mod grouping_by_swapping;
135pub(crate) mod integer_expression_membership;
136mod job_shop_scheduling;
137mod knapsack;
138mod kth_largest_m_tuple;
139mod longest_common_subsequence;
140pub(crate) mod maximum_likelihood_ranking;
141mod minimum_axiom_set;
142mod minimum_code_generation_one_register;
143pub(crate) mod minimum_code_generation_parallel_assignments;
144mod minimum_code_generation_unlimited_registers;
145pub(crate) mod minimum_decision_tree;
146pub(crate) mod minimum_discrete_planar_inverse_kinematics;
147pub(crate) mod minimum_disjunctive_normal_form;
148mod minimum_external_macro_data_compression;
149mod minimum_fault_detection_test_set;
150mod minimum_internal_macro_data_compression;
151mod minimum_register_sufficiency_for_loops;
152mod minimum_tardiness_sequencing;
153mod minimum_weight_and_or_graph;
154mod multiprocessor_scheduling;
155mod non_liveness_free_petri_net;
156mod numerical_3_dimensional_matching;
157mod numerical_matching_with_target_sums;
158mod open_shop_scheduling;
159pub(crate) mod optimum_communication_spanning_tree;
160pub(crate) mod paintshop;
161pub(crate) mod partially_ordered_knapsack;
162pub(crate) mod partition;
163mod precedence_constrained_scheduling;
164mod preemptive_scheduling;
165mod production_planning;
166mod rectilinear_picture_compression;
167mod register_sufficiency;
168pub(crate) mod resource_constrained_scheduling;
169mod scheduling_to_minimize_weighted_completion_time;
170mod scheduling_with_individual_deadlines;
171mod sequencing_to_minimize_maximum_cumulative_cost;
172mod sequencing_to_minimize_tardy_task_weight;
173mod sequencing_to_minimize_weighted_completion_time;
174mod sequencing_to_minimize_weighted_tardiness;
175mod sequencing_with_deadlines_and_set_up_times;
176mod sequencing_with_release_times_and_deadlines;
177mod sequencing_within_intervals;
178pub(crate) mod shortest_common_supersequence;
179pub(crate) mod shortest_common_superstring;
180mod square_tiling;
181mod stacker_crane;
182mod staff_scheduling;
183pub(crate) mod string_to_string_correction;
184mod subset_product;
185mod subset_sum;
186pub(crate) mod sum_of_squares_partition;
187mod three_partition;
188mod timetable_design;
189
190pub use additional_key::AdditionalKey;
191pub use betweenness::Betweenness;
192pub use bin_packing::BinPacking;
193pub use boyce_codd_normal_form_violation::BoyceCoddNormalFormViolation;
194pub use capacity_assignment::CapacityAssignment;
195pub use closest_string::ClosestString;
196pub use closest_substring::ClosestSubstring;
197pub use clustering::Clustering;
198pub use conjunctive_boolean_query::{ConjunctiveBooleanQuery, QueryArg, Relation as CbqRelation};
199pub use conjunctive_query_foldability::{ConjunctiveQueryFoldability, Term};
200pub use consistency_of_database_frequency_tables::{
201    ConsistencyOfDatabaseFrequencyTables, FrequencyTable, KnownValue,
202};
203pub use cosine_product_integration::CosineProductIntegration;
204pub use cyclic_ordering::CyclicOrdering;
205pub use dynamic_storage_allocation::DynamicStorageAllocation;
206pub use ensemble_computation::EnsembleComputation;
207pub use expected_retrieval_cost::ExpectedRetrievalCost;
208pub use factoring::Factoring;
209pub use feasible_register_assignment::FeasibleRegisterAssignment;
210pub use flow_shop_scheduling::FlowShopScheduling;
211pub use grouping_by_swapping::GroupingBySwapping;
212pub use integer_expression_membership::{IntExpr, IntegerExpressionMembership};
213pub use job_shop_scheduling::JobShopScheduling;
214pub use knapsack::Knapsack;
215pub use kth_largest_m_tuple::KthLargestMTuple;
216pub use longest_common_subsequence::LongestCommonSubsequence;
217pub use maximum_likelihood_ranking::MaximumLikelihoodRanking;
218pub use minimum_axiom_set::MinimumAxiomSet;
219pub use minimum_code_generation_one_register::MinimumCodeGenerationOneRegister;
220pub use minimum_code_generation_parallel_assignments::MinimumCodeGenerationParallelAssignments;
221pub use minimum_code_generation_unlimited_registers::MinimumCodeGenerationUnlimitedRegisters;
222pub use minimum_decision_tree::MinimumDecisionTree;
223pub use minimum_discrete_planar_inverse_kinematics::MinimumDiscretePlanarInverseKinematics;
224pub use minimum_disjunctive_normal_form::MinimumDisjunctiveNormalForm;
225pub use minimum_external_macro_data_compression::MinimumExternalMacroDataCompression;
226pub use minimum_fault_detection_test_set::MinimumFaultDetectionTestSet;
227pub use minimum_internal_macro_data_compression::MinimumInternalMacroDataCompression;
228pub use minimum_register_sufficiency_for_loops::MinimumRegisterSufficiencyForLoops;
229pub use minimum_tardiness_sequencing::MinimumTardinessSequencing;
230pub use minimum_weight_and_or_graph::MinimumWeightAndOrGraph;
231pub use multiprocessor_scheduling::MultiprocessorScheduling;
232pub use non_liveness_free_petri_net::NonLivenessFreePetriNet;
233pub use numerical_3_dimensional_matching::Numerical3DimensionalMatching;
234pub use numerical_matching_with_target_sums::NumericalMatchingWithTargetSums;
235pub use open_shop_scheduling::OpenShopScheduling;
236pub use optimum_communication_spanning_tree::OptimumCommunicationSpanningTree;
237pub use paintshop::PaintShop;
238pub use partially_ordered_knapsack::PartiallyOrderedKnapsack;
239pub use partition::Partition;
240pub use precedence_constrained_scheduling::PrecedenceConstrainedScheduling;
241pub use preemptive_scheduling::PreemptiveScheduling;
242pub use production_planning::ProductionPlanning;
243pub use rectilinear_picture_compression::RectilinearPictureCompression;
244pub use register_sufficiency::RegisterSufficiency;
245pub use resource_constrained_scheduling::ResourceConstrainedScheduling;
246pub use scheduling_to_minimize_weighted_completion_time::SchedulingToMinimizeWeightedCompletionTime;
247pub use scheduling_with_individual_deadlines::SchedulingWithIndividualDeadlines;
248pub use sequencing_to_minimize_maximum_cumulative_cost::SequencingToMinimizeMaximumCumulativeCost;
249pub use sequencing_to_minimize_tardy_task_weight::SequencingToMinimizeTardyTaskWeight;
250pub use sequencing_to_minimize_weighted_completion_time::SequencingToMinimizeWeightedCompletionTime;
251pub use sequencing_to_minimize_weighted_tardiness::SequencingToMinimizeWeightedTardiness;
252pub use sequencing_with_deadlines_and_set_up_times::SequencingWithDeadlinesAndSetUpTimes;
253pub use sequencing_with_release_times_and_deadlines::SequencingWithReleaseTimesAndDeadlines;
254pub use sequencing_within_intervals::SequencingWithinIntervals;
255pub use shortest_common_supersequence::ShortestCommonSupersequence;
256pub use shortest_common_superstring::ShortestCommonSuperstring;
257pub use square_tiling::SquareTiling;
258pub use stacker_crane::StackerCrane;
259pub use staff_scheduling::StaffScheduling;
260pub use string_to_string_correction::StringToStringCorrection;
261pub use subset_product::SubsetProduct;
262pub use subset_sum::SubsetSum;
263pub use sum_of_squares_partition::SumOfSquaresPartition;
264pub use three_partition::ThreePartition;
265pub use timetable_design::TimetableDesign;
266
267#[cfg(feature = "example-db")]
268pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
269    let mut specs = Vec::new();
270    specs.extend(boyce_codd_normal_form_violation::canonical_model_example_specs());
271    specs.extend(capacity_assignment::canonical_model_example_specs());
272    specs.extend(closest_string::canonical_model_example_specs());
273    specs.extend(closest_substring::canonical_model_example_specs());
274    specs.extend(consistency_of_database_frequency_tables::canonical_model_example_specs());
275    specs.extend(conjunctive_boolean_query::canonical_model_example_specs());
276    specs.extend(conjunctive_query_foldability::canonical_model_example_specs());
277    specs.extend(ensemble_computation::canonical_model_example_specs());
278    specs.extend(expected_retrieval_cost::canonical_model_example_specs());
279    specs.extend(factoring::canonical_model_example_specs());
280    specs.extend(grouping_by_swapping::canonical_model_example_specs());
281    specs.extend(longest_common_subsequence::canonical_model_example_specs());
282    specs.extend(multiprocessor_scheduling::canonical_model_example_specs());
283    specs.extend(open_shop_scheduling::canonical_model_example_specs());
284    specs.extend(paintshop::canonical_model_example_specs());
285    specs.extend(partition::canonical_model_example_specs());
286    specs.extend(production_planning::canonical_model_example_specs());
287    specs.extend(rectilinear_picture_compression::canonical_model_example_specs());
288    specs.extend(scheduling_to_minimize_weighted_completion_time::canonical_model_example_specs());
289    specs.extend(scheduling_with_individual_deadlines::canonical_model_example_specs());
290    specs.extend(sequencing_within_intervals::canonical_model_example_specs());
291    specs.extend(staff_scheduling::canonical_model_example_specs());
292    specs.extend(stacker_crane::canonical_model_example_specs());
293    specs.extend(timetable_design::canonical_model_example_specs());
294    specs.extend(shortest_common_supersequence::canonical_model_example_specs());
295    specs.extend(shortest_common_superstring::canonical_model_example_specs());
296    specs.extend(resource_constrained_scheduling::canonical_model_example_specs());
297    specs.extend(partially_ordered_knapsack::canonical_model_example_specs());
298    specs.extend(string_to_string_correction::canonical_model_example_specs());
299    specs.extend(minimum_tardiness_sequencing::canonical_model_example_specs());
300    specs.extend(sequencing_to_minimize_weighted_completion_time::canonical_model_example_specs());
301    specs.extend(sequencing_to_minimize_weighted_tardiness::canonical_model_example_specs());
302    specs.extend(additional_key::canonical_model_example_specs());
303    specs.extend(sequencing_to_minimize_maximum_cumulative_cost::canonical_model_example_specs());
304    specs.extend(sequencing_to_minimize_tardy_task_weight::canonical_model_example_specs());
305    specs.extend(sequencing_with_deadlines_and_set_up_times::canonical_model_example_specs());
306    specs.extend(sum_of_squares_partition::canonical_model_example_specs());
307    specs.extend(precedence_constrained_scheduling::canonical_model_example_specs());
308    specs.extend(job_shop_scheduling::canonical_model_example_specs());
309    specs.extend(sequencing_with_release_times_and_deadlines::canonical_model_example_specs());
310    specs.extend(flow_shop_scheduling::canonical_model_example_specs());
311    specs.extend(bin_packing::canonical_model_example_specs());
312    specs.extend(knapsack::canonical_model_example_specs());
313    specs.extend(integer_expression_membership::canonical_model_example_specs());
314    specs.extend(subset_product::canonical_model_example_specs());
315    specs.extend(subset_sum::canonical_model_example_specs());
316    specs.extend(numerical_3_dimensional_matching::canonical_model_example_specs());
317    specs.extend(numerical_matching_with_target_sums::canonical_model_example_specs());
318    specs.extend(three_partition::canonical_model_example_specs());
319    specs.extend(cosine_product_integration::canonical_model_example_specs());
320    specs.extend(dynamic_storage_allocation::canonical_model_example_specs());
321    specs.extend(minimum_code_generation_one_register::canonical_model_example_specs());
322    specs.extend(minimum_code_generation_parallel_assignments::canonical_model_example_specs());
323    specs.extend(minimum_code_generation_unlimited_registers::canonical_model_example_specs());
324    specs.extend(minimum_decision_tree::canonical_model_example_specs());
325    specs.extend(minimum_discrete_planar_inverse_kinematics::canonical_model_example_specs());
326    specs.extend(minimum_disjunctive_normal_form::canonical_model_example_specs());
327    specs.extend(minimum_external_macro_data_compression::canonical_model_example_specs());
328    specs.extend(minimum_internal_macro_data_compression::canonical_model_example_specs());
329    specs.extend(minimum_register_sufficiency_for_loops::canonical_model_example_specs());
330    specs.extend(register_sufficiency::canonical_model_example_specs());
331    specs.extend(feasible_register_assignment::canonical_model_example_specs());
332    specs.extend(kth_largest_m_tuple::canonical_model_example_specs());
333    specs.extend(preemptive_scheduling::canonical_model_example_specs());
334    specs.extend(betweenness::canonical_model_example_specs());
335    specs.extend(cyclic_ordering::canonical_model_example_specs());
336    specs.extend(non_liveness_free_petri_net::canonical_model_example_specs());
337    specs.extend(maximum_likelihood_ranking::canonical_model_example_specs());
338    specs.extend(clustering::canonical_model_example_specs());
339    specs.extend(minimum_weight_and_or_graph::canonical_model_example_specs());
340    specs.extend(minimum_fault_detection_test_set::canonical_model_example_specs());
341    specs.extend(minimum_axiom_set::canonical_model_example_specs());
342    specs.extend(optimum_communication_spanning_tree::canonical_model_example_specs());
343    specs.extend(square_tiling::canonical_model_example_specs());
344    specs
345}
problemreductions/models/misc/mod.rs

problemreductions/models/misc/
mod.rs
