Abstract
We present a multidimensional optimization problem that is formulated and solved in the tropical mathematics setting. The problem consists of minimizing a nonlinear objective function defined on vectors over an idempotent semifield by means of a conjugate transposition operator, subject to constraints in the form of linear vector inequalities. A complete direct solution to the problem under fairly general assumptions is given in a compact vector form suitable for both further analysis and practical implementation. We apply the result to solve a multidimensional minimax single facility location problem with Chebyshev distance and with inequality constraints imposed on the feasible location area.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akian, M., Bapat, R., Gaubert, S.: Max-plus algebra. In: Hogben, L. (ed.) Handbook of Linear Algebra. Discrete Mathematics and its Applications, pp. 25-1–25-17. Taylor and Francis, Boca Raton (2007)
Baccelli, F.L., Cohen, G., Olsder, G.J., Quadrat, J.-P.: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley Series in Probability and Statistics. Wiley, Chichester (1993)
Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics. Springer, London (2010)
Carré, B.A.: An algebra for network routing problems. IMA J. Appl. Math. 7, 273–294 (1971)
Carré, B.: Graphs and Networks. Oxford Applied Mathematics and Computing Science Series. Clarendon Press, Oxford (1979)
Cuninghame-Green, R.A.: Describing industrial processes with interference and approximating their steady-state behaviour. Oper. Res. Quart. 13, 95–100 (1962)
Cuninghame-Green, R.A.: Minimax algebra and applications. Fuzzy Sets and Systems 41, 251–267 (1991)
Cuninghame-Green, R.A.: Minimax algebra and applications. In: Hawkes, P.W. (ed.) Advances in Imaging and Electron Physics, vol. 90, pp. 1–121. Academic Press, San Diego (1994)
Cuninghame-Green, R.: Minimax Algebra. Lecture Notes in Economics and Mathematical Systems, vol. 166. Springer, Berlin (1979)
Drezner, Z.: Continuous Center Problems. In: Eiselt, H.A., Marianov, V. (eds.) Foundations of Location Analysis. International Series in Operations Research and Management Science, vol. 155, pp. 63–78. Springer, New York (2011)
Elzinga, J., Hearn, D.W.: Geometrical solutions for some minimax location problems. Transport. Sci. 6, 379–394 (1972)
Giffler, B.: Scheduling general production systems using schedule algebra. Naval Res. Logist. Quart. 10, 237–255 (1963)
Golan, J.S.: Semirings and Affine Equations Over Them: Theory and Applications. Mathematics and its Applications, vol. 556. Springer, New York (2003)
Gondran, M., Minoux, M.: Graphs, Dioids and Semirings: New Models and Algorithms. Operations Research/Computer Science Interfaces, vol. 41. Springer, New York (2008)
Hansen, P., Peeters, D., Thisse, J.-F.: Location of public services: A selective method-oriented survey. Annals of Public and Cooperative Economics 51, 9–51 (1980)
Hansen, P., Peeters, D., Thisse, J.-F.: Constrained location and the Weber-Rawls problem. In: Hansen, P. (ed.) Annals of Discrete Mathematics (11) Studies on Graphs and Discrete Programming. North-Holland Mathematics Studies, vol. 59, pp. 147–166. North-Holland (1981)
Heidergott, B., Olsder, G.J., van der Woude, J.: Max-plus at Work: Modeling and Analysis of Synchronized Systems. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2006)
Hudec, O., Zimmermann, K.: Biobjective center – balance graph location model. Optimization 45, 107–115 (1999)
Hudec, O., Zimmermann, K.: A service points location problem with Min-Max distance optimality criterion. Acta Univ. Carolin. Math. Phys. 34, 105–112 (1993)
Kolokoltsov, V.N., Maslov, V.P.: Idempotent Analysis and Its Applications, Mathematics and its Applications, vol. 401. Kluwer Academic Publishers, Dordrecht (1997)
Krivulin, N.K.: Solution of generalized linear vector equations in idempotent algebra. Vestnik St. Petersburg Univ. Math. 39, 16–26 (2006)
Krivulin, N.K.: Methods of Idempotent Algebra for Problems in Modeling and Analysis of Complex Systems. Saint Petersburg University Press, St. Petersburg (2009) (in Russian)
Krivulin, N.K.: On solution of a class of linear vector equations in idempotent algebra. Vestnik St. Petersburg University. Applied Mathematics, Informatics, Control Processes 10, 64–77 (2009) (in Russian)
Krivulin, N.: An algebraic approach to multidimensional minimax location problems with Chebyshev distance. WSEAS Trans. Math. 10, 191–200 (2011)
Krivulin, N.: A new algebraic solution to multidimensional minimax location problems with Chebyshev distance. WSEAS Trans. Math. 11, 605–614 (2012)
Krivulin, N.: A multidimensional tropical optimization problem with nonlinear objective function and linear constraints. Optimization (2013)
Krivulin, N., Zimmermann, K.: Direct solutions to tropical optimization problems with nonlinear objective functions and boundary constraints. In: Biolek, D., Walter, H., Utu, I., von Lucken, C. (eds.) Mathematical Methods and Optimization Techniques in Engineering, pp. 86–91. WSEAS Press (2013)
Krivulin, N.: A constrained tropical optimization problem: complete solution and application example. In: Litvinov, G.L., Sergeev, S.N. (eds.) Tropical and Idempotent Mathematics and Applications, Contemp. Math. American Mathematical Society, Providence (2014)
Moradi, E., Bidkhori, M.: Single facility location problem. In: Farahani, R.Z., Hekmatfar, M. (eds.) Facility Location, Contributions to Management Science, pp. 37–68. Physica (2009)
Pandit, S.N.N.: A new matrix calculus. J. SIAM 9, 632–639 (1961)
Romanovskiĭ, I. V.: Asymptotic behavior of dynamic programming processes with a continuous set of states. Soviet Math. Dokl. 5, 1684–1687 (1964)
Sule, D.R.: Logistics of facility location and allocation. Marcel Dekker Ltd., New York (2001)
Tharwat, A., Zimmermann, K.: One class of separable optimization problems: Solution method, application. Optimization 59, 619–625 (2010)
Vorob’ev, N.N.: The extremal matrix algebra. Soviet Math. Dokl. 4, 1220–1223 (1963)
Zimmermann, K.: Optimization problems with unimodal functions in max-separable constraints. Optimization 24, 31–41 (1992)
Zimmermann, U.: Linear and Combinatorial Optimization in Ordered Algebraic Structures. Annals of Discrete Mathematics, vol. 10. Elsevier, Amsterdam (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Krivulin, N. (2014). Complete Solution of a Constrained Tropical Optimization Problem with Application to Location Analysis. In: Höfner, P., Jipsen, P., Kahl, W., Müller, M.E. (eds) Relational and Algebraic Methods in Computer Science. RAMICS 2014. Lecture Notes in Computer Science, vol 8428. Springer, Cham. https://doi.org/10.1007/978-3-319-06251-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-06251-8_22
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06250-1
Online ISBN: 978-3-319-06251-8
eBook Packages: Computer ScienceComputer Science (R0)