Skip to content

Calculates the optimal set of points in a multi-dimentional system

License

Notifications You must be signed in to change notification settings

justinormont/pareto-frontier

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Pareto Frontier

NPM version Build Status Coverage Status Dependencies

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
Top Left Pareto Frontier
pf.getParetoFrontier(graph, { optimize: 'topLeft' });
Top Right Pareto Frontier
Top Left Pareto Frontier
pf.getParetoFrontier(graph, { optimize: 'topRight'} );
Bottom Right Pareto Frontier
Bottom Right Pareto Frontier
pf.getParetoFrontier(graph, { optimize: 'bottomRight'} );
Bottom Left Pareto Frontier
Bottom Right 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.

About

Calculates the optimal set of points in a multi-dimentional system

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published