problemreductions/models/graph/

multiple_choice_branching.rs

//! Multiple Choice Branching problem implementation.
//!
//! Given a directed graph with arc weights, a partition of the arcs, and a
//! threshold, determine whether there exists a high-weight branching that
//! picks at most one arc from each partition group.

use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
use crate::topology::DirectedGraph;
use crate::traits::Problem;
use crate::types::WeightElement;
use num_traits::Zero;
use serde::de::Error as _;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "MultipleChoiceBranching",
        display_name: "Multiple Choice Branching",
        aliases: &[],
        dimensions: &[
            VariantDimension::new("weight", "i64", &["i64"]),
        ],
        category: crate::registry::ProblemCategory::Graph,
        module_path: module_path!(),
        description: "Find a branching with partition constraints and weight at least K",
        fields: MultipleChoiceBranchingCreateSpec::FIELDS,
    }
}

/// The Multiple Choice Branching problem.
///
/// Given a directed graph G = (V, A), arc weights w(a), a partition of A into
/// disjoint groups A_1, ..., A_m, and a threshold K, determine whether there
/// exists a subset A' of arcs such that:
/// - the selected arcs have total weight at least K
/// - every vertex has in-degree at most one in the selected subgraph
/// - the selected subgraph is acyclic
/// - at most one arc is selected from each partition group
#[derive(Debug, Clone, Serialize)]
pub struct MultipleChoiceBranching<W: WeightElement> {
    graph: DirectedGraph,
    weights: Vec<W>,
    partition: Vec<Vec<usize>>,
    threshold: W::Sum,
}

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct MultipleChoiceBranchingCreateSpec {
    /// Directed graph arcs.
    #[create(codec = "arc-list")]
    arcs: Vec<(usize, usize)>,
    /// Vertex count, needed to preserve isolated vertices.
    num_vertices: Option<usize>,
    /// Arc weights w(a) for each arc a in A.
    weights: Vec<i64>,
    /// Partition of arc indices; each arc must appear exactly once.
    partition: Vec<Vec<usize>>,
    /// Weight threshold K.
    threshold: i64,
}

impl TryFrom<MultipleChoiceBranchingCreateSpec> for MultipleChoiceBranching<i64> {
    type Error = crate::registry::ConstructionError;
    fn try_from(spec: MultipleChoiceBranchingCreateSpec) -> Result<Self, Self::Error> {
        let inferred = spec
            .arcs
            .iter()
            .flat_map(|&(u, v)| [u, v])
            .max()
            .map(|vertex| vertex.checked_add(1).ok_or("vertex count overflows usize"))
            .transpose()?
            .unwrap_or(0);
        let num_vertices = spec.num_vertices.unwrap_or(inferred);
        if num_vertices < inferred {
            return Err("num_vertices is too small for arc endpoints"
                .to_string()
                .into());
        }
        let graph = DirectedGraph::new(num_vertices, spec.arcs);
        let num_arcs = graph.num_arcs();
        if spec.weights.len() != num_arcs {
            return Err(format!(
                "weights has {} entries, expected {num_arcs}",
                spec.weights.len()
            )
            .into());
        }
        if let Some(message) = partition_validation_error(&spec.partition, num_arcs) {
            return Err(message.into());
        }
        Ok(Self::new(
            graph,
            spec.weights,
            spec.partition,
            spec.threshold,
        ))
    }
}

#[derive(Debug, Deserialize)]
struct MultipleChoiceBranchingUnchecked<W: WeightElement> {
    graph: DirectedGraph,
    weights: Vec<W>,
    partition: Vec<Vec<usize>>,
    threshold: W::Sum,
}

impl<'de, W> Deserialize<'de> for MultipleChoiceBranching<W>
where
    W: WeightElement + Deserialize<'de>,
    W::Sum: Deserialize<'de>,
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        let unchecked = MultipleChoiceBranchingUnchecked::<W>::deserialize(deserializer)?;
        let num_arcs = unchecked.graph.num_arcs();
        if unchecked.weights.len() != num_arcs {
            return Err(D::Error::custom(format!(
                "weights length must match graph num_arcs (expected {num_arcs}, got {})",
                unchecked.weights.len()
            )));
        }
        if let Some(message) = partition_validation_error(&unchecked.partition, num_arcs) {
            return Err(D::Error::custom(message));
        }

        Ok(Self {
            graph: unchecked.graph,
            weights: unchecked.weights,
            partition: unchecked.partition,
            threshold: unchecked.threshold,
        })
    }
}

impl<W: WeightElement> MultipleChoiceBranching<W> {
    /// Create a new Multiple Choice Branching instance.
    pub fn new(
        graph: DirectedGraph,
        weights: Vec<W>,
        partition: Vec<Vec<usize>>,
        threshold: W::Sum,
    ) -> Self {
        let num_arcs = graph.num_arcs();
        assert_eq!(
            weights.len(),
            num_arcs,
            "weights length must match graph num_arcs"
        );
        validate_partition(&partition, num_arcs);
        Self {
            graph,
            weights,
            partition,
            threshold,
        }
    }

    /// Get the underlying directed graph.
    pub fn graph(&self) -> &DirectedGraph {
        &self.graph
    }

    /// Get the arc weights.
    pub fn weights(&self) -> &[W] {
        &self.weights
    }

    /// Replace the arc weights.
    pub fn set_weights(&mut self, weights: Vec<W>) {
        assert_eq!(
            weights.len(),
            self.graph.num_arcs(),
            "weights length must match graph num_arcs"
        );
        self.weights = weights;
    }

    /// Check whether this problem uses a non-unit weight type.
    pub fn is_weighted(&self) -> bool {
        !W::IS_UNIT
    }

    /// Get the partition groups.
    pub fn partition(&self) -> &[Vec<usize>] {
        &self.partition
    }

