[pve-devel] [PATCH proxmox-resource-scheduling 1/3] initial commit

[Fiona Ebner <f.ebner@proxmox.com>]

Implement the TOPSIS[0] algorithm to score multi-valued alternatives
according to a given set of weighted criteria.

The number of alternatives cannot be known at compile time, but the
number of criteria should be (a given module using the topsis module
should have one (or more) fixed sets of criteria). Therefore, the
TopsisMatrix is implemented as a Vec of N_CRITERIA-sized arrays.

Compared to the description in [0] the weighing of the matrix
according to the weights of the criteria only happens during distance
calculation to the idealized alternatives. It turned out more natural
like that, because the matrix doesn't need to be mutable.

[0]: https://en.wikipedia.org/wiki/TOPSIS

Signed-off-by: Fiona Ebner <f.ebner@proxmox.com>
---
 .cargo/config   |   5 +
 .gitignore      |   2 +
 Cargo.toml      |  20 ++++
 rustfmt.toml    |   1 +
 src/lib.rs      |   1 +
 src/topsis.rs   | 216 +++++++++++++++++++++++++++++++++++
 tests/topsis.rs | 293 ++++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 538 insertions(+)
 create mode 100644 .cargo/config
 create mode 100644 .gitignore
 create mode 100644 Cargo.toml
 create mode 100644 rustfmt.toml
 create mode 100644 src/lib.rs
 create mode 100644 src/topsis.rs
 create mode 100644 tests/topsis.rs

