Journal "Computational Technologies"

Article information

2021 , Volume 26, № 6, p.82-109

Prolubnikov A.V.

Approaches to discrete optimization problems with interval objective function

Optimization problems with uncertainties in their input data have been investigated by many researchers in different directions. There are a lot of sources of the uncertainties in the input data for applied problems. Inaccurate measurements and variability of the parameters with time are some of such sources. The interval of possible values of uncertain parameter is the natural and the only possible way to represent the uncertainty for a wide share of applied problems. We consider discrete optimization problems with interval uncertainties in their objective functions. The purpose of the paper is to provide an overview of the investigations in this field. The overview is given in the overall context of the researches of optimization problems with uncertainties.

We review the interval approaches for the discrete optimization problem with interval objective function. The approaches we consider operate with the interval values and are focused on obtaining possible solutions or certain sets of the solutions that are optimal according to some concepts of optimality that are used by the approaches. We consider the different concepts of optimality: robust solutions, the Pareto sets, weak and strong solutions, the united solution sets, the sets of possible approximate solutions that correspond to possible values of uncertain parameters. All the approaches we consider allow absence of information on probabilistic distribution on intervals of possible values of parameters, though some of them may use the information to evaluate the probabilities of possible solutions, the distribution on the interval of possible objective function values for the solutions, etc. We assess the possibilities and limitations of the considered approaches.

[full text]
Keywords: discrete optimization, interval uncertainty

doi: 10.25743/ICT.2021.26.6.007

Author(s):
Prolubnikov Alexander Vyacheslavovich
Position: engineer
Office: Omsk Scientific Center of Siberian branch of the Russian Academy of Sciences
Address: 644010, Russia, Omsk, Marx avenue, 15
Phone Office: (3812) 64-42-38
E-mail: a.v.prolubnikov@mail.ru
SPIN-code: 4729-9643

References:

1. Garey M., Johnson D. Computers and intractability: A guide to the theory of NP-completness. San-Francisco: Freeman; 1978: 419.

2. Novitskiy P.V., Zorgraf I.A. Otsenka pogreshnostey rezul’tatov izmereniy [Evaluation of measurement errors]. Leningrad: Energoatomizdat. Leningradskoe otdelenie; 1991: 304. (In Russ.)

3. Orlov A.I. Is it often that the results of observations are normally distributed? Zavodskaya Laboratoria. 1991; 57(7):64–66. (In Russ.)

4. Perepelitsa V.A., Sergienko I.V. A study of one class of integer multicriterion problems. USSR Computational Mathematics and Mathematical Physics. 1988; 28(2):63–75. DOI:10.1016/0041-5553(88)90144-9.

5. Kearfott R.B., Kreinovich V. Applications of interval computations: An introduction. R.B. Kearfott et al. (eds.). Applications of Interval Computations. Kluwer, Dordrecht. 1996: 1–22. DOI:10.1007/978-1-4613-3440-8_1.

6. IEEE Standard for Interval Arithmetic. In IEEE Std 1788-2015. N.Y.: The Institute of Electrical and Electronics Engineers, Inc; 2015: 79. DOI:10.1109/IEEESTD.2015.7140721.

7. Allen J.F. Maintaining knowledge about temporal intervals. Communications of the ACM. 1983; 26(11):832–843. DOI:10.1145/182.358434.

8. Shary S.P. Finite-dimensional interval analysis. Available at: http://www.nsc.ru/interval/ Library/InteBooks/SharyBook.pdf (accessed 21.09.2021) (In Russ.)

9. Fishburn P. Utility theory for decision making. N.Y.: Wiley; 1970: 234.

10. Voshchinin A.P., Sotirov G.P. Optimizatsiya v usloviyakh neopredelennosti [Optimization under uncertainty]. Moscow: MEI; Sofiya: Tekhnika; 1989: 224. (In Russ.)

11. Tsoukias A., Vincke Ph. A characterization of PQI interval orders. Discrete Applied Mathematics. 2003; 122(2):387–397. DOI:10.1016/S0166-218X(02)00256-1.

12. Aschepkov L.T., Davydov D.V. Numerical characterization for interval inequalities: Properties and applications. Computational Technologies. 2006; 11(4):13–22. (In Russ.)

13. Hu B., Wang S. A novel approach in uncertain programming. Part I: New arithmetic and order relation of interval numbers. Journal of Industrial and Management Optimization. 2006; 2(4):351–371. DOI:10.3934/jimo.2006.2.351.

14. Collins D., Hu C. Studying interval valued matrix games with fuzzy logic. Journal of Soft Computing. 2008: 12(2):147–155. DOI:10.1007/s00500-007-0207-6.

