On weighting two criteria with a parameter in combinatorial optimization problems
- 作者：C.W. Duin ; c.w.duin@uva.nl ; A. Volgenant
- 关键词：Bicriteria combinatorial problems ; Spanning tree ; Linear assignment ; Single machine scheduling
- 刊名：European Journal of Operational Research
- 出版年：2012
- 期刊代码：58_03772217
- 类别：et
- 出版时间：16 August, 2012
- 卷：221
- 期：1
- 页码：1-6
- 文件大小：268 K
摘要
Two criteria in a combinatorial problem are often combined in a weighted sum objective using a weighting parameter between 0 and 1. For special problem types, e.g., when one of the criteria is a bottleneck value, efficient algorithms are known that solve for a given value of the weighting parameter.
We transform the underlying enumeration method into a parametric algorithm solving simultaneously for all values of the weighting parameter. Efficient implementations are presented for combinatorial problems with criteria as balanced optimization, min-sum with min-max, and min-sum with balanced optimization, considering the spanning tree, the linear assignment and the single machine scheduling problem. Further the new algorithmic scheme can easily incorporate a trade-off of the criteria by means of penalty functions, again without consequences for the algorithm and its complexity order.