diff --git a/.cargo/config b/.cargo/config
new file mode 100644
index 0000000..3b5b6e4
--- /dev/null
+++ b/.cargo/config
@@ -0,0 +1,5 @@
+[source]
+[source.debian-packages]
+directory = "/usr/share/cargo/registry"
+[source.crates-io]
+replace-with = "debian-packages"
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..1e7caa9
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+Cargo.lock
+target/
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..ec8e12f
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,20 @@
+[package]
+name = "proxmox-resource-scheduling"
+version = "0.1.0"
+authors = [
+    "Fiona Ebner <f.ebner@proxmox.com>",
+    "Proxmox Support Team <support@proxmox.com>",
+]
+edition = "2021"
+license = "AGPL-3"
+description = "Proxmox library for resource scheduling"
+homepage = "https://www.proxmox.com"
+
+exclude = [ "debian" ]
+
+[lib]
+name = "proxmox_resource_scheduling"
+path = "src/lib.rs"
+
+[dependencies]
+anyhow = "1.0"
diff --git a/rustfmt.toml b/rustfmt.toml
new file mode 100644
index 0000000..3a26366
--- /dev/null
+++ b/rustfmt.toml
@@ -0,0 +1 @@
+edition = "2021"
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..dda0563
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1 @@
+pub mod topsis;
diff --git a/src/topsis.rs b/src/topsis.rs
new file mode 100644
index 0000000..f932bcd
--- /dev/null
+++ b/src/topsis.rs
@@ -0,0 +1,216 @@
+use anyhow::{bail, Error};
+
+fn differences<const N: usize>(xs: &[f64; N], ys: &[f64; N]) -> [f64; N] {
+    let mut differences = [0.0; N];
+    for n in 0..N {
+        differences[n] = xs[n] - ys[n];
+    }
+    differences
+}
+
+/// Calculate the L^2-norm of the given values.
+fn l2_norm(values: &[f64]) -> f64 {
+    values
+        .iter()
+        .fold(0.0, |sum_of_squares, value| sum_of_squares + value * value)
+        .sqrt()
+}
+
+/// A criterion that can be used when scoring with the TOPSIS algorithm.
+pub struct TopsisCriterion {
+    /// Name of the criterion.
+    name: String,
+    /// The relative weight of the criterion. Is non-negative.
+    weight: f64,
+    /// Whether it's good to maximize or minimize the criterion.
+    maximize: bool,
+}
+
+impl TopsisCriterion {
+    /// Construct a new `TopsisCriterion`. Use a negative weight if the value for the criterion
+    /// should be minimized rather than maximized.
+    ///
+    /// Assumes that `weight` is finite.
+    pub fn new(name: String, weight: f64) -> Self {
+        let (maximize, weight) = if weight >= 0.0 {
+            (true, weight)
+        } else {
+            (false, -weight)
+        };
+
+        TopsisCriterion {
+            name,
+            weight,
+            maximize,
+        }
+    }
+}
+
+/// A normalized array of `TopsisCriterion`.
+pub struct TopsisCriteria<const N_CRITERIA: usize>([TopsisCriterion; N_CRITERIA]);
+
+/// A normalized matrix used for scoring with the TOPSIS algorithm.
+pub struct TopsisMatrix<const N_CRITERIA: usize>(Vec<[f64; N_CRITERIA]>);
+
+/// Idealized alternatives from a `TopsisMatrix`. That is, the alternative consisting of the best
+/// (respectively worst) value among the alternatives in the matrix for each single criterion.
+struct TopsisIdealAlternatives<const N_CRITERIA: usize> {
+    best: [f64; N_CRITERIA],
+    worst: [f64; N_CRITERIA],
+}
+
+impl<const N: usize> TopsisCriteria<N> {
+    /// Create a new instance of normalized TOPSIS criteria.
+    ///
+    /// Assumes that the sum of weights can be calculated to a finite, non-zero value.
+    pub fn new(mut criteria: [TopsisCriterion; N]) -> Result<Self, Error> {
+        let divisor = criteria
+            .iter()
+            .fold(0.0, |sum, criterion| sum + criterion.weight);
+
+        if divisor == 0.0 {
+            bail!("no criterion has a non-zero weight");
+        }
+
+        for criterion in criteria.iter_mut() {
+            criterion.weight /= divisor;
+            if criterion.weight > 1.0 || criterion.weight < 0.0 || !criterion.weight.is_finite() {
+                bail!(
+                    "criterion '{}' got invalid weight {}",
+                    criterion.name,
+                    criterion.weight
+                );
+            }
+        }
+
+        Ok(TopsisCriteria(criteria))
+    }
+
+    /// Weigh each value according to the weight of its corresponding criterion.
+    pub fn weigh<'a>(&self, values: &'a mut [f64; N]) -> &'a [f64; N] {
+        for (n, value) in values.iter_mut().enumerate() {
+            *value *= self.0[n].weight
+        }
+        values
+    }
+}
+
+impl<const N: usize> TopsisMatrix<N> {
+    /// Values of the matrix for the fixed critierion with index `index`.
+    fn fixed_criterion(&self, index: usize) -> Vec<f64> {
+        self.0
+            .iter()
+            .map(|alternative| alternative[index])
+            .collect::<Vec<_>>()
+    }
+
+    /// Mutable values of the matrix for the fixed critierion with index `index`.
+    fn fixed_criterion_mut(&mut self, index: usize) -> Vec<&mut f64> {
+        self.0
+            .iter_mut()
+            .map(|alternative| &mut alternative[index])
+            .collect::<Vec<&mut _>>()
+    }
+
+    /// Create a normalized `TopsisMatrix` based on the given values.
+    ///
+    /// Assumes that the sum of squares for each fixed criterion in `matrix` can be calculated to a
+    /// finite value.
+    pub fn new(matrix: Vec<[f64; N]>) -> Result<Self, Error> {
+        let mut matrix = TopsisMatrix(matrix);
+        for n in 0..N {
+            let divisor = l2_norm(&matrix.fixed_criterion(n));
+
+            // If every alternative has zero value for the given criterion, keep it like that.
+            if divisor != 0.0 {
+                for value in matrix.fixed_criterion_mut(n).into_iter() {
+                    *value /= divisor;
+                    if !value.is_finite() {
+                        bail!("criterion {} got invalid value {}", n, value);
+                    }
+                }
+            }
+        }
+
+        Ok(matrix)
+    }
+}
+
+/// Compute the idealized alternatives from the given `matrix`. The `criteria` are required to know
+/// if a critierion should be maximized or minimized.
+fn ideal_alternatives<const N: usize>(
+    matrix: &TopsisMatrix<N>,
+    criteria: &TopsisCriteria<N>,
+) -> TopsisIdealAlternatives<N> {
+    let criteria = &criteria.0;
+
+    let mut best = [0.0; N];
+    let mut worst = [0.0; N];
+
+    for n in 0..N {
+        let fixed_criterion = matrix.fixed_criterion(n);
+        let min = fixed_criterion
+            .iter()
+            .min_by(|a, b| a.total_cmp(b))
+            .unwrap();
+        let max = fixed_criterion
+            .iter()
+            .max_by(|a, b| a.total_cmp(b))
+            .unwrap();
+
+        (best[n], worst[n]) = match criteria[n].maximize {
+            true => (*max, *min),
+            false => (*min, *max),
+        }
+    }
+
+    TopsisIdealAlternatives { best, worst }
+}
+
+/// Scores the alternatives in `matrix` according to their similarity to the ideal worst
+/// alternative. Scores range from 0.0 to 1.0 and a low score indicates closness to the ideal worst
+/// and/or distance to the ideal best alternatives.
+pub fn score_alternatives<const N: usize>(
+    matrix: &TopsisMatrix<N>,
+    criteria: &TopsisCriteria<N>,
+) -> Result<Vec<f64>, Error> {
+    let ideal_alternatives = ideal_alternatives(matrix, criteria);
+    let ideal_best = &ideal_alternatives.best;
+    let ideal_worst = &ideal_alternatives.worst;
+
+    let mut scores = vec![];
+
+    for alternative in matrix.0.iter() {
+        let distance_to_best = l2_norm(criteria.weigh(&mut differences(alternative, ideal_best)));
+        let distance_to_worst = l2_norm(criteria.weigh(&mut differences(alternative, ideal_worst)));
+
+        let divisor = distance_to_worst + distance_to_best;
+        if divisor == 0.0 {
+            // Can happen if all alternatives are the same.
+            scores.push(0.0);
+        } else {
+            scores.push(distance_to_worst / divisor);
+        }
+    }
+
+    if let Some(score) = scores.iter().find(|score| !score.is_finite()) {
+        bail!("invalid score {}", score);
+    }
+
+    Ok(scores)
+}
+
+/// Similar to `score_alternatives`, but returns the list of indices decreasing by score.
+pub fn rank_alternatives<const N: usize>(
+    matrix: &TopsisMatrix<N>,
+    criteria: &TopsisCriteria<N>,
+) -> Result<Vec<usize>, Error> {
+    let scores = score_alternatives(matrix, criteria)?;
+
+    let mut enumerated = scores
+        .into_iter()
+        .enumerate()
+        .collect::<Vec<(usize, f64)>>();
+    enumerated.sort_by(|(_, a), (_, b)| b.total_cmp(a));
+    Ok(enumerated.into_iter().map(|(n, _)| n).collect())
+}
diff --git a/tests/topsis.rs b/tests/topsis.rs
new file mode 100644
index 0000000..bfb8624
--- /dev/null
+++ b/tests/topsis.rs
@@ -0,0 +1,293 @@
+use anyhow::Error;
+
+use proxmox_resource_scheduling::topsis::{
+    rank_alternatives, TopsisCriteria, TopsisCriterion, TopsisMatrix,
+};
+
+#[test]
+fn test_topsis_single_criterion() -> Result<(), Error> {
+    let criteria_pos =
+        TopsisCriteria::new([TopsisCriterion::new("the one and only".to_string(), 1.0)])?;
+
+    let criteria_neg =
+        TopsisCriteria::new([TopsisCriterion::new("the one and only".to_string(), -1.0)])?;
+
+    let matrix = vec![[0.0]];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_pos)?,
+        vec![0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_neg)?,
+        vec![0],
+    );
+
+    let matrix = vec![[0.0], [2.0]];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_pos)?,
+        vec![1, 0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_neg)?,
+        vec![0, 1],
+    );
+
+    let matrix = vec![[1.0], [2.0]];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_pos)?,
+        vec![1, 0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_neg)?,
+        vec![0, 1],
+    );
+
+    let matrix = vec![[1.0], [2.0], [5.0], [3.0], [4.0]];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_pos)?,
+        vec![2, 4, 3, 1, 0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_neg)?,
+        vec![0, 1, 3, 4, 2],
+    );
+
+    let matrix = vec![[-2.0], [-5.0], [-4.0], [1.0], [-3.0]];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_pos)?,
+        vec![3, 0, 4, 2, 1],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_neg)?,
+        vec![1, 2, 4, 0, 3],
+    );
+
+    Ok(())
+}
+
+#[test]
+fn test_topsis_two_criteria() -> Result<(), Error> {
+    let criteria_max_min = TopsisCriteria::new([
+        TopsisCriterion::new("max".to_string(), 1.0),
+        TopsisCriterion::new("min".to_string(), -1.0),
+    ])?;
+    let criteria_min_max = TopsisCriteria::new([
+        TopsisCriterion::new("min".to_string(), -1.0),
+        TopsisCriterion::new("max".to_string(), 1.0),
+    ])?;
+    let criteria_min_min = TopsisCriteria::new([
+        TopsisCriterion::new("min1".to_string(), -1.0),
+        TopsisCriterion::new("min2".to_string(), -1.0),
+    ])?;
+    let criteria_max_max = TopsisCriteria::new([
+        TopsisCriterion::new("max1".to_string(), 1.0),
+        TopsisCriterion::new("max2".to_string(), 1.0),
+    ])?;
+
+    let matrix = vec![[0.0, 0.0]];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_max_min)?,
+        vec![0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_min_max)?,
+        vec![0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_min_min)?,
+        vec![0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_max_max)?,
+        vec![0],
+    );
+
+    #[rustfmt::skip]
+    let matrix = vec![
+        [0.0, 1.0],
+        [1.0, 0.0],
+        [1.0, -1.0],
+        [1.0, 1.0],
+        [0.0, 0.0],
+    ];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_max_min)?,
+        vec![2, 1, 4, 3, 0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_min_max)?,
+        vec![0, 3, 4, 1, 2],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_min_min)?,
+        vec![2, 4, 1, 0, 3],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_max_max)?,
+        vec![3, 0, 1, 4, 2],
+    );
+
+    // This one was cross-checked with https://decision-radar.com/topsis rather than manually.
+    #[rustfmt::skip]
+    let matrix = vec![
+        [7.0, 4.0],
+        [1.0, 0.5],
+        [-1.0, -1.0],
+        [-8.5, 11.5],
+        [4.0, 7.0],
+    ];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_max_min)?,
+        vec![0, 1, 4, 2, 3],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_min_max)?,
+        vec![3, 2, 4, 1, 0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_min_min)?,
+        vec![2, 3, 1, 0, 4],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_max_max)?,
+        vec![4, 0, 1, 3, 2],
+    );
+
+    Ok(())
+}
+
+#[test]
+fn test_topsis_three_criteria() -> Result<(), Error> {
+    let criteria_first = TopsisCriteria::new([
+        TopsisCriterion::new("more".to_string(), 10.0),
+        TopsisCriterion::new("less".to_string(), 0.2),
+        TopsisCriterion::new("least".to_string(), 0.1),
+    ])?;
+    let criteria_second = TopsisCriteria::new([
+        TopsisCriterion::new("less".to_string(), 0.2),
+        TopsisCriterion::new("more".to_string(), 10.0),
+        TopsisCriterion::new("least".to_string(), 0.1),
+    ])?;
+    let criteria_third = TopsisCriteria::new([
+        TopsisCriterion::new("less".to_string(), 0.2),
+        TopsisCriterion::new("least".to_string(), 0.1),
+        TopsisCriterion::new("more".to_string(), 10.0),
+    ])?;
+    let criteria_min = TopsisCriteria::new([
+        TopsisCriterion::new("most".to_string(), -10.0),
+        TopsisCriterion::new("more".to_string(), -5.0),
+        TopsisCriterion::new("less".to_string(), 0.1),
+    ])?;
+
+    #[rustfmt::skip]
+    let matrix = vec![
+        [1.0, 0.0, 0.0],
+        [0.0, 1.0, 0.0],
+        [0.0, 0.0, 1.0],
+    ];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_first)?,
+        vec![0, 1, 2],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_second)?,
+        vec![1, 0, 2],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_third)?,
+        vec![2, 0, 1],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_min)?,
+        vec![2, 1, 0],
+    );
+
+    #[rustfmt::skip]
+    let matrix = vec![
+        [1.0, 0.0, 0.0],
+        [0.0, 1.0, 0.0],
+        [0.0, 0.0, 1000.0],
+    ];
+    // normalization ensures that it's still the same as above
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_first)?,
+        vec![0, 1, 2],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_second)?,
+        vec![1, 0, 2],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_third)?,
+        vec![2, 0, 1],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_min)?,
+        vec![2, 1, 0],
+    );
+
+    #[rustfmt::skip]
+    let matrix = vec![
+        [-1.0, 0.0, 0.0],
+        [0.0, -1.0, 0.0],
+        [0.0, 0.0, 1.0],
+    ];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_first)?,
+        vec![2, 1, 0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_second)?,
+        vec![2, 0, 1],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix.clone())?, &criteria_third)?,
+        vec![2, 1, 0],
+    );
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_min)?,
+        vec![0, 1, 2],
+    );
+
+    Ok(())
+}
+
+#[test]
+fn test_nan() {
+    #[rustfmt::skip]
+    let matrix = vec![
+        [-1.0, 0.0, 0.0],
+        [0.0, -1.0, 0.0],
+        [0.0, f64::NAN, 1.0],
+    ];
+    assert!(TopsisMatrix::new(matrix).is_err());
+}
+
+#[test]
+fn test_zero() -> Result<(), Error> {
+    let criteria_zero = TopsisCriteria::new([
+        TopsisCriterion::new("z".to_string(), 0.0),
+        TopsisCriterion::new("e".to_string(), 0.0),
+        TopsisCriterion::new("ro".to_string(), 0.0),
+    ]);
+    assert!(criteria_zero.is_err());
+
+    let criteria_first = TopsisCriteria::new([
+        TopsisCriterion::new("more".to_string(), 10.0),
+        TopsisCriterion::new("less".to_string(), 0.2),
+        TopsisCriterion::new("least".to_string(), 0.1),
+    ])?;
+
+    #[rustfmt::skip]
+    let matrix = vec![
+        [0.0, 0.0, 0.0],
+        [0.0, 1.0, 0.0],
+        [0.0, 0.0, 1.0],
+    ];
+    assert_eq!(
+        rank_alternatives(&TopsisMatrix::new(matrix)?, &criteria_first)?,
+        vec![1, 2, 0],
+    );
+
+    Ok(())
+}
-- 
2.30.2