problemreductions/models/misc/

timetable_design.rs

//! Timetable Design problem implementation.
//!
//! Decide whether craftsmen can be assigned to tasks across work periods while
//! respecting availability, per-period exclusivity, and exact pairwise work
//! requirements.

use crate::registry::{CreateSpec, ProblemSchemaEntry};
use crate::traits::Problem;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "TimetableDesign",
        display_name: "Timetable Design",
        aliases: &[],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Misc,
        module_path: module_path!(),
        description: "Assign craftsmen to tasks over work periods subject to availability and exact pairwise requirements",
        fields: TimetableDesignCreateSpec::FIELDS,
    }
}

/// The Timetable Design problem.
///
/// A configuration is a flattened binary tensor `f(c,t,h)` in craftsman-major,
/// task-next, period-last order:
/// `idx = ((c * num_tasks) + t) * num_periods + h`.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct TimetableDesign {
    num_periods: usize,
    num_craftsmen: usize,
    num_tasks: usize,
    craftsman_avail: Vec<Vec<bool>>,
    task_avail: Vec<Vec<bool>>,
    requirements: Vec<Vec<i64>>,
}

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct TimetableDesignCreateSpec {
    /// Number of work periods.
    num_periods: usize,
    /// Number of craftsmen.
    num_craftsmen: usize,
    /// Number of tasks.
    num_tasks: usize,
    /// Craftsman availability matrix.
    craftsman_avail: Vec<Vec<bool>>,
    /// Task availability matrix.
    task_avail: Vec<Vec<bool>>,
    /// Required work periods for each craftsman-task pair.
    requirements: Vec<Vec<i64>>,
}
impl TryFrom<TimetableDesignCreateSpec> for TimetableDesign {
    type Error = crate::registry::ConstructionError;
    fn try_from(spec: TimetableDesignCreateSpec) -> Result<Self, Self::Error> {
        if spec.craftsman_avail.len() != spec.num_craftsmen {
            return Err(format!(
                "craftsman_avail has {} rows, expected {}",
                spec.craftsman_avail.len(),
                spec.num_craftsmen
            )
            .into());
        }
        if let Some((index, row)) = spec
            .craftsman_avail
            .iter()
            .enumerate()
            .find(|(_, row)| row.len() != spec.num_periods)
        {
            return Err(format!(
                "craftsman_avail row {index} has {} periods, expected {}",
                row.len(),
                spec.num_periods
            )
            .into());
        }
        if spec.task_avail.len() != spec.num_tasks {
            return Err(format!(
                "task_avail has {} rows, expected {}",
                spec.task_avail.len(),
                spec.num_tasks
            )
            .into());
        }
        if let Some((index, row)) = spec
            .task_avail
            .iter()
            .enumerate()
            .find(|(_, row)| row.len() != spec.num_periods)
        {
            return Err(format!(
                "task_avail row {index} has {} periods, expected {}",
                row.len(),
                spec.num_periods
            )
            .into());
        }
        if spec.requirements.len() != spec.num_craftsmen {
            return Err(format!(
                "requirements has {} rows, expected {}",
                spec.requirements.len(),
                spec.num_craftsmen
            )
            .into());
        }
        if let Some((index, row)) = spec
            .requirements
            .iter()
            .enumerate()
            .find(|(_, row)| row.len() != spec.num_tasks)
        {
            return Err(format!(
                "requirements row {index} has {} tasks, expected {}",
                row.len(),
                spec.num_tasks
            )
            .into());
        }
        Ok(Self::new(
            spec.num_periods,
            spec.num_craftsmen,
            spec.num_tasks,
            spec.craftsman_avail,
            spec.task_avail,
            spec.requirements,
        ))
    }
}

impl TimetableDesign {
    /// Create a new Timetable Design instance.
    ///
    /// # Panics
    ///
    /// Panics if any matrix dimensions do not match the declared counts.
    pub fn new(
        num_periods: usize,
        num_craftsmen: usize,
        num_tasks: usize,
        craftsman_avail: Vec<Vec<bool>>,
        task_avail: Vec<Vec<bool>>,
        requirements: Vec<Vec<i64>>,
    ) -> Self {
        assert_eq!(
            craftsman_avail.len(),
            num_craftsmen,
            "craftsman_avail has {} rows, expected {}",
            craftsman_avail.len(),
            num_craftsmen
        );
        for (craftsman, row) in craftsman_avail.iter().enumerate() {
            assert_eq!(
                row.len(),
                num_periods,
                "craftsman {} availability has {} periods, expected {}",
                craftsman,
                row.len(),
                num_periods
            );
        }

        assert_eq!(
            task_avail.len(),
            num_tasks,
            "task_avail has {} rows, expected {}",
            task_avail.len(),
            num_tasks
        );
        for (task, row) in task_avail.iter().enumerate() {
            assert_eq!(
                row.len(),
                num_periods,
                "task {} availability has {} periods, expected {}",
                task,
                row.len(),
                num_periods
            );
        }

        assert_eq!(
            requirements.len(),
            num_craftsmen,
            "requirements has {} rows, expected {}",
            requirements.len(),
            num_craftsmen
        );
        for (craftsman, row) in requirements.iter().enumerate() {
            assert_eq!(
                row.len(),
                num_tasks,
                "requirements row {} has {} tasks, expected {}",
                craftsman,
                row.len(),
                num_tasks
            );
        }

        Self {
            num_periods,
            num_craftsmen,
            num_tasks,
            craftsman_avail,
            task_avail,
            requirements,
        }
    }

