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<i32>`, 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<i32>,
38    alphabet_size: usize,
39    string_length: usize,
40}
41
42impl ReductionResult for ReductionClosestStringToILP {
43    type Source = ClosestString;
44    type Target = ILP<i32>;
45
46    fn target_problem(&self) -> &ILP<i32> {
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`. If the target assignment is missing or none of the
54    /// per-position `x_{j, *}` variables are set to 1, we fall back to symbol
55    /// `0` so the returned vector still has the expected length; partial /
56    /// infeasible ILP solutions are the caller's responsibility.
57    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
58        let q = self.alphabet_size;
59        (0..self.string_length)
60            .map(|j| {
61                (0..q)
62                    .find(|&a| target_solution.get(j * q + a).copied().unwrap_or(0) == 1)
63                    .unwrap_or(0)
64            })
65            .collect()
66    }
67}
68
69#[reduction(
70    overhead = {
71        num_vars = "alphabet_size * string_length + 1",
72        num_constraints = "string_length + num_strings",
73    }
74)]
75impl ReduceTo<ILP<i32>> for ClosestString {
76    type Result = ReductionClosestStringToILP;
77
78    fn reduce_to(&self) -> Self::Result {
79        let q = self.alphabet_size();
80        let m = self.string_length();
81        let strings = self.strings();
82        let n = strings.len();
83
84        let x_idx = |j: usize, a: usize| -> usize { j * q + a };
85        let r_idx = q * m;
86        let num_vars = q * m + 1;
87
88        let mut constraints: Vec<LinearConstraint> = Vec::with_capacity(m + n);
89
90        // Assignment constraints: exactly one symbol per center position.
91        // Together with the non-negativity built into ILP<i32>, this also
92        // forces every x_{j, a} to lie in {0, 1}.
93        for j in 0..m {
94            let terms: Vec<(usize, f64)> = (0..q).map(|a| (x_idx(j, a), 1.0)).collect();
95            constraints.push(LinearConstraint::eq(terms, 1.0));
96        }
97
98        // Radius constraints: R + sum_j x_{j, s_i[j]} >= m.
99        // Equivalently, R >= m - sum_j x_{j, s_i[j]} = d_H(c, s_i).
100        for s in strings.iter() {
101            let mut terms: Vec<(usize, f64)> = Vec::with_capacity(m + 1);
102            terms.push((r_idx, 1.0));
103            for (j, &symbol) in s.iter().enumerate() {
104                terms.push((x_idx(j, symbol), 1.0));
105            }
106            constraints.push(LinearConstraint::ge(terms, m as f64));
107        }
108
109        // Objective: minimize R.
110        let objective = vec![(r_idx, 1.0)];
111
112        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
113
114        ReductionClosestStringToILP {
115            target,
116            alphabet_size: q,
117            string_length: m,
118        }
119    }
120}
121
122#[cfg(feature = "example-db")]
123pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
124    vec![crate::example_db::specs::RuleExampleSpec {
125        id: "closeststring_to_ilp",
126        build: || {
127            // Canonical issue #1032 instance: binary alphabet, the four length-3
128            // strings 000, 011, 101, 110. Optimum radius is 2 (achieved by any
129            // binary length-3 center, e.g. 000).
130            let source = ClosestString::new(
131                2,
132                vec![vec![0, 0, 0], vec![0, 1, 1], vec![1, 0, 1], vec![1, 1, 0]],
133            );
134            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
135        },
136    }]
137}
138
139#[cfg(test)]
140#[path = "../unit_tests/rules/closeststring_ilp.rs"]
141mod tests;
problemreductions/rules/closeststring_ilp.rs

problemreductions/rules/
closeststring_ilp.rs
