On combinatorial optimization problems on matroids with uncertain weights. (English) Zbl 1110.90075
Summary: The combinatorial optimization problem on weighted matroid is considered. It is assumed that the weights in the problem are ill-known and they are modeled as fuzzy intervals. The optimality of solutions and the optimality of elements are characterized. This characterization is performed in the setting of possibility theory. A method of choosing a solution under uncertainty is also proposed.
MSC:
| 90C27 | Combinatorial optimization |
References:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows, Theory, Algorithms and Applications (1993), Prentice-Hall: Prentice-Hall Engelwood Cliffs, NJ · Zbl 1201.90001 |
| [2] | I. Aron, P. van Hentenryck, A constraint satisfaction approach to the robust spanning tree with interval data, in: Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence. Edmonton, Canada, 2002.; I. Aron, P. van Hentenryck, A constraint satisfaction approach to the robust spanning tree with interval data, in: Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence. Edmonton, Canada, 2002. |
| [3] | Averbakh, I., On the complexity of a class of combinatorial optimization problems with uncertainty, Mathematical Programming, 90, 263-272 (2001) · Zbl 0980.90070 |
| [4] | Averbakh, I.; Lebedev, V., Interval data minmax regret network optimization problems, Discrete Applied Mathematics, 138, 289-301 (2004) · Zbl 1056.90010 |
| [5] | Chanas, S.; Kasperski, A., Possible and necessary optimality of solutions in the single machine scheduling problem with fuzzy parameters, Fuzzy Sets and Systems, 142, 359-371 (2004) · Zbl 1044.90032 |
| [6] | Chanas, S.; Zieliński, P., Critical path analysis in the network with fuzzy activity times, Fuzzy Sets and Systems, 122, 195-204 (2001) · Zbl 1015.90096 |
| [7] | Chanas, S.; Zieliński, P., The computational complexity of the criticality problems in a network with interval activity times, European Journal of Operational Research, 136, 541-550 (2002) · Zbl 1008.90029 |
| [8] | Conde, E., An improved algorithm for selecting \(p\) items with uncertain returns according to the minmax regret criterion, Mathematical Programming, 100, 345-353 (2004) · Zbl 1070.90129 |
| [9] | Dubois, D.; Prade, H., Operations on fuzzy numbers, International Journal of Systems Science, 30, 613-626 (1978) · Zbl 0383.94045 |
| [10] | Dubois, D.; Prade, H., Possibility Theory: An Approach to Computerized Processing of Uncertainty (1988), Plenum Press: Plenum Press New York · Zbl 0703.68004 |
| [11] | Dubois, D.; Fargier, H.; Prade, H., Fuzzy constraints in job-shop scheduling, Intelligent Manufacturing, 6, 215-234 (1995) |
| [12] | Dubois, D.; Fargier, H.; Fortemps, P., Fuzzy scheduling: Modelling flexible constraints vs. coping with incomplete knowledge, European Journal of Operational Research, 147, 231-252 (2003) · Zbl 1037.90028 |
| [13] | Fortin, J.; Zieliński, P.; Dubois, D.; Fargier, H., Interval analysis in scheduling, (van Beek, P., Principles and Practice of Constraint Programming—CP 2005 11th International Conference, CP 2005. Principles and Practice of Constraint Programming—CP 2005 11th International Conference, CP 2005, Lecture Notes in Computer Science, vol. 3709 (2005), Springer Verlag: Springer Verlag Berlin), 226-240 · Zbl 1153.90421 |
| [14] | A. Kasperski, P. Zieliński, An approximation algorithm for interval data minmax regret combinatorial optimization problems, Information Processing Letters, in press.; A. Kasperski, P. Zieliński, An approximation algorithm for interval data minmax regret combinatorial optimization problems, Information Processing Letters, in press. · Zbl 1184.68640 |
| [15] | A. Kasperski, P. Zieliński, A characterization of optimality of elements in combinatorial optimization problems with fuzzy weights, Raport serii PREPRINTY nr 021, Inst. Organizacji i Zarza¸dzania PWr, Wrocław 2005.; A. Kasperski, P. Zieliński, A characterization of optimality of elements in combinatorial optimization problems with fuzzy weights, Raport serii PREPRINTY nr 021, Inst. Organizacji i Zarza¸dzania PWr, Wrocław 2005. |
| [16] | A. Kasperski, P. Zieliński, Some general properties of interval data minmax regret combinatorial optimization problems, Raport serii PREPRINTY nr 022, Inst. Organizacji i Zarza¸dzania PWr, Wrocław 2005.; A. Kasperski, P. Zieliński, Some general properties of interval data minmax regret combinatorial optimization problems, Raport serii PREPRINTY nr 022, Inst. Organizacji i Zarza¸dzania PWr, Wrocław 2005. |
| [17] | Kouvelis, P.; Yu, G., Robust Discrete Optimization and its Applications (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0873.90071 |
| [18] | Okada, S., Fuzzy shortest path problems incorporating interactivity among paths, Fuzzy Sets and Systems, 142, 335-357 (2004) · Zbl 1045.90092 |
| [19] | Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press New York · Zbl 0784.05002 |
| [20] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization (1998), Dover Publications, Inc.: Dover Publications, Inc. Mineola, NY · Zbl 0944.90066 |
| [21] | Sotskov, Y. N.; Leontev, V. K.; Gordeev, E. N., Some concepts of stability analysis in combinatorial optimization, Discrete Applied Mathematics, 58, 169-190 (1995) · Zbl 0833.90098 |
| [22] | Whitney, H., On the abstract properties of linear dependence, American Journal of Mathematics, 57, 509-533 (1935) · JFM 61.0073.03 |
| [23] | Yaman, H.; Karaşan, O. E.; Pinar, M. C., The robust spanning tree problem with interval data, Operations Research Letters, 29, 31-40 (2001) · Zbl 0981.05029 |
| [24] | Zadeh, L., Fuzzy Sets, Information and Control, 8, 338-353 (1965) · Zbl 0139.24606 |
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.
