Pareto Frontier

The Pareto Frontier, or Pareto set, is the set of choices which optimizes a system. This package calculates the optimal set of points in a 2D system.

For a given system, the Pareto frontier or Pareto set is the set of parameterizations (allocations) that are all Pareto efficient. Finding Pareto frontiers is particularly useful in engineering. By yielding all of the potentially optimal solutions, a designer can make focused tradeoffs within this constrained set of parameters, rather than needing to consider the full ranges of parameters.

The Pareto frontier, P(Y), may be more formally described as follows. Consider a system with function , where ''X'' is a compact set of feasible decisions in the metric space , and ''Y'' is the feasible set of criterion vectors in , such that .

We assume that the preferred directions of criteria values are known. A point is preferred to (strictly dominates) another point , written as . The Pareto frontier is thus written as:

Installation

$ npm install --save pareto-frontier

For use in the browser, use browserify.

Usage

const pf = require('pareto-frontier');

pf.getParetoFrontier(graph)

Evaluates the Pareto Frontier. graph must be an array of points. Each point must be an array of length two (or more). Additional information can be stored in each point and will pass through. Eg: [55, 42, 'red'].

Returned points are the Pareto Optimal set sorted to form a line.

const graph = [
    [55, 42],
    [60, 22],
    [83, 20],
    [20, 81],
    [41, 35],
    [12, 32],
    [29, 17],
    [64, 55],
    [47, 31],
    [89, 10],
    [68, 66],
    [33, 35],
    [72, 47],
    [33, 90],
    [49, 25],
];

const out = pf.getParetoFrontier(graph);

/* returns:
[
    [89, 10],
    [83, 20],
    [72, 47],
    [68, 66],
    [33, 90]
]
*/

Direction of Pareto Frontier

Optional options object may be pass to getParetoFrontier(graph, options) to specify which direction to optimize.

| Top Left Pareto Frontier | | ------ | | | | pf.getParetoFrontier(graph, { optimize: 'topLeft' }); |

| Top Right Pareto Frontier | | ------ | | | | pf.getParetoFrontier(graph, { optimize: 'topRight'} ); |

| Bottom Right Pareto Frontier | | ------ | | | | pf.getParetoFrontier(graph, { optimize: 'bottomRight'} ); |

| Bottom Left Pareto Frontier | | ------ | | | | pf.getParetoFrontier(graph, { optimize: 'bottomLeft'} ); |

Bad inputs

For non-wellformed inputs, a TypeError will be thrown.

const graph = [
	[0,-4],
	[1],  // Missing second dimension
	[2,0],
];

// Throws a TypeError
const out = pf.getParetoFrontier(graph);

Tests

Unit

Unit tests use the Mocha test framework with Chai assertions. To run the tests, execute the following command in the top-level application directory:

$ npm test

All new feature development should have corresponding unit tests to validate correct functionality.

Test Coverage

This repository uses Istanbul as its code coverage tool. To generate a test coverage report, execute the following command in the top-level application directory:

$ npm run test-cov

Istanbul creates a ./reports/coverage directory. To access an HTML version of the report,

License

MIT license.

Copyright

Copyright © 2016. The pareto-frontier Authors.

Description text partially via Wikipedia.