    /// Get the number of periods.
    pub fn num_periods(&self) -> usize {
        self.num_periods
    }

    /// Get the number of craftsmen.
    pub fn num_craftsmen(&self) -> usize {
        self.num_craftsmen
    }

    /// Get the number of tasks.
    pub fn num_tasks(&self) -> usize {
        self.num_tasks
    }

    /// Get craftsman availability.
    pub fn craftsman_avail(&self) -> &[Vec<bool>] {
        &self.craftsman_avail
    }

    /// Get task availability.
    pub fn task_avail(&self) -> &[Vec<bool>] {
        &self.task_avail
    }

    /// Get the pairwise work requirements.
    pub fn requirements(&self) -> &[Vec<i64>] {
        &self.requirements
    }

    fn config_len(&self) -> usize {
        self.num_craftsmen * self.num_tasks * self.num_periods
    }

    fn index(&self, craftsman: usize, task: usize, period: usize) -> usize {
        ((craftsman * self.num_tasks) + task) * self.num_periods + period
    }

    pub(crate) fn solve_via_required_assignments(&self) -> Option<Vec<Vec<Vec<bool>>>> {
        #[derive(Clone)]
        struct PairRequirement {
            craftsman: usize,
            task: usize,
            required: usize,
            allowed_periods: Vec<usize>,
        }

        let mut craftsman_demand = vec![0usize; self.num_craftsmen];
        let mut task_demand = vec![0usize; self.num_tasks];
        let mut pairs = Vec::new();

        for (craftsman, requirement_row) in self.requirements.iter().enumerate() {
            for (task, required_i64) in requirement_row.iter().enumerate() {
                let required = usize::try_from(*required_i64).ok()?;
                craftsman_demand[craftsman] += required;
                task_demand[task] += required;

                if required == 0 {
                    continue;
                }

                let allowed_periods = (0..self.num_periods)
                    .filter(|&period| {
                        self.craftsman_avail[craftsman][period] && self.task_avail[task][period]
                    })
                    .collect::<Vec<_>>();

                if allowed_periods.len() < required {
                    return None;
                }

                pairs.push(PairRequirement {
                    craftsman,
                    task,
                    required,
                    allowed_periods,
                });
            }
        }

        if craftsman_demand
            .iter()
            .zip(&self.craftsman_avail)
            .any(|(demand, avail)| *demand > avail.iter().filter(|&&v| v).count())
        {
            return None;
        }

        if task_demand
            .iter()
            .zip(&self.task_avail)
            .any(|(demand, avail)| *demand > avail.iter().filter(|&&v| v).count())
        {
            return None;
        }

        pairs.sort_by_key(|pair| (pair.allowed_periods.len(), pair.required));

        struct SearchState<'a> {
            problem: &'a TimetableDesign,
            pairs: &'a [PairRequirement],
            craftsman_busy: Vec<Vec<bool>>,
            task_busy: Vec<Vec<bool>>,
            config: Vec<usize>,
        }

        impl SearchState<'_> {
            fn search_pair(
                &mut self,
                pair_index: usize,
                period_offset: usize,
                remaining: usize,
            ) -> bool {
                if pair_index == self.pairs.len() {
                    return true;
                }

                let pair = &self.pairs[pair_index];
                if remaining == 0 {
                    return self.search_pair(
                        pair_index + 1,
                        0,
                        self.pairs
                            .get(pair_index + 1)
                            .map_or(0, |next| next.required),
                    );
                }

                let feasible_remaining = pair.allowed_periods[period_offset..]
                    .iter()
                    .filter(|&&period| {
                        !self.craftsman_busy[pair.craftsman][period]
                            && !self.task_busy[pair.task][period]
                    })
                    .count();
                if feasible_remaining < remaining {
                    return false;
                }

                for candidate_index in period_offset..pair.allowed_periods.len() {
                    let period = pair.allowed_periods[candidate_index];
                    if self.craftsman_busy[pair.craftsman][period]
                        || self.task_busy[pair.task][period]
                    {
                        continue;
                    }

                    self.craftsman_busy[pair.craftsman][period] = true;
                    self.task_busy[pair.task][period] = true;
                    self.config[self.problem.index(pair.craftsman, pair.task, period)] = 1;

                    if self.search_pair(pair_index, candidate_index + 1, remaining - 1) {
                        return true;
                    }

                    self.config[self.problem.index(pair.craftsman, pair.task, period)] = 0;
                    self.task_busy[pair.task][period] = false;
                    self.craftsman_busy[pair.craftsman][period] = false;
                }

                false
            }
        }

        let mut state = SearchState {
            problem: self,
            pairs: &pairs,
            craftsman_busy: vec![vec![false; self.num_periods]; self.num_craftsmen],
            task_busy: vec![vec![false; self.num_periods]; self.num_tasks],
            config: vec![0; self.config_len()],
        };

        if state.search_pair(0, 0, pairs.first().map_or(0, |pair| pair.required)) {
            Some(
                (0..self.num_craftsmen)
                    .map(|craftsman| {
                        (0..self.num_tasks)
                            .map(|task| {
                                (0..self.num_periods)
                                    .map(|period| {
                                        state.config[self.index(craftsman, task, period)] == 1
                                    })
                                    .collect()
                            })
                            .collect()
                    })
                    .collect(),
            )
        } else {
            None
        }
    }
}

