pare

Pareto frontier and skyline query primitives.

[dependencies]
pare = "0.2.0"

Quick start

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 excluded

Mixed objectives

When 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 out

Selecting from the frontier

Pick 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);

Normalization and scaling

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);

Post-hoc filtering

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);

Convenience functions

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, ...

Epsilon-dominance archiving

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();

Quality indicators

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 + spread

Sensitivity analysis

The sensitivity module computes finite-difference Jacobians and objective redundancy analysis to find which objectives can be dropped. See the sensitivity_analysis example and TECHNICAL_BACKGROUND.md for details.

License

MIT OR Apache-2.0