    /// Get the threshold K.
    pub fn threshold(&self) -> &W::Sum {
        &self.threshold
    }

    /// Smallest h >= 1 bounding arc weights and the threshold in magnitude strictly by 2^h.
    pub fn max_weight_bits(&self) -> u64 {
        crate::types::max_numeric_magnitude_bits(
            self.weights
                .iter()
                .map(|weight| weight.to_sum())
                .chain(std::iter::once(self.threshold.clone())),
        )
    }

    /// Get the number of vertices.
    pub fn num_vertices(&self) -> usize {
        self.graph.num_vertices()
    }

    /// Get the number of arcs.
    pub fn num_arcs(&self) -> usize {
        self.graph.num_arcs()
    }

    /// Get the number of partition groups.
    pub fn num_partition_groups(&self) -> usize {
        self.partition.len()
    }

    /// Check whether a configuration is a satisfying solution.
    pub fn is_valid_solution(
        &self,
        config: &[bool],
    ) -> Result<bool, crate::traits::EvaluationError> {
        is_valid_multiple_choice_branching(
            &self.graph,
            &self.weights,
            &self.partition,
            &self.threshold,
            config,
        )
    }
}

impl<W> Problem for MultipleChoiceBranching<W>
where
    W: WeightElement + crate::variant::VariantParam,
{
    const NAME: &'static str = "MultipleChoiceBranching";
    type Solution = Vec<bool>;
    type Value = crate::types::Or;

    crate::problem_parameters![
        ("max_weight_bits", max_weight_bits),
        ("num_vertices", num_vertices),
        ("num_arcs", num_arcs),
        ("num_partition_groups", num_partition_groups),
    ];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![W]
    }

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
        if config.len() != self.graph.num_arcs() {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "arc-selection length does not match the graph".into(),
            ));
        }
        Ok({
            crate::types::Or({
                is_valid_multiple_choice_branching(
                    &self.graph,
                    &self.weights,
                    &self.partition,
                    &self.threshold,
                    config,
                )?
            })
        })
    }
}

impl<W> crate::solvers::BruteForceProblem for MultipleChoiceBranching<W>
where
    W: WeightElement + crate::variant::VariantParam,
{
    fn dimensions(&self) -> Vec<usize> {
        vec![2; self.graph.num_arcs()]
    }
}

fn validate_partition(partition: &[Vec<usize>], num_arcs: usize) {
    if let Some(message) = partition_validation_error(partition, num_arcs) {
        panic!("{message}");
    }
}

fn partition_validation_error(partition: &[Vec<usize>], num_arcs: usize) -> Option<String> {
    let mut seen = vec![false; num_arcs];
    for group in partition {
        for &arc_index in group {
            if arc_index >= num_arcs {
                return Some(format!(
                    "partition arc index {} out of range for {} arcs",
                    arc_index, num_arcs
                ));
            }
            if seen[arc_index] {
                return Some(format!(
                    "partition arc index {} appears more than once",
                    arc_index
                ));
            }
            seen[arc_index] = true;
        }
    }
    if seen.iter().all(|present| *present) {
        None
    } else {
        Some("partition must cover every arc exactly once".to_string())
    }
}

fn is_valid_multiple_choice_branching<W: WeightElement>(
    graph: &DirectedGraph,
    weights: &[W],
    partition: &[Vec<usize>],
    threshold: &W::Sum,
    config: &[bool],
) -> Result<bool, crate::traits::EvaluationError> {
    if config.len() != graph.num_arcs() {
        return Ok(false);
    }
    for group in partition {
        if group.iter().filter(|&&arc_index| config[arc_index]).count() > 1 {
            return Ok(false);
        }
    }

    let arcs = graph.arcs();
    let mut in_degree = vec![0usize; graph.num_vertices()];
    let mut selected_successors = vec![Vec::new(); graph.num_vertices()];
    let mut total = W::Sum::zero();
    for (index, &selected) in config.iter().enumerate() {
        if selected {
            let (source, target) = arcs[index];
            in_degree[target] += 1;
            if in_degree[target] > 1 {
                return Ok(false);
            }
            selected_successors[source].push(target);
            total = W::checked_add_to_sum(
                total,
                weights[index].to_sum(),
                "summing multiple-choice branching weights",
            )?;
        }
    }

    if total < *threshold {
        return Ok(false);
    }

    let mut queue: Vec<usize> = (0..graph.num_vertices())
        .filter(|&vertex| in_degree[vertex] == 0)
        .collect();
    let mut visited = 0usize;
    while let Some(source) = queue.pop() {
        visited += 1;
        for &target in &selected_successors[source] {
            in_degree[target] -= 1;
            if in_degree[target] == 0 {
                queue.push(target);
            }
        }
    }

    Ok(visited == graph.num_vertices())
}

crate::declare_variants! {
    default MultipleChoiceBranching<i64> => "2^num_arcs" create MultipleChoiceBranchingCreateSpec,
}

crate::register_brute_force! {
    MultipleChoiceBranching<i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "multiple_choice_branching",
        instance: Box::new(MultipleChoiceBranching::new(
            DirectedGraph::new(
                6,
                vec![
                    (0, 1),
                    (0, 2),
                    (1, 3),
                    (2, 3),
                    (1, 4),
                    (3, 5),
                    (4, 5),
                    (2, 4),
                ],
            ),
            vec![3, 2, 4, 1, 2, 3, 1, 3],
            vec![vec![0, 1], vec![2, 3], vec![4, 7], vec![5, 6]],
            10,
        )),
        optimal_config: serde_json::json!(vec![true, false, true, false, false, true, false, true]),
        optimal_value: serde_json::json!(true),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/graph/multiple_choice_branching.rs"]
mod tests;