problemreductions/rules/
closeststring_ilp.rs

1//! Reduction from ClosestString to ILP (Integer Linear Programming).
2//!
3//! Given an alphabet of size `q`, `n` input strings of common length `m`, and
4//! the goal of finding a center `c in Sigma^m` that minimizes the maximum
5//! Hamming distance to every input string, the natural encoding picks one
6//! alphabet symbol at every center position and constrains a radius variable
7//! to upper-bound every per-string Hamming distance:
8//!
9//! - Binary `x_{j, a} in {0, 1}` for `j in {0, ..., m - 1}` and `a in
10//!   {0, ..., q - 1}`: `x_{j, a} = 1` iff the chosen center has symbol `a` at
11//!   position `j`.
12//! - Nonnegative integer radius variable `R`.
13//! - Assignment constraint: `sum_a x_{j, a} = 1` for every position `j`.
14//!   Because every ILP variable is a nonnegative integer, this also forces
15//!   each `x_{j, a} in {0, 1}`.
16//! - Radius constraint per input string `s_i`:
17//!   `R + sum_j x_{j, s_i[j]} >= m`, which is equivalent to `R >= d_H(c, s_i)`.
18//! - Objective: minimize `R`.
19//!
20//! Reference: Ming Li, Bin Ma, and Lusheng Wang, "On the closest string and
21//! substring problems," Journal of the ACM 49(2):157-171, 2002.
22//! <https://doi.org/10.1145/506147.506150>
23
24use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
25use crate::models::misc::ClosestString;
26use crate::reduction;
27use crate::rules::traits::{ReduceTo, ReductionResult};
28
29/// Result of reducing ClosestString to ILP.
30///
31/// Variable layout (`ILP<i64, i64, Bounded>`, all non-negative):
32/// - `x_{j, a}` at index `j * alphabet_size + a` for `j in [0, m)` and
33///   `a in [0, q)`, bounded to `{0, 1}`.
34/// - `R` (radius) at index `m * q`, an integer in `[0, m]`.
35#[derive(Debug, Clone)]
36pub struct ReductionClosestStringToILP {
37    target: ILP<i64, i64, Bounded>,
38    alphabet_size: usize,
39    string_length: usize,
40}
41
42impl ReductionResult for ReductionClosestStringToILP {
43    type Source = ClosestString;
44    type Target = ILP<i64, i64, Bounded>;
45
46    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
47        &self.target
48    }
49
50    /// Decode the integer ILP assignment into the source center config.
51    ///
52    /// For every position `j`, choose the unique alphabet symbol `a` with
53    /// `x_{j, a} = 1`.
54    fn extract_solution(
55        &self,
56        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
57    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
58        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
59
60        let q = self.alphabet_size;
61        let mut center = Vec::with_capacity(self.string_length);
62        for position in 0..self.string_length {
63            let block = &target_solution[position * q..(position + 1) * q];
64            let mut selected = block.iter().enumerate().filter(|(_, value)| **value == 1);
65            let symbol = selected.next().map(|(symbol, _)| symbol).ok_or_else(|| {
66                crate::rules::ExtractionError::invalid(format!(
67                    "center position {position} has no selected symbol"
68                ))
69            })?;
70            if selected.next().is_some() || block.iter().any(|&value| value > 1) {
71                return Err(crate::rules::ExtractionError::invalid(format!(
72                    "center position {position} is not one-hot"
73                )));
74            }
75            center.push(symbol);
76        }
77        Ok(center)
78    }
79}
80
81#[reduction(transform = {
82    exact {
83        num_vars = "alphabet_size * string_length + 1",
84        num_constraints = "string_length + num_strings",
85        num_nonzeros = "alphabet_size * string_length + num_strings * (string_length + 1)",
86    },
87    upper_bound {
88        max_constraint_magnitude_bits = "string_length + 1",
89    },
90})]
91impl ReduceTo<ILP<i64, i64, Bounded>> for ClosestString {
92    type Result = ReductionClosestStringToILP;
93
94    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
95        let q = self.alphabet_size();
96        let m = self.string_length();
97        let strings = self.strings();
98        let n = strings.len();
99
100        let x_idx = |j: usize, a: usize| -> usize { j * q + a };
101        let r_idx = q * m;
102        let num_vars = q * m + 1;
103
104        let mut constraints: Vec<LinearConstraint> = Vec::with_capacity(m + n);
105
106        // Assignment constraints: exactly one symbol per center position.
107        // Together with the non-negativity built into `ILP<i64, i64, Bounded>`, this also
108        // forces every x_{j, a} to lie in {0, 1}.
109        for j in 0..m {
110            let terms: Vec<(usize, i64)> = (0..q).map(|a| (x_idx(j, a), 1)).collect();
111            constraints.push(LinearConstraint::eq(terms, 1));
112        }
113
114        // Radius constraints: R + sum_j x_{j, s_i[j]} >= m.
115        // Equivalently, R >= m - sum_j x_{j, s_i[j]} = d_H(c, s_i).
116        for s in strings.iter() {
117            let mut terms: Vec<(usize, i64)> = Vec::with_capacity(m + 1);
118            terms.push((r_idx, 1));
119            for (j, &symbol) in s.iter().enumerate() {
120                terms.push((x_idx(j, symbol), 1));
121            }
122            constraints.push(LinearConstraint::ge(
123                terms,
124                Self::exact_i64(m, "encoding the string length")?,
125            ));
126        }
127
128        // Objective: minimize R.
129        let objective = vec![(r_idx, 1)];
130
131        // Every center has Hamming distance at most the string length, so an optimum has R <= m.
132        let mut variables = vec![IntegerVariable::binary(); num_vars];
133        variables[r_idx] = IntegerVariable::new(
134            Some(0),
135            Some(Self::exact_i64(m, "bounding the Hamming radius")?),
136        )
137        .map_err(Self::target_construction)?;
138
139        let target =
140            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Minimize)
141                .map_err(Self::target_construction)?;
142
143        Ok(ReductionClosestStringToILP {
144            target,
145            alphabet_size: q,
146            string_length: m,
147        })
148    }
149}
150
151#[cfg(feature = "example-db")]
152pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
153    vec![crate::example_db::specs::RuleExampleSpec {
154        id: "closeststring_to_ilp",
155        build: || {
156            // Canonical issue #1032 instance: binary alphabet, the four length-3
157            // strings 000, 011, 101, 110. Optimum radius is 2 (achieved by any
158            // binary length-3 center, e.g. 000).
159            let source = ClosestString::new(
160                2,
161                vec![vec![0, 0, 0], vec![0, 1, 1], vec![1, 0, 1], vec![1, 1, 0]],
162            );
163            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
164        },
165    }]
166}
167
168#[cfg(test)]
169#[path = "../unit_tests/rules/closeststring_ilp.rs"]
170mod tests;
problemreductions/rules/closeststring_ilp.rs

problemreductions/rules/
closeststring_ilp.rs
