Pareto Algebra

Many problems involve multi-objective optimization challenges, where a trade-off needs to be struck between two or more potentially conflicting goals. If we do not fix an a priori decision mechanism to select a possible solution, we can categories solutions as potentially optimal, or never optimal. This not is called Pareto optimality, introduced conceptually in the context of economics by Vilfredo Pareto in the early 20th century (in English translation, [1]) as follows.

We will say that the members of a collectivity enjoy
maximum ophelimity in a certain position when it is impossible to
find a way of moving from that position very slightly in such a
manner that the ophelimity enjoyed by each of the individuals of
that collectivity increases or decreases. That is to say, any small
displacement in departing from that position necessarily has the
effect of increasing the ophelimity which certain individuals enjoy,
and decreasing that which others enjoy, of being agreeable to some
and disagreeable to others.

It is widely used in various engineering disciplines. Multi-objective optimization is typically treated in terms of the analysis of continuous functions on real-valued domains [2].

In many cases, however, the criteria are discrete, and sometimes not totally ordered. Moreover, it is often necessary or desirable to compute Pareto points in a compositional manner.

To support this type of analysis, we have developed Pareto Algebra as an algebra of Pareto points [3]. It provides an algebraic characterization of Pareto optimality and a number of useful operators to compute Pareto optimal configurations of a composite system from the Pareto optimal configurations of its components.

Pareto Algebra provides a basis for the semantics of the Quality and Resource Management Language. and its interface model [4, 5].

Pareto Analysis

A configuration describes a possible choice (for instance of a potential system realization) by a number of values of different optimization criteria. These so-called quantities have a partial order relation associated with them to indicate which values are better than others.

The well-known Pareto optimality criterion specifies that one configuration dominates the other when it is at least as good in all of the criteria and also strictly better in at least one of them. In that case, the former configuration is always preferred over the latter one, independent of how the various optimization criteria are weighed. Such configurations are called Pareto points (the solid points in Figure 1).

Example

As an example of application of the Pareto Algebra and Calculator we look at an MPEG-4 video stream that is played from a media center device over a wireless connection to a handheld device. The optimisation criteria that matter to the end-user are the following.

• Quality of the video. Although an objective measure of perceived quality is difficult to give. Signal-to-noise ratio, frame rate and frame size of the video contribute to the quality in a higher is better fashion. For the example we represent a combination of these aspects as a single number, but any other model of quality could be fit in, including considering the three aspects as individual, independent optimization criteria.
• Energy consumption by the hand held, or battery lifetime of the hand held. Depending on the settings, the hand held may use less or more energy for decoding and rendering the video. The user prefers the device to run out of energy as late as possible.
• Latency of the transmission. Long latency makes the play back slow to respond to commands from the user and hence should be minimized.

All of the above criteria cannot be optimized independently. There is a trade-off. High quality video requires more processing and hence more energy. Energy savings are possible at the expense of additional latency.

Figure 3: Configuring an application-platform mapping

MPEG-4 Encoder

Figure 4: Quality vs. bit rate of an MPEG-4 stream

The parameters that can be changed on the MPEG-4 encoder, that determine the bit rate and the quality, considered in this example, are the frame rate, the frame size and the bit rate through control of the quantization parameter. We consider eight combinations of parameters, listed in Table 1.

The xml specification of the encoder profile can be seen here.

Wireless Transmission

Bursty transmission of data allows for pauses in transmission during which the transceiver can be turned off. This can save energy over lower bandwidth transmission. At the expense of in particular additional latency and additional memory requirements for buffering, energy can thus be saved. The bit rate that needs to be supported by the transmission depends on the encode parameter settings.
Figure 5: Trade-offs in wireless transmission

Figure 5 shows a trade-off between bit rate, buffer capacity and power. The four dots represent four alternative configurations considered for configuration of the example setup.

Decoder on Hand Held Platform

At the end of the delivery chain, the stream is decoded and rendered on the hand held device. The parameter settings of the MPEG-4 encoded stream have their impact on the amount of processing that needs to be done on the device. Only a limited amount of processing is available and through voltage scaling (3 discrete available levels), the available processing power can be traded for energy consumption. In the example, separate models of the platform processor and the decoder application are combined to obtain a model of the hand held device (decoding + rendering). This results in the following table.

End-to-end model

Pareto algebra allows one to compositionally compute the end-to-end trade-offs of the delivery chain from the models of the components. The models of the decoder software and the processor platform have already been combined to determine the power consumption of the different MPEG-4 stream parameters. Additionally, all components should assume the same MPEG-4 parameter settings and the transmission should support the bit rate needed by the MPEG-4 stream. Energy consumption of the wireless transmission and the decoding and rendering are added up. Parameters that were relevant to compute the composition, but that are not relevant to the end user can be abstracted and the result is a set of configurations that are potentially interesting to the end-user. Finally, the user should decide about her or his preferences between a high quality, low latency or long battery lifetime solution.

Tools

Pareto Algebra operations are implemented in the Pareto Calculator [6].

The example above is available with the calculator.

Selected Related publications

