×

Multi-objective problems in terms of relational algebra. (English) Zbl 1138.90468

Berghammer, Rudolf (ed.) et al., Relations and Kleene algebra in computer science. 10th international conference on relational methods in computer science, and 5th international conference on applications of Kleene algebra, RelMiCS/AKA 2008, Frauenwörth, Germany, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78912-3/pbk). Lecture Notes in Computer Science 4988, 84-98 (2008).
Summary: Relational algebra has been shown to be a powerful tool for solving a wide range of combinatorial optimization problems with small computational and programming effort. The problems considered in recent years are single-objective ones where one single objective function has to be optimized. With this paper we start considerations on the use of relational algebra for multi-objective problems. In contrast to single-objective optimization multiple objective functions have to be optimized at the same time usually resulting in a set of different trade-offs with respect to the different functions. On the one hand, we examine how to solve the mentioned problem exactly by using relational algebraic programs. On the other hand, we address the problem of objective reduction that has recently been shown to be NP-hard. We propose an exact algorithm for this problem based on relational algebra. Our experimental results show that this algorithm drastically outperforms the currently best one.
For the entire collection see [Zbl 1136.68002].

MSC:

90C29 Multi-objective and goal programming
03G15 Cylindric and polyadic algebras; relation algebras
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C59 Approximation methods and heuristics in mathematical programming

Software:

RelView; Knapsack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beier, R.; Vöcking, B., Random knapsack in expected polynomial time., J. Comput. Syst. Sci., 69, 3, 306-329 (2004) · Zbl 1062.90037 · doi:10.1016/j.jcss.2004.04.004
[2] Berghammer, R.; Ganzha, V. G.; Mayr, E. W.; Vorozhtsov, E. V., Solving algorithmic problems on orders and lattices by relation algebra and RelView, Computer Algebra in Scientific Computing, 49-63 (2006), Heidelberg: Springer, Heidelberg · Zbl 1141.68671 · doi:10.1007/11870814_4
[3] Berghammer, R.; Leoniuk, B.; Milanese, U.; de Swart, H., Implementation of relational algebra using binary decision diagrams, Relational Methods in Computer Science, 241-257 (2002), Heidelberg: Springer, Heidelberg · Zbl 1027.68036 · doi:10.1007/3-540-36280-0_17
[4] Berghammer, R.; Milanese, U.; MacCaull, W.; Winter, M.; Düntsch, I., Relational approach to boolean logic problems, Relational Methods in Computer Science, 48-59 (2006), Heidelberg: Springer, Heidelberg · Zbl 1185.03090 · doi:10.1007/11734673_4
[5] Berghammer, R.; Neumann, F.; Ganzha, V. G.; Mayr, E. W.; Vorozhtsov, E. V., RelView – an OBDD-based computer algebra system for relations, Computer Algebra in Scientific Computing, 40-51 (2005), Heidelberg: Springer, Heidelberg · Zbl 1144.68384 · doi:10.1007/11555964_4
[6] Berghammer, R.; Rusinowska, A.; de Swart, H. C.M., Applying relational algebra and RelView to coalition formation, European Journal of Operational Research, 178, 2, 530-542 (2007) · Zbl 1171.91312 · doi:10.1016/j.ejor.2006.01.022
[7] Beyer, D.; Noack, A.; Lewerentz, C., Efficient relational calculation for software analysis, IEEE Transactions on Software Engineering, 31, 2, 137-149 (2005) · doi:10.1109/TSE.2005.23
[8] Brockhoff, D.; Zitzler, E.; Waldmann, K. H.; Stocker, U. M., Dimensionality reduction in multiobjective optimization: The minimum objective subset problem, Operations Research Proceedings 2006, 423-430 (2007), Heidelberg: Springer, Heidelberg · Zbl 1209.90311 · doi:10.1007/978-3-540-69995-8_68
[9] Ehrgott, M., Multicriteria Optimization (2005), Berlin: Springer, Berlin · Zbl 1132.90001
[10] Goemans, M. X., Minimum bounded degree spanning trees, Proc. of FOCS 2006, 273-282 (2006), Los Alamitos: IEEE Computer Society Press, Los Alamitos
[11] Kehden, B.; Schmidt, R. A., Evaluating sets of search points using relational algebra, Relations and Kleene Algebra in Computer Science, 266-280 (2006), Heidelberg: Springer, Heidelberg · Zbl 1134.68497 · doi:10.1007/11828563_18
[12] Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack Problems (2004), Heidelberg: Springer, Heidelberg · Zbl 1103.90003
[13] Könemann, J.; Ravi, R., Primal-dual meets local search: Approximating MSTs with nonuniform degree bounds, SIAM J. Comput., 34, 3, 763-773 (2005) · Zbl 1075.68101 · doi:10.1137/S0097539702418048
[14] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), Chichester: Wiley, Chichester · Zbl 0708.68002
[15] Nemhauser, G.; Ullmann, Z., Discrete dynamic programming and capital allocation., Management Sci., 15, 9, 494-505 (1969) · Zbl 1231.90339 · doi:10.1287/mnsc.15.9.494
[16] Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Many birds with one stone: multi-objective approximation algorithms. In: Proc. of STOC 1993, pp. 438-447 (1993) · Zbl 1310.68247
[17] Schmidt, G.; Ströhlein, T., Relations and Graphs - Discrete Mathematics for Computer Scientists (1993), Heidelberg: Springer, Heidelberg · Zbl 0900.68328
[18] Singh, M.; Lau, L. C., Approximating minimum bounded degree spanning trees to within one of optimal., Proc. of STOC 2007, 661-670 (2007), New York: ACM Press, New York · Zbl 1232.68184
[19] Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization. In: Giannakoglou, K.C., et al. (eds.) Proc. of EUROGEN 2001, pp. 95-100. CIMNE (2002)
[20] Zitzler, E.; Thiele, L., Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach, IEEE Transactions on Evolutionary Computation, 3, 4, 257-271 (1999) · doi:10.1109/4235.797969
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.