impl Problem for TimetableDesign {
    const NAME: &'static str = "TimetableDesign";
    type Solution = Vec<Vec<Vec<bool>>>;
    type Value = crate::types::Or;

    crate::problem_parameters![
        ("num_craftsmen", num_craftsmen),
        ("num_periods", num_periods),
        ("num_tasks", num_tasks),
    ];

    fn evaluate(
        &self,
        solution: &Self::Solution,
    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
        if solution.len() != self.num_craftsmen
            || solution.iter().any(|craftsman| {
                craftsman.len() != self.num_tasks
                    || craftsman.iter().any(|task| task.len() != self.num_periods)
            })
        {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "timetable dimensions do not match the instance".into(),
            ));
        }
        let config = solution
            .iter()
            .flatten()
            .flatten()
            .copied()
            .collect::<Vec<_>>();
        Ok({
            crate::types::Or({
                if config.len() != self.config_len() {
                    return Ok(crate::types::Or(false));
                }
                let mut craftsman_busy = vec![vec![false; self.num_periods]; self.num_craftsmen];
                let mut task_busy = vec![vec![false; self.num_periods]; self.num_tasks];
                let mut pair_counts = vec![vec![0i64; self.num_tasks]; self.num_craftsmen];

                for craftsman in 0..self.num_craftsmen {
                    for task in 0..self.num_tasks {
                        for period in 0..self.num_periods {
                            if !config[self.index(craftsman, task, period)] {
                                continue;
                            }

                            if !self.craftsman_avail[craftsman][period]
                                || !self.task_avail[task][period]
                            {
                                return Ok(crate::types::Or(false));
                            }

                            if craftsman_busy[craftsman][period] || task_busy[task][period] {
                                return Ok(crate::types::Or(false));
                            }

                            craftsman_busy[craftsman][period] = true;
                            task_busy[task][period] = true;
                            pair_counts[craftsman][task] += 1;
                        }
                    }
                }

                pair_counts == self.requirements
            })
        })
    }

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

impl crate::solvers::BruteForceProblem for TimetableDesign {
    fn dimensions(&self) -> Vec<usize> {
        vec![2; self.config_len()]
    }
}

crate::declare_variants! {
    default TimetableDesign => "2^(num_craftsmen * num_tasks * num_periods)" create TimetableDesignCreateSpec,
}

crate::register_brute_force! {
    TimetableDesign decode |problem: &TimetableDesign, indices: Vec<usize>| (0..problem.num_craftsmen()).map(|craftsman| (0..problem.num_tasks()).map(|task| (0..problem.num_periods()).map(|period| indices[problem.index(craftsman, task, period)] != 0).collect()).collect()).collect(),
}

#[cfg(any(test, feature = "example-db"))]
const ISSUE_EXAMPLE_ASSIGNMENTS: &[(usize, usize, usize)] = &[
    (0, 0, 0),
    (1, 4, 0),
    (1, 1, 1),
    (2, 3, 1),
    (0, 2, 2),
    (3, 4, 2),
    (4, 1, 2),
];

#[cfg(any(test, feature = "example-db"))]
fn issue_example_problem() -> TimetableDesign {
    TimetableDesign::new(
        3,
        5,
        5,
        vec![
            vec![true, true, true],
            vec![true, true, false],
            vec![false, true, true],
            vec![true, false, true],
            vec![true, true, true],
        ],
        vec![
            vec![true, true, false],
            vec![false, true, true],
            vec![true, false, true],
            vec![true, true, true],
            vec![true, true, true],
        ],
        vec![
            vec![1, 0, 1, 0, 0],
            vec![0, 1, 0, 0, 1],
            vec![0, 0, 0, 1, 0],
            vec![0, 0, 0, 0, 1],
            vec![0, 1, 0, 0, 0],
        ],
    )
}

#[cfg(any(test, feature = "example-db"))]
fn issue_example_config() -> Vec<Vec<Vec<bool>>> {
    let problem = issue_example_problem();
    let mut config = vec![
        vec![vec![false; problem.num_periods()]; problem.num_tasks()];
        problem.num_craftsmen()
    ];
    for &(craftsman, task, period) in ISSUE_EXAMPLE_ASSIGNMENTS {
        config[craftsman][task][period] = true;
    }
    config
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "timetable_design",
        instance: Box::new(issue_example_problem()),
        optimal_config: serde_json::json!(issue_example_config()),
        optimal_value: serde_json::json!(true),
    }]
}

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