quantrs2_tytan/problem_decomposition/

hierarchical_solver.rs

//! Hierarchical solving methods for large-scale problems

use super::types::*;
use crate::sampler::{SampleResult, Sampler};
use scirs2_core::ndarray::Array2;
use std::collections::HashMap;

/// Hierarchical solver with multi-level approach
pub struct HierarchicalSolver<S: Sampler> {
    /// Base sampler for solving problems
    base_sampler: S,
    /// Hierarchical strategy
    strategy: HierarchicalStrategy,
    /// Coarsening approach
    coarsening: CoarseningStrategy,
    /// Minimum problem size for recursion
    min_problem_size: usize,
    /// Maximum number of levels
    max_levels: usize,
    /// Refinement iterations per level
    refinement_iterations: usize,
}

impl<S: Sampler> HierarchicalSolver<S> {
    /// Create new hierarchical solver
    pub const fn new(base_sampler: S) -> Self {
        Self {
            base_sampler,
            strategy: HierarchicalStrategy::CoarsenSolve,
            coarsening: CoarseningStrategy::VariableClustering,
            min_problem_size: 10,
            max_levels: 10,
            refinement_iterations: 5,
        }
    }

    /// Set hierarchical strategy
    pub const fn with_strategy(mut self, strategy: HierarchicalStrategy) -> Self {
        self.strategy = strategy;
        self
    }

    /// Set coarsening strategy
    pub const fn with_coarsening(mut self, coarsening: CoarseningStrategy) -> Self {
        self.coarsening = coarsening;
        self
    }

    /// Set minimum problem size
    pub const fn with_min_problem_size(mut self, size: usize) -> Self {
        self.min_problem_size = size;
        self
    }

    /// Solve using hierarchical approach
    pub fn solve(
        &mut self,
        qubo: &Array2<f64>,
        var_map: &HashMap<String, usize>,
        shots: usize,
    ) -> Result<SampleResult, String> {
        match self.strategy {
            HierarchicalStrategy::CoarsenSolve => self.coarsen_solve_approach(qubo, var_map, shots),
            HierarchicalStrategy::MultiGrid => self.multigrid_approach(qubo, var_map, shots),
            HierarchicalStrategy::VCycle => self.v_cycle_approach(qubo, var_map, shots),
        }
    }

    /// Coarsen-solve approach: coarsen problem, solve, then refine
    fn coarsen_solve_approach(
        &mut self,
        qubo: &Array2<f64>,
        var_map: &HashMap<String, usize>,
        shots: usize,
    ) -> Result<SampleResult, String> {
        // Build hierarchy
        let hierarchy = self.build_hierarchy(qubo, var_map)?;

        // Solve coarsest level
        let coarsest_level = hierarchy.levels.last().ok_or("Empty hierarchy")?;

        let coarse_results = self
            .base_sampler
            .run_qubo(
                &(coarsest_level.qubo.clone(), coarsest_level.var_map.clone()),
                shots,
            )
            .map_err(|e| format!("Sampler error: {e:?}"))?;

        // Take the best result (first one, since they're sorted by energy)
        let coarse_result = coarse_results
            .into_iter()
            .next()
            .ok_or_else(|| "No solutions found".to_string())?;

        // Refine solution back through levels
        self.refine_through_hierarchy(&hierarchy, coarse_result)
    }

    /// Multi-grid approach with multiple V-cycles
    fn multigrid_approach(
        &mut self,
        qubo: &Array2<f64>,
        var_map: &HashMap<String, usize>,
        shots: usize,
    ) -> Result<SampleResult, String> {
        let initial_results = self
            .base_sampler
            .run_qubo(&(qubo.clone(), var_map.clone()), shots / 4)
            .map_err(|e| format!("Initial sampler error: {e:?}"))?;

        // Take the best result (first one, since they're sorted by energy)
        let mut current_solution = initial_results
            .into_iter()
            .next()
            .ok_or_else(|| "No initial solutions found".to_string())?;

        // Perform multiple V-cycles for refinement
        for _cycle in 0..3 {
            current_solution =
                self.v_cycle_refinement(qubo, var_map, &current_solution, shots / 4)?;
        }

        Ok(current_solution)
    }

