Pareto frontier and skyline query primitives for multi-objective optimization. Filters sets of items to find non-dominated candidates across multiple metrics.
[dependencies]
pare = "0.2.0"use pare::ParetoFrontier;
// [Relevance, Recency] -- higher is better
let candidates = vec![
vec![0.9, 0.1], // A
vec![0.5, 0.5], // B
vec![0.1, 0.9], // C
vec![0.4, 0.4], // D (dominated by B)
];
let frontier = ParetoFrontier::try_new(&candidates).unwrap();
assert_eq!(frontier.indices(), vec![0, 1, 2]); // D excludedWhen some objectives should be minimized, construct with explicit directions:
use pare::{Direction, ParetoFrontier};
// accuracy (maximize) vs latency_ms (minimize)
let mut f = ParetoFrontier::new(vec![Direction::Maximize, Direction::Minimize]);
f.push(vec![0.92, 120.0], "model_a");
f.push(vec![0.90, 80.0], "model_b");
f.push(vec![0.88, 150.0], "model_c"); // dominated by model_b
assert_eq!(f.len(), 2); // model_c filtered outPick a point with weighted scoring, ASF (Achievement Scalarizing Function), knee detection, or analyze spread with crowding distance:
use pare::{Direction, ParetoFrontier};
let mut f = ParetoFrontier::new(vec![Direction::Maximize, Direction::Maximize]);
f.push(vec![0.9, 0.1], "A");
f.push(vec![0.5, 0.5], "B");
f.push(vec![0.1, 0.9], "C");
// ASF -- works on non-convex fronts, finds the best compromise point
let ideal = f.ideal_point().unwrap();
let best_asf = f.best_asf(&[1.0, 1.0], &ideal).unwrap();
// Knee point -- highest tradeoff point on the frontier
let knee = f.knee_index().unwrap();
// Weighted linear score -- simple but misses non-convex regions
let best = f.best_index(&[0.7, 0.3]).unwrap();
// Full ranking by score (descending)
let ranked = f.ranked_indices(&[0.5, 0.5]);
// Crowding distance -- points in sparse regions score higher
let distances = f.crowding_distances();
// Hypervolume -- area dominated by the frontier (quality indicator)
let ref_pt = f.suggest_ref_point(0.1).unwrap();
let hv = f.hypervolume(&ref_pt);
// Per-point hypervolume contribution (for indicator-based selection)
let contribs = f.hypervolume_contributions(&ref_pt);Objectives often have different units (accuracy 0-1, latency 10-500ms, cost $0-$10000). pare handles this:
use pare::{Direction, ParetoFrontier};
let mut f = ParetoFrontier::new(vec![Direction::Maximize, Direction::Minimize]);
f.push(vec![0.92, 120.0], "model_a");
f.push(vec![0.88, 80.0], "model_b");
// Unit-free normalized values: 0 = worst on front, 1 = best on front
let norm = f.normalized_values(0).unwrap();
// norm[0] = 1.0 (best accuracy), norm[1] = 0.0 (worst latency)
// Ideal (best per-objective) and nadir (worst per-objective)
let ideal = f.ideal_point().unwrap(); // [0.92, 80.0]
let nadir = f.nadir_point().unwrap(); // [0.88, 120.0]
// For stable scoring across frontier changes, use static bounds:
let bounds = vec![(0.0, 1.0), (0.0, 500.0)];
let score = f.scalar_score_static(0, &[1.0, 1.0], &bounds);Apply constraints after frontier construction:
use pare::{Direction, ParetoFrontier};
let mut f = ParetoFrontier::new(vec![Direction::Maximize, Direction::Minimize]);
f.push(vec![0.95, 200.0], "expensive");
f.push(vec![0.90, 50.0], "moderate");
f.push(vec![0.80, 10.0], "cheap");
// Keep only points within budget
f.retain(|p| p.values[1] < 100.0);
assert_eq!(f.len(), 2);For simple cases where you just need non-dominated indices from Vec<f32> points:
use pare::{pareto_indices, pareto_indices_2d, pareto_indices_k_dominance, pareto_layers};
let points = vec![vec![0.9f32, 0.1], vec![0.5, 0.5], vec![0.4, 0.4]];
let idx = pareto_indices(&points).unwrap(); // general N-d
let idx2 = pareto_indices_2d(&points).unwrap(); // optimized 2-d path
// k-dominance: a point is dominated only if worse in >= k objectives
let relaxed = pareto_indices_k_dominance(&points, 2).unwrap();
// Non-dominated sorting: partition into successive Pareto layers
let layers = pareto_layers(&points).unwrap();
// layers[0] = Pareto front, layers[1] = front of remainder, ...For streaming / online optimization where memory must be bounded:
use pare::{Direction, EpsilonArchive};
let mut archive = EpsilonArchive::new_uniform(
vec![Direction::Maximize, Direction::Maximize],
0.1, // grid cell width per dimension
);
// Insert many points; archive stays bounded
for i in 0..1000 {
let x = (i as f64) / 1000.0;
archive.push(vec![x, 1.0 - x], i);
}
assert!(archive.len() <= 100); // at most ceil(1/0.1)^2 cells
// Convert to ParetoFrontier for analysis
let frontier = archive.into_frontier();Compare fronts with Generational Distance (GD) and Inverted Generational Distance (IGD):
use pare::{generational_distance, inverted_generational_distance};
let front = vec![vec![1.0, 0.0], vec![0.0, 1.0]];
let reference = vec![vec![1.0, 0.0], vec![0.5, 0.5], vec![0.0, 1.0]];
let gd = generational_distance(&front, &reference).unwrap(); // convergence
let igd = inverted_generational_distance(&front, &reference).unwrap(); // convergence + spreadThe sensitivity module computes finite-difference Jacobians and objective redundancy analysis:
use pare::sensitivity::{finite_difference_jacobian, analyze_redundancy};
let objectives: Vec<fn(&[f64]) -> f64> = vec![
|x| x[0] * x[0],
|x| (x[0] - 1.0).powi(2),
];
let jac = finite_difference_jacobian(&[0.5], &objectives, 1e-6);
let analysis = analyze_redundancy(&jac).unwrap();
// analysis.redundant_pairs -- objectives that move togethersensitivity_analysis.rs -- Multi-objective sensitivity analysis for a simulated 3-arm experiment with 9 covariate cells and 6 objectives. Builds a finite-difference Jacobian across the full parameter space, computes the eigenvalue spectrum to find how many objectives actually matter (effective dimensionality), identifies redundant pairs via cosine similarity, and reports which objectives can be dropped without losing decision power. Useful when you suspect your objective set is over-specified.
cargo run --example sensitivity_analysisFor background on dominance, crowding distance, and hypervolume, see
TECHNICAL_BACKGROUND.md.
MIT OR Apache-2.0