• M. Geilen, T. Basten, B. Theelen, and R. Otten, “An algebra of pareto points,” Fundam. inf., vol. 78, iss. 1, p. 35–74, 2007.
  [Bibtex]

  @Article{GBTO07,
  author = {Geilen, Marc and Basten, Twan and Theelen, Bart and Otten, Ralph},
  journal = {Fundam. Inf.},
  title = {An Algebra of Pareto Points},
  year = {2007},
  issn = {0169-2968},
  month = {jan},
  number = {1},
  pages = {35–74},
  volume = {78},
  address = {NLD},
  issue_date = {January 2007},
  numpages = {40},
  publisher = {IOS Press},
  url = {https://dl.acm.org/doi/10.5555/2366476.2366479},
  }

• M. Hendriks, M. Geilen, K. Goossens, R. de Jong, and T. Basten, “Interface Modeling for Quality and Resource Management,” Logical Methods in Computer Science, vol. {Volume 17, Issue 2}, 2021.
  [Bibtex]

  @Article{HGGJB21,
  author = {Martijn Hendriks and Marc Geilen and Kees Goossens and Rob de Jong and Twan Basten},
  journal = {{Logical Methods in Computer Science}},
  title = {{Interface Modeling for Quality and Resource Management}},
  year = {2021},
  month = May,
  volume = {{Volume 17, Issue 2}},
  doi = {10.23638/LMCS-17(2:19)2021},
  keywords = {Computer Science - Logic in Computer Science ; Computer Science - Discrete Mathematics ; Computer Science - Performance},
  url = {https://lmcs.episciences.org/7513},
  }

• R. Hoes, T. Basten, C. -, M. Geilen, and H. Corporaal, “Quality-of-service trade-off analysis for wireless sensor networks,” Perform. evaluation, vol. 66, iss. 3-5, p. 191–208, 2009.
  [Bibtex]

  @article{HBTGC09,
  author = {Rob Hoes and
  Twan Basten and
  Chen{-}Khong Tham and
  Marc Geilen and
  Henk Corporaal},
  title = {Quality-of-service trade-off analysis for wireless sensor networks},
  journal = {Perform. Evaluation},
  volume = {66},
  number = {3-5},
  pages = {191--208},
  year = {2009},
  url = {https://doi.org/10.1016/j.peva.2008.10.007},
  doi = {10.1016/j.peva.2008.10.007},
  timestamp = {Mon, 26 Oct 2020 08:56:56 +0100},
  }

Acknowledgements

This work is supported by the Horizon 2020 ECSEL Joint Undertaking in the FitOpTiVis project, the European Commission through the IST-004042 project Betsy and the IST-216224 project MNEMEE.

References

@Book{Par71,
author = {V. Pareto},
title={Manual of Political Economy},
publisher = {Augustus M. Kelley Publishers},
address = {New York},
year={1971}
}

@book{SNT85,
title={Theory of multiobjective optimization},
author={Sawaragi, Yoshikazu and NAKAYAMA, HIROTAKA and TANINO, TETSUZO},
year={1985},
publisher={Elsevier}
}

@Article{GBTO07,
author = {Geilen, Marc and Basten, Twan and Theelen, Bart and Otten, Ralph},
journal = {Fundam. Inf.},
title = {An Algebra of Pareto Points},
year = {2007},
issn = {0169-2968},
month = {jan},
number = {1},
pages = {35–74},
volume = {78},
address = {NLD},
issue_date = {January 2007},
numpages = {40},
publisher = {IOS Press},
url = {https://dl.acm.org/doi/10.5555/2366476.2366479},
}

[4] M. Hendriks, M. Geilen, K. Goossens, R. de Jong, and T. Basten, “Interface Modeling for Quality and Resource Management,” Logical Methods in Computer Science, vol. {Volume 17, Issue 2}, 2021.
[Bibtex]

@Article{HGGJB21,
author = {Martijn Hendriks and Marc Geilen and Kees Goossens and Rob de Jong and Twan Basten},
journal = {{Logical Methods in Computer Science}},
title = {{Interface Modeling for Quality and Resource Management}},
year = {2021},
month = May,
volume = {{Volume 17, Issue 2}},
doi = {10.23638/LMCS-17(2:19)2021},
keywords = {Computer Science - Logic in Computer Science ; Computer Science - Discrete Mathematics ; Computer Science - Performance},
url = {https://lmcs.episciences.org/7513},
}

[5] F. van den Berg, V. Čamra, M. Hendriks, M. Geilen, P. Hnetynka, F. Manteca, P. Sánchez, T. Bureš, and T. Basten, “Qrml: a component language and toolset for quality and resource management,” in 2020 forum for specification and design languages (fdl), 2020, pp. 1-8.
[Bibtex]

@InProceedings{BCHea20,
author = {van den Berg, Freek and Čamra, Václav and Hendriks, Martijn and Geilen, Marc and Hnetynka, Petr and Manteca, Fernando and Sánchez, Pablo and Bureš, Tomáš and Basten, Twan},
booktitle = {2020 Forum for Specification and Design Languages (FDL)},
title = {QRML: A Component Language and Toolset for Quality and Resource Management},
year = {2020},
pages = {1-8},
doi = {10.1109/FDL50818.2020.9232936},
}

[6] M. Geilen and T. Basten, “A calculator for pareto points,” in 2007 design, automation test in europe conference exhibition, 2007, pp. 1-6.
[Bibtex]

@InProceedings{GB07,
author = {Geilen, Marc and Basten, Twan},
booktitle = {2007 Design, Automation Test in Europe Conference Exhibition},
title = {A Calculator for Pareto Points},
year = {2007},
pages = {1-6},
doi = {10.1109/DATE.2007.364605},
}