From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from firstgate.proxmox.com (firstgate.proxmox.com [212.224.123.68]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by lists.proxmox.com (Postfix) with ESMTPS id D48318E186 for ; Thu, 10 Nov 2022 15:38:24 +0100 (CET) Received: from firstgate.proxmox.com (localhost [127.0.0.1]) by firstgate.proxmox.com (Proxmox) with ESMTP id 48ED0297A2 for ; Thu, 10 Nov 2022 15:38:24 +0100 (CET) Received: from proxmox-new.maurer-it.com (proxmox-new.maurer-it.com [94.136.29.106]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by firstgate.proxmox.com (Proxmox) with ESMTPS for ; Thu, 10 Nov 2022 15:38:08 +0100 (CET) Received: from proxmox-new.maurer-it.com (localhost.localdomain [127.0.0.1]) by proxmox-new.maurer-it.com (Proxmox) with ESMTP id E142044B43 for ; Thu, 10 Nov 2022 15:38:06 +0100 (CET) From: Fiona Ebner To: pve-devel@lists.proxmox.com Date: Thu, 10 Nov 2022 15:37:40 +0100 Message-Id: <20221110143800.98047-2-f.ebner@proxmox.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20221110143800.98047-1-f.ebner@proxmox.com> References: <20221110143800.98047-1-f.ebner@proxmox.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-SPAM-LEVEL: Spam detection results: 0 AWL -0.023 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% KAM_DMARC_STATUS 0.01 Test Rule for DKIM or SPF Failure with Strict Alignment PROLO_LEO1 0.1 Meta Catches all Leo drug variations so far SPF_HELO_NONE 0.001 SPF: HELO does not publish an SPF Record SPF_PASS -0.001 SPF: sender matches SPF record Subject: [pve-devel] [PATCH proxmox-resource-scheduling 1/3] initial commit X-BeenThere: pve-devel@lists.proxmox.com X-Mailman-Version: 2.1.29 Precedence: list List-Id: Proxmox VE development discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Nov 2022 14:38:24 -0000 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 --- .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 ", + "Proxmox Support Team ", +] +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(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([TopsisCriterion; N_CRITERIA]); + +/// A normalized matrix used for scoring with the TOPSIS algorithm. +pub struct TopsisMatrix(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 { + best: [f64; N_CRITERIA], + worst: [f64; N_CRITERIA], +} + +impl TopsisCriteria { + /// 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 { + 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 TopsisMatrix { + /// Values of the matrix for the fixed critierion with index `index`. + fn fixed_criterion(&self, index: usize) -> Vec { + self.0 + .iter() + .map(|alternative| alternative[index]) + .collect::>() + } + + /// 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::>() + } + + /// 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 { + 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( + matrix: &TopsisMatrix, + criteria: &TopsisCriteria, +) -> TopsisIdealAlternatives { + 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( + matrix: &TopsisMatrix, + criteria: &TopsisCriteria, +) -> Result, 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( + matrix: &TopsisMatrix, + criteria: &TopsisCriteria, +) -> Result, Error> { + let scores = score_alternatives(matrix, criteria)?; + + let mut enumerated = scores + .into_iter() + .enumerate() + .collect::>(); + 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