15. Kouvelis P., Yu G. Robust discrete optimization and its applications. Dordrecht: Kluwer Academic Publishers; 1997: 358.
DOI:10.1007/978-1-4757-2620-6.

16. Kaspersky A., Zielinski P. Robust discrete optimization under discrete and interval uncertainty: A survey. International Series in Operations Research and Mangement Science. 2016; 113–143. DOI:10.1007/978-3-319-33121-8_6.

17. Kaspersky A., Zielinski P. Robust independent set problems on interval graphs. Optimization Letters. 2015; (9):427–436.
DOI:10.1007/S11590-014-0773-3.
18. Soyster A.L. Convex programming with set inclusive constraints and applications to inexact linear programming. Operations Research. 1973; 21(5):1154–1157. DOI:10.1287/opre.21.5.1154.

19. Falk J.E. Exact solutions of inexact linear programs. Operations Research. 1976; 24(4):783–786.
DOI:10.1287/opre.24.4.783.

20. Vatolin A.A. On the problems of linear programming with interval coefficients. USSR Computational Mathematics and Mathematical Physics. 1984; 24(6):18–23. DOI:10.1016/0041-5553(84)90003-X.

21. Agayan G.M., Ryutin A.A., Tikhonov A.N. The problem of linear programming with approximate data. USSR Computational Mathematics and Mathematical Physics. 1984; 24(5):14–19. DOI:10.1016/0041-5553(84)90149-6.

22. Eremin I.I. Protivorechivye modeli optimal’nogo planirovaniya [Contradictory models of optimal planning]. Moscow: Nauka; 1988: 160. (In Russ.)

23. Rohn J. Complexity of some linear problems with interval data. Reliable Computing. 1997; 3(3):315–323. DOI:10.1023/A:1009987227018.

24. Fiedler M., Nedoma J., Ramik J., Rohn J., Zimmerman K. Linear optimization problems with inexact data. N.Y.: Springer Science & Business Media, Inc.; 2006: 288. DOI:10.1007/0-387-32698-7.

25. Libura M. Integer programming problems with inexact objective function. Control and Cybernetics. 1980; 9(4):189–202.

26. Roshchin V.A., Semenova N.V., Sergienko I.V. A decomposition approach to the solution of some integer programming problems with inexact data. USSR Computational Mathematics and Mathematical Physics. 1990; 30(3):107–112. DOI:10.1016/0041-5553(90).90197-z.

27. Semenova N.V. Solution of a problem of the generalized integer programming. Kibernetika. 1984; (5):25–31. (In Russ.)

28. Roshchin V.A., Sergienko I.V. Solution of integer programming problems with inexact data. Cybernetics and System Analysis. 1994; 30(5):666–671. DOI:10.1007/bf02367747.

29. Sergienko I.V., Semenova N.V. Integer programming problems with inexact data: Exact and approximate solutions. Cybernetics and System Analysis. 1995; 31(6):842–851. DOI:10.1007/bf02366621.

30. Sergienko I.V., Shylo V.P. Problems of discrete optimization: Challenges and main approaches. Cybernetics and System Analysis. 2006; 42(4):465–481. DOI:10.1007/s10559-006-0086-3.

31. Beraldi P., Ruszczynski A. The probabilistic set-covering problem. Operations Research. 2002; 50(6):956–967. DOI:10.1287/opre.50.6.956.345.

32. Fischetti M., Monaci M. Cutting plane versus compact formulations for uncertain (integer) linear programs. Mathematical Programming Computation. 2012; 4(3):239–273. DOI:10.1007/s12532-012-0039-y.

33. Kaspersky A. Discrete optimization with interval data. Minmax regret and fuzzy approach. Studies in Fuzziness and Soft Computing. Springer-Verlag, Berlin, Heidelberg. 2008; (228):236. DOI:10.1007/978-3-540-78484-5.

34. Hwang M.J., Chiang C.I., Liu Y.H. Solving a fuzzy set-covering problem. Mathematical and Computer Modelling. 2004; 40(7):861–865. DOI:10.1016/j.mcm.2004.10.015.

35. Chiang C.I., Hwang M.J., Liu Y.H. An alternative formulation for certain fuzzyset-covering problems. Mathematical and Computer Modelling. 2005; 42(3–4):363–365. DOI:10.1016/j.mcm.2004.05.012.

36. Kozina G.L., Perepelitsa V.A. Interval spanning trees problem: Solvability and computational complexity. Interval Computations. 1994; (1):42–50.

37. Perepelitsa V.A., Tebueva F.B. Discrete optimization problems with interval parameters. Computational Mathematics and Mathematical Physics. 2010. 50(5):795–804. DOI:10.1134/S0965542510050052.

