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

problemreductions/models/misc/
mod.rs