    /// V-cycle approach: down to coarse, solve, up with refinement
    fn v_cycle_approach(
        &mut self,
        qubo: &Array2<f64>,
        var_map: &HashMap<String, usize>,
        shots: usize,
    ) -> Result<SampleResult, String> {
        self.v_cycle_refinement(qubo, var_map, &SampleResult::default(), shots)
    }

    /// Single V-cycle for solution refinement
    fn v_cycle_refinement(
        &mut self,
        qubo: &Array2<f64>,
        var_map: &HashMap<String, usize>,
        initial_solution: &SampleResult,
        shots: usize,
    ) -> Result<SampleResult, String> {
        // Build hierarchy
        let hierarchy = self.build_hierarchy(qubo, var_map)?;

        // Restrict solution to coarse levels
        let mut current_solution = initial_solution.clone();

        // Down cycle: restrict to coarser levels
        for level in 1..hierarchy.levels.len() {
            current_solution = self.restrict_solution(&hierarchy, level - 1, &current_solution)?;
        }

        // Solve at coarsest level
        if let Some(coarsest_level) = hierarchy.levels.last() {
            let coarse_results = self
                .base_sampler
                .run_qubo(
                    &(coarsest_level.qubo.clone(), coarsest_level.var_map.clone()),
                    shots,
                )
                .map_err(|e| format!("Coarse sampler error: {e:?}"))?;

            // Take the best result (first one, since they're sorted by energy)
            current_solution = coarse_results
                .into_iter()
                .next()
                .ok_or_else(|| "No coarse solutions found".to_string())?;
        }

        // Up cycle: interpolate and refine
        for level in (0..hierarchy.levels.len() - 1).rev() {
            current_solution =
                self.interpolate_and_refine(&hierarchy, level, &current_solution, shots / 4)?;
        }

        Ok(current_solution)
    }

    /// Build problem hierarchy through coarsening
    fn build_hierarchy(
        &self,
        qubo: &Array2<f64>,
        var_map: &HashMap<String, usize>,
    ) -> Result<Hierarchy, String> {
        let mut levels = Vec::new();
        let mut projections = Vec::new();

        let mut current_qubo = qubo.clone();
        let mut current_var_map = var_map.clone();
        let mut current_size = current_qubo.shape()[0];
        let mut level = 0;

        // Add finest level
        levels.push(HierarchyLevel {
            level,
            qubo: current_qubo.clone(),
            var_map: current_var_map.clone(),
            size: current_size,
        });

        // Build coarser levels
        while current_size > self.min_problem_size && level < self.max_levels {
            let (coarse_qubo, coarse_var_map, projection) =
                self.coarsen_problem(&current_qubo, &current_var_map)?;

            current_qubo = coarse_qubo;
            current_var_map = coarse_var_map;
            current_size = current_qubo.shape()[0];
            level += 1;

            levels.push(HierarchyLevel {
                level,
                qubo: current_qubo.clone(),
                var_map: current_var_map.clone(),
                size: current_size,
            });

            projections.push(projection);
        }

        Ok(Hierarchy {
            levels,
            projections,
        })
    }

    /// Coarsen problem to next level
    fn coarsen_problem(
        &self,
        qubo: &Array2<f64>,
        var_map: &HashMap<String, usize>,
    ) -> Result<(Array2<f64>, HashMap<String, usize>, Projection), String> {
        match self.coarsening {
            CoarseningStrategy::VariableClustering => {
                self.variable_clustering_coarsen(qubo, var_map)
            }
            _ => {
                // Default to variable clustering
                self.variable_clustering_coarsen(qubo, var_map)
            }
        }
    }

