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::{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>`, 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>,
38    alphabet_size: usize,
39    string_length: usize,
40}
41
42impl ReductionResult for ReductionClosestStringToILP {
43    type Source = ClosestString;
44    type Target = ILP<i64>;
45
46    fn target_problem(&self) -> &ILP<i64> {
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(
82    transform = exact {
83        num_vars = "alphabet_size * string_length + 1",
84        num_constraints = "string_length + num_strings",
85    },
86    unavailable = {
87        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
88    }
89)]
90impl ReduceTo<ILP<i64>> for ClosestString {
91    type Result = ReductionClosestStringToILP;
92
93    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
94        let q = self.alphabet_size();
95        let m = self.string_length();
96        let strings = self.strings();
97        let n = strings.len();
98
99        let x_idx = |j: usize, a: usize| -> usize { j * q + a };
100        let r_idx = q * m;
101        let num_vars = q * m + 1;
102
103        let mut constraints: Vec<LinearConstraint> = Vec::with_capacity(m + n);
104
105        // Assignment constraints: exactly one symbol per center position.
106        // Together with the non-negativity built into `ILP<i64>`, this also
107        // forces every x_{j, a} to lie in {0, 1}.
108        for j in 0..m {
109            let terms: Vec<(usize, i64)> = (0..q).map(|a| (x_idx(j, a), 1)).collect();
110            constraints.push(LinearConstraint::eq(terms, 1));
111        }
112
113        // Radius constraints: R + sum_j x_{j, s_i[j]} >= m.
114        // Equivalently, R >= m - sum_j x_{j, s_i[j]} = d_H(c, s_i).
115        for s in strings.iter() {
116            let mut terms: Vec<(usize, i64)> = Vec::with_capacity(m + 1);
117            terms.push((r_idx, 1));
118            for (j, &symbol) in s.iter().enumerate() {
119                terms.push((x_idx(j, symbol), 1));
120            }
121            constraints.push(LinearConstraint::ge(
122                terms,
123                Self::exact_i64(m, "encoding the string length")?,
124            ));
125        }
126
127        // Objective: minimize R.
128        let objective = vec![(r_idx, 1)];
129
130        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
131            .map_err(Self::target_construction)?;
132
133        Ok(ReductionClosestStringToILP {
134            target,
135            alphabet_size: q,
136            string_length: m,
137        })
138    }
139}
140
141#[cfg(feature = "example-db")]
142pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
143    vec![crate::example_db::specs::RuleExampleSpec {
144        id: "closeststring_to_ilp",
145        build: || {
146            // Canonical issue #1032 instance: binary alphabet, the four length-3
147            // strings 000, 011, 101, 110. Optimum radius is 2 (achieved by any
148            // binary length-3 center, e.g. 000).
149            let source = ClosestString::new(
150                2,
151                vec![vec![0, 0, 0], vec![0, 1, 1], vec![1, 0, 1], vec![1, 1, 0]],
152            );
153            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
154        },
155    }]
156}
157
158#[cfg(test)]
159#[path = "../unit_tests/rules/closeststring_ilp.rs"]
160mod tests;
problemreductions/rules/closeststring_ilp.rs

problemreductions/rules/
closeststring_ilp.rs
