On the number of non-dominated points of a multicriteria optimization problem

详细信息    查看全文

• 作者：Cristina Bazgan ; Florian Jamain ; Daniel V ; erpooten
• 关键词：Multicriteria optimization ; Non-dominated points ; Comparability graph ; Stability number ; Product of chains ; Sperner property
• 刊名：Discrete Applied Mathematics
• 出版年：December, 2013
• 年：2013
• 卷：161
• 期：18
• 页码：2841-2850
• 全文大小：440 K

文摘

This work proposes an upper bound on the maximal number of non-dominated points of a multicriteria optimization problem. Assuming that the number of values taken on each criterion is known, the criterion space corresponds to a comparability graph or a product of chains. Thus, the upper bound can be interpreted as the stability number of a comparability graph or, equivalently, as the width of a product of chains. Standard approaches or formulas for computing these numbers are impractical. We develop a practical formula which only depends on the number of criteria. We also investigate the tightness of this upper bound and the reduction of this bound when feasible, possibly efficient, solutions are known.