    /// Variable clustering coarsening
    fn variable_clustering_coarsen(
        &self,
        qubo: &Array2<f64>,
        _var_map: &HashMap<String, usize>,
    ) -> Result<(Array2<f64>, HashMap<String, usize>, Projection), String> {
        let n = qubo.shape()[0];

        // Cluster strongly connected variables
        let mut clusters = Vec::new();
        let mut assigned = vec![false; n];

        for i in 0..n {
            if !assigned[i] {
                let mut cluster = vec![i];
                assigned[i] = true;

                // Find strongly connected variables
                for j in i + 1..n {
                    if !assigned[j] && qubo[[i, j]].abs() > 0.5 {
                        cluster.push(j);
                        assigned[j] = true;
                    }
                }

                clusters.push(cluster);
            }
        }

        // Build coarse problem
        let num_clusters = clusters.len();
        let mut coarse_qubo = Array2::zeros((num_clusters, num_clusters));

        for (ci, cluster_i) in clusters.iter().enumerate() {
            for (cj, cluster_j) in clusters.iter().enumerate() {
                let mut weight = 0.0;

                for &i in cluster_i {
                    for &j in cluster_j {
                        weight += qubo[[i, j]];
                    }
                }

                coarse_qubo[[ci, cj]] = weight;
            }
        }

        // Build variable mapping
        let mut coarse_var_map = HashMap::new();
        for (ci, _cluster) in clusters.iter().enumerate() {
            let var_name = format!("cluster_{ci}");
            coarse_var_map.insert(var_name, ci);
        }

        // Build projection
        let projection = Projection {
            fine_to_coarse: (0..n)
                .map(|i| clusters.iter().position(|c| c.contains(&i)).unwrap_or(0))
                .collect(),
            coarse_to_fine: clusters,
        };

        Ok((coarse_qubo, coarse_var_map, projection))
    }

    /// Refine solution through hierarchy levels
    fn refine_through_hierarchy(
        &mut self,
        hierarchy: &Hierarchy,
        coarse_solution: SampleResult,
    ) -> Result<SampleResult, String> {
        let mut current_solution = coarse_solution;

        // Interpolate solution from coarse to fine levels
        for level in (0..hierarchy.levels.len() - 1).rev() {
            current_solution = self.interpolate_solution(hierarchy, level, &current_solution)?;

            // Refine at this level
            for _iter in 0..self.refinement_iterations {
                current_solution = self.refine_solution(
                    &hierarchy.levels[level].qubo,
                    &hierarchy.levels[level].var_map,
                    &current_solution,
                    10, // Small number of shots for refinement
                )?;
            }
        }

        Ok(current_solution)
    }

    /// Restrict solution to coarser level
    fn restrict_solution(
        &self,
        hierarchy: &Hierarchy,
        level: usize,
        solution: &SampleResult,
    ) -> Result<SampleResult, String> {
        if level >= hierarchy.projections.len() {
            return Ok(solution.clone());
        }

        let projection = &hierarchy.projections[level];
        let coarse_level = &hierarchy.levels[level + 1];

        // Create restricted solution
        let restricted_solution = SampleResult::default();

        for (var_name, &coarse_idx) in &coarse_level.var_map {
            // Find corresponding fine variables
            let fine_vars = &projection.coarse_to_fine[coarse_idx];

            // Simple majority vote for binary variables
            let mut votes = 0i32;
            for &fine_idx in fine_vars {
                if let Some(fine_var_name) = hierarchy.levels[level]
                    .var_map
                    .iter()
                    .find(|(_, &idx)| idx == fine_idx)
                    .map(|(name, _)| name)
                {
                    if let Some(sample) = solution.best_sample() {
                        if let Some(&value) = sample.get(fine_var_name) {
                            votes += if value { 1 } else { -1 };
                        }
                    }
                }
            }

            // Set coarse variable value
            if let Some(mut best_sample) = restricted_solution.best_sample().cloned() {
                best_sample.insert(var_name.clone(), votes > 0);
            } else {
                let mut new_sample = HashMap::new();
                new_sample.insert(var_name.clone(), votes > 0);
                // Create new SampleResult with this sample
                // This is simplified - in practice would need proper SampleResult construction
            }
        }

        Ok(restricted_solution)
    }