38. Demchenko A.I. Modeling the problem of transport network synthesis under conditions of uncertain initial information. International Conference of Industrial Engineering. Procedia Engineering. 2015; (129):676–680. DOI:10.1016/j.proeng.2015.12.090.

39. Demchenko A.I. Modeling the problem of transport network synthesis under conditions of uncertain initial information. International Conference of Industrial Engineering. Procedia Engineering. 2015; (129):676–680. DOI:10.1016/j.proeng.2015.12.090.

40. Yaman H., Karasan O.E., Pinar M.C. Minimum spanning tree problem with interval data. Technical Report 9909, Department of Industrial Engineering, Bilkent University, Ankara, Turkey. 1999: 16.

41. Aissi H., Bazgan C., Vanderpooten D. Approximation of min-max and min-max regret versions of some combinatorial optimization problems. European Journal of Operational Research. 2007; 179(2):281–290. DOI:10.1016/j.ejor.2006.03.023.

42. Yu G., Kouvelis P. Complexity results for a class of min-max problems with robust optimization applications. P.M. Pardalos (ed.) Complexity in Numerical Optimization. World Scientyfic. 1993: 501–511. DOI:10.1142/9789814354363_0023.

43. Yu G., Yang J. On the robust shortest path problem. Computers and Operations Research. 1998; 25(6):457–468. DOI:10.1016/S0305-0548(97)00085-3.

44. Bertsimas D., Sim M. Robust discrete optimization and network flows. Mathematical Programming. 2003; (98):49–71. DOI:10.1007/s10107-003-0396-4.

45. Luce R.D., Raiffa H. Games and decisions: Introduction and critical survey. N.Y.: Dover Publications Inc.; 1989: 544.

46. Perepelitsa V.A., Tebueva F.B., Shenkao T.M. On computational complexity of interval problems on graphs. Bulletin of Higher Education Institutes. North Caucasus Region. Natural Sciences. 2006; (12):18–30. (In Russ.)

47. Perepelitsa V.A., Kozin I.V., Maksishko N.K. Optimization problems on graphs with interval parameters. Cybernetics and System Analysis. 2009; 45(2):3–14. (In Russ.)

48. Kozina G.L., Perepelitsa V.A. Interval discrete models and multiobjectivity. Complexity estimates. Interval Computations. 1993; (1):51–59.

49. Shaposhnikova O.I., Temirova L.G. Interval spanning tree problem on a topological criterion. Scientific Journal of KubSAU. 2016; 115(01):369–378. (In Russ.)

50. Kozina G.L. Discrete optimization problems with interval data: Pareto set of solutions or set of weak solutions? Reliable Computing. 2004; 10(6):469–487. DOI:10.1023/B:REOM.0000047095.22096.16.

51. Prolubnikov A.V. The set cover problem with interval weights and the greedy algorithm for its solution. Computational Technologies. 2015; 20(6):70–84. (In Russ.)

52. Kozina G.L. A rule for selection of solutions for optimization problems on graphs with interval parameters. Proceedings of 13-th Baikal International School-Seminar Optimization Methods and Their Applications. Volume 4. Interval Analysis. Irkutsk-Severobaikalsk. 2005; (4):51–55. (In Russ.)

53. Levin V.I. Discrete optimization under interval uncertainty. Automation and Remote Control. 1992; 53(7):1039–1047.

54. Levin V.I. Comparison of intervals and optimization under uncertainty. Journal “Tambov University Review. Series: Humanities”. 2002; 7(3):383–389. (In Russ.)

55. Medvedev S.N., Medvedeva O.A. About the solution of the interval integer linear optimization problems. Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies. 2016; (4):37–42. (In Russ.)

56. Popov V.P., Mayorova I.V. An interval approach to optimization of solving of multi-objective task about appointments. Journal of Applied Informatics. 2015; 3(57):122–131. (In Russ.)

57. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: Algorithms and complexity. New Jersey: Prentice Hall; 1987: 496.

58. Feige U. A threshhold of ln 𝑛 for approximating set cover. Journal of the ACM. 1998; 45(4):634–652. DOI:10.1145/285055.285059.

59. Frieze A., Szpankowski W. A greedy algorithm for the shortest common superstring is asymptotically optimal. Algorithmica. 1998; 21(1):21–36. DOI:10.1007/PL00009207.

60. Prolubnikov A.V. On an approach to set covering problem with interval weights and its computational complexity. Computational Technologies. 2017; 22(2):115–126. (In Russ.)

61. Chvatal V. A greedy heuristic for the set-covering problem. Mathematics of Operation Research. 1979; 4(3):233–235. DOI:10.1287/moor.4.3.233.

Bibliography link:
Prolubnikov A.V. Approaches to discrete optimization problems with interval objective function // Computational technologies. 2021. V. 26. № 6. P. 82-109