    /// Interpolate solution from coarse to fine level
    fn interpolate_solution(
        &self,
        hierarchy: &Hierarchy,
        level: usize,
        coarse_solution: &SampleResult,
    ) -> Result<SampleResult, String> {
        if level >= hierarchy.projections.len() {
            return Ok(coarse_solution.clone());
        }

        let projection = &hierarchy.projections[level];
        let fine_level = &hierarchy.levels[level];
        let coarse_level = &hierarchy.levels[level + 1];

        let interpolated_solution = SampleResult::default();

        // Interpolate from coarse to fine
        for (fine_var_name, &fine_idx) in &fine_level.var_map {
            let coarse_idx = projection.fine_to_coarse[fine_idx];

            // Find coarse variable name
            if let Some((coarse_var_name, _)) = coarse_level
                .var_map
                .iter()
                .find(|(_, &idx)| idx == coarse_idx)
            {
                if let Some(coarse_sample) = coarse_solution.best_sample() {
                    if let Some(&coarse_value) = coarse_sample.get(coarse_var_name) {
                        // Simple interpolation: copy coarse value to fine
                        if let Some(mut fine_sample) = interpolated_solution.best_sample().cloned()
                        {
                            fine_sample.insert(fine_var_name.clone(), coarse_value);
                        } else {
                            let mut new_sample = HashMap::new();
                            new_sample.insert(fine_var_name.clone(), coarse_value);
                            // Create new SampleResult - simplified
                        }
                    }
                }
            }
        }

        Ok(interpolated_solution)
    }

    /// Interpolate and refine solution at given level
    fn interpolate_and_refine(
        &mut self,
        hierarchy: &Hierarchy,
        level: usize,
        coarse_solution: &SampleResult,
        shots: usize,
    ) -> Result<SampleResult, String> {
        // First interpolate
        let mut interpolated = self.interpolate_solution(hierarchy, level, coarse_solution)?;

        // Then refine
        for _iter in 0..self.refinement_iterations {
            interpolated = self.refine_solution(
                &hierarchy.levels[level].qubo,
                &hierarchy.levels[level].var_map,
                &interpolated,
                shots,
            )?;
        }

        Ok(interpolated)
    }

    /// Refine solution at current level
    fn refine_solution(
        &mut self,
        qubo: &Array2<f64>,
        var_map: &HashMap<String, usize>,
        _current_solution: &SampleResult,
        shots: usize,
    ) -> Result<SampleResult, String> {
        // Use base sampler with warm start from current solution
        // This is simplified - in practice would implement warm starting
        let results = self
            .base_sampler
            .run_qubo(&(qubo.clone(), var_map.clone()), shots)
            .map_err(|e| format!("Refinement sampler error: {e:?}"))?;

        // Take the best result (first one, since they're sorted by energy)
        results
            .into_iter()
            .next()
            .ok_or_else(|| "No refinement results found".to_string())
    }
}

impl Default for SampleResult {
    fn default() -> Self {
        // Simplified default implementation
        // In practice, this would create a proper empty SampleResult
        Self {
            assignments: HashMap::new(),
            energy: 0.0,
            occurrences: 0,
        }
    }
}

impl SampleResult {
    /// Get best sample (simplified implementation)
    pub const fn best_sample(&self) -> Option<&HashMap<String, bool>> {
        Some(&self.assignments)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::sampler::simulated_annealing::SASampler;
    use scirs2_core::ndarray::Array2;
    use std::collections::HashMap;

    #[test]
    fn test_hierarchical_solver_creation() {
        let base_sampler = SASampler::new(None);
        let solver = HierarchicalSolver::new(base_sampler);

        // Test that solver is created with default parameters
        assert_eq!(solver.min_problem_size, 10);
        assert_eq!(solver.max_levels, 10);
    }

    #[test]
    fn test_hierarchy_building() {
        let base_sampler = SASampler::new(None);
        let solver = HierarchicalSolver::new(base_sampler);

        // Create simple QUBO
        let mut qubo = Array2::from_shape_vec(
            (4, 4),
            vec![
                1.0, 0.5, 0.1, 0.0, 0.5, 1.0, 0.0, 0.1, 0.1, 0.0, 1.0, 0.5, 0.0, 0.1, 0.5, 1.0,
            ],
        )
        .expect("QUBO matrix construction should succeed");

        let mut var_map = HashMap::new();
        for i in 0..4 {
            var_map.insert(format!("x{i}"), i);
        }

        let hierarchy = solver.build_hierarchy(&qubo, &var_map);
        assert!(hierarchy.is_ok());

        let h = hierarchy.expect("Hierarchy building should succeed");
        assert!(!h.levels.is_empty());
        assert_eq!(h.levels[0].size, 4); // Finest level should have 4 variables
    }
}