Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Quadratic Optimization Models and Convex Extensions on Permutation Matrix Set

  • Conference paper
  • First Online:
Advances in Intelligent Systems and Computing IV (CSIT 2019)

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 1080))

Included in the following conference series:

Abstract

A new approach to the construction of lower bounds of quadratic function the permutation matrix set, based on the utilization of functional representations and convex extensions, is offered. Several quadratic functional representations of the are formed. A family of one-parametric convex quadratic extensions of a quadratic function from the set onto the Euclidean space is formed. The results can be applied in approximate and exact methods of quadratic optimization on the permutation matrix set.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Armbruster, M., Fügenschuh, M., Helmberg, C., Martin, A.: A comparative study of linear and semidefinite branch-and-cut methods for solving the minimum graph bisection problem. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) Integer Programming and Combinatorial Optimization, pp. 112–124. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68891-4_8

    Chapter  MATH  Google Scholar 

  2. Bachem, A., Euler, R.: Recent trends in combinatorial optimization. OR Spektrum 6, 1–21 (1984). https://doi.org/10.1007/BF01721246

    Article  MATH  Google Scholar 

  3. Berge, C.: Principes de combinatoire. Dunod, Paris (1968)

    MATH  Google Scholar 

  4. Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999)

    MATH  Google Scholar 

  5. Billionnet, A., Elloumi, S., Plateau, M.-C.: Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: the QCR method. Discrete Appl. Math. 157, 1185–1197 (2009). https://doi.org/10.1016/j.dam.2007.12.007

    Article  MathSciNet  MATH  Google Scholar 

  6. Billionnet, A., Jarray, F., Tlig, G., Zagrouba, E.: Reconstructing convex matrices by integer programming approaches. J. Math. Model. Algor. 12, 329–343 (2012). https://doi.org/10.1007/s10852-012-9193-5

    Article  MathSciNet  MATH  Google Scholar 

  7. Brualdi, R.A.: Combinatorial Matrix Classes. Cambridge University Press, Cambridge (2006)

    Book  Google Scholar 

  8. Burkard, R.E.: Quadratic assignment problems. In: Pardalos, P.M., Du, D.-Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 2741–2814. Springer, New York (2013). https://doi.org/10.1007/978-1-4419-7997-1_22

    Chapter  Google Scholar 

  9. Burkard, R.E., Çela, E.: Linear assignment problems and extensions. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp. 75–149. Springer, New York (1999). https://doi.org/10.1007/978-1-4757-3023-4_2

    Chapter  Google Scholar 

  10. Cela, E.: The Quadratic Assignment Problem: Theory and Algorithms. Springer, New York (2010)

    MATH  Google Scholar 

  11. Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998)

    MATH  Google Scholar 

  12. Crama, Y., Spieksma, F.C.R.: Scheduling jobs of equal length: complexity, facets and computational results. In: Balas, E., Clausen, J. (eds.) Integer Programming and Combinatorial Optimization, pp. 277–291. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-59408-6_58

    Chapter  Google Scholar 

  13. Colbourn, C.J., Dinitz, J.H. (eds.): Handbook of Combinatorial Designs. Chapman and Hall, CRC Press, New York (2006)

    Google Scholar 

  14. Dahl, J.: Convex optimization in signal processing and communications (2003)

    Google Scholar 

  15. Farzad, B., Pichugina, O., Koliechkina, L.: Multi-layer community detection. In: 2018 International Conference on Control, Artificial Intelligence, Robotics Optimization (ICCAIRO), pp. 133–140 (2018). https://doi.org/10.1109/ICCAIRO.2018.00030

  16. Floudas, C.A., Pardalos, P.M., Adjiman, C.S., Esposito, W.R., Gümüş, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Quadratic programming problems. In: Handbook of Test Problems in Local and Global Optimization, pp. 5–19. Springer, New York (1999)

    Google Scholar 

  17. Stoyan, Yu.G., Sokolovskii, V.Z., Yakovlev, S.V.: Method of balancing rotating discretely distributed masses. Energomashinostroenie 2, 4–5 (1982)

    Google Scholar 

  18. Hulianytskyi, L., Riasna, I.: Formalization and classification of combinatorial optimization problems. In: Optimization Methods and Applications, pp. 239–250. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68640-0_11

  19. Kabadi, S.N.: Polynomially solvable cases of the TSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variations, pp. 489–583. Springer, New York (2007). https://doi.org/10.1007/0-306-48213-4_11

    Chapter  Google Scholar 

  20. Kaibel, V.: Polyhedral methods for the QAP. In: Pardalos, P.M., Pitsoulis, L.S. (eds.) Nonlinear Assignment Problems, pp. 109–141. Springer, New York (2000). https://doi.org/10.1007/978-1-4757-3155-2_6

    Chapter  Google Scholar 

  21. Kammerdiner, A., Gevezes, T., Pasiliao, E., Pitsoulis, L., Pardalos, P.M.: Quadratic assignment problem. In: Gass, S.I., Fu, M.C. (eds.) Encyclopedia of Operations Research and Management Science, pp. 1193–1207. Springer, New York (2013). https://doi.org/10.1007/978-1-4419-1153-7_1152

    Chapter  Google Scholar 

  22. Koliechkina, L.M., Dvirna, O.A.: Solving extremum problems with linear fractional objective functions on the combinatorial configuration of permutations under multicriteriality. Cybern. Syst. Anal. 53, 590–599 (2017). https://doi.org/10.1007/s10559-017-9961-3

    Article  MATH  Google Scholar 

  23. Koliechkina, L., Pichugina, O.: A horizontal method of localizing values of a linear function in permutation-based optimization. In: Le Thi, H.A., Le, H.M., Pham Dinh, T. (eds.) Optimization of Complex Systems: Theory, Models, Algorithms and Applications, pp. 355–364. Springer, Cham (2019)

    Google Scholar 

  24. Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, Heidelberg (2012)

    Book  Google Scholar 

  25. Krislock, N., Malick, J., Roupin, F.: Computational results of a semidefinite branch-and-bound algorithm for k-cluster. Comput. Oper. Res. 66, 153–159 (2016). https://doi.org/10.1016/j.cor.2015.07.008

    Article  MathSciNet  MATH  Google Scholar 

  26. Lawler, E.L.: The quadratic assignment problem. Manage. Sci. 9, 586–599 (1963)

    Article  MathSciNet  Google Scholar 

  27. Mashtalir, V.P., Yakovlev, S.V.: Point-set methods of clusterization of standard information. Cybern. Syst. Anal. 37(3), 295–307 (2001). https://doi.org/10.1023/A:1011985908177

    Article  MATH  Google Scholar 

  28. Miller, A.J., Nemhauser, G.L., Savelsbergh, M.W.P.: Facets, algorithms, and polyhedral characterizations for a multi-item production planning model with setup times. In: Aardal, K., Gerards, B. (eds.) Integer Programming and Combinatorial Optimization, pp. 318–332. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45535-3_25

    Chapter  MATH  Google Scholar 

  29. Nakamura, D., Tamura, A.: The generalized stable set problem for claw-free bidirected graphs. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) Integer Programming and Combinatorial Optimization, pp. 69–83. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-69346-7_6

    Chapter  Google Scholar 

  30. Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Mineola (2013)

    MATH  Google Scholar 

  31. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2002)

    MATH  Google Scholar 

  32. Pardalos, P.M., Wolkowicz, H.: Quadratic Assignment and Related Problems: DIMACS Workshop, 20–21 May 1993. American Mathematical Soc. (1994)

    Google Scholar 

  33. Pichugina, O.: Placement problems in chip design: modeling and optimization. In: 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), pp. 465–473 (2017). https://doi.org/10.1109/INFOCOMMST.2017.8246440

  34. Pichugina, O., Farzad, B.: A human communication network model. In: CEUR Workshop Proceedings, KNU, Kyiv, pp. 33–40 (2016)

    Google Scholar 

  35. Pichugina, O., Kartashov, O.: Signed permutation polytope packing in VLSI design. In: 2019 IEEE 15th International Conference on the Experience of Designing and Application of CAD Systems (CADSM) Conference Proceedings, Lviv, pp. 4/50–4/55 (2019). https://doi.org/10.1109/CADSM.2019.8779353

  36. Pichugina, O.S., Yakovlev, S.V.: Continuous representations and functional extensions in combinatorial optimization. Cybern. Syst. Anal. 52(6), 921–930 (2016). https://doi.org/10.1007/s10559-016-9894-2

    Article  MathSciNet  MATH  Google Scholar 

  37. Pichugina, O.S., Yakovlev, S.V.: Functional and analytic representations of the general permutation. Eastern-Eur. J. Enterp. Technol. 79, 27–38 (2016). https://doi.org/10.15587/1729-4061.2016.58550

    Article  Google Scholar 

  38. Pichugina, O., Yakovlev, S.: Optimization on polyhedral-spherical sets: theory and applications. In: 2017 IEEE 1st Ukraine Conference on Electrical and Computer Engineering, UKRCON 2017 - Proceedings, KPI, Kiev, pp. 1167–1174 (2017). https://doi.org/10.1109/UKRCON.2017.8100436

  39. Pichugina, O., Yakovlev, S.: Euclidean combinatorial configurations: continuous representations and convex extensions. In: Lytvynenko, V., Babichev, S., Wójcik, W., Vynokurova, O., Vyshemyrskaya, S., Radetskaya, S. (eds.) Lecture Notes in Computational Intelligence and Decision Making, pp. 65–80. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26474-1_5

    Chapter  Google Scholar 

  40. Pitsoulis, L., Pardalos, P.M.: Quadratic assignment problem. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 2075–2107. Springer, New York (2001). https://doi.org/10.1007/0-306-48332-7_405

    Chapter  Google Scholar 

  41. Semenova, N.V., Kolechkina, L.N., Nagornaya, A.N.: One approach to solving vector problems with fractionally linear functions of the criteria on the combinatorial set of arrangements. J. Autom. Inf. Sci. 42, 67–80 (2010). https://doi.org/10.1615/JAutomatInfScien.v42.i2.50

    Article  Google Scholar 

  42. Sergienko, I.V., Hulianytskyi, L.F., Sirenko, S.I.: Classification of applied methods of combinatorial optimization. Cybern. Syst. Anal. 45, 732 (2009). https://doi.org/10.1007/s10559-009-9134-0

    Article  MathSciNet  MATH  Google Scholar 

  43. Sergienko, I.V., Shylo, V.P.: Modern approaches to solving complex discrete optimization problems. J. Autom. Inf. Sci. 48, 15–24 (2016). https://doi.org/10.1615/JAutomatInfScien.v48.i1.30

    Article  Google Scholar 

  44. Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dordrecht (1999)

    Book  Google Scholar 

  45. Shor, N.Z., Stetsyuk, P.I.: Lagrangian bounds in multiextremal polynomial and discrete optimization problems. J. Global Optim. 23, 1–41 (2002). https://doi.org/10.1023/A:1014004625997

    Article  MathSciNet  MATH  Google Scholar 

  46. Stetsyuk, P.I.: Problem statements for k-node shortest path and k-node shortest cycle in a complete graph. Cybern. Syst. Anal. 52, 71–75 (2016). https://doi.org/10.1007/s10559-016-9801-x

    Article  MathSciNet  MATH  Google Scholar 

  47. Yakovlev, S.V.: Bounds on the minimum of convex functions on Euclidean combinatorial sets. Cybernetics 25, 385–391 (1989). https://doi.org/10.1007/BF01069996

    Article  MathSciNet  MATH  Google Scholar 

  48. Yakovlev, S.V.: The theory of convex continuations of functions on vertices of convex polyhedra. Comp. Math. Math. Phys. 34, 1112–1119 (1994)

    MathSciNet  Google Scholar 

  49. Yakovlev, S.V., Grebennik, I.V.: Localization of solutions of some problems of nonlinear integer optimization. Cybern. Syst. Anal. 29, 727–734 (1993). https://doi.org/10.1007/BF01125802

    Article  MATH  Google Scholar 

  50. Yakovlev, S., Pichugina, O.: On constrained optimization of polynomials on permutation set. In: Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (CMIS-2019), CEUR Vol-2353 urn:nbn:de:0074-2353-0, Zaporizhzhia, Ukraine, pp. 570–580 (2019)

    Google Scholar 

  51. Yakovlev, S.V., Valuiskaya, O.A.: Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints. Ukr. Math. J. 53, 1535–1545 (2001). https://doi.org/10.1023/A:1014374926840

    Article  Google Scholar 

  52. Yakovlev, S., Pichugina, O., Yarovaya, O.: On optimization problems on the polyhedral-spherical configurations with their properties. In: 2018 IEEE First International Conference on System Analysis Intelligent Computing (SAIC), pp. 94–100 (2018). https://doi.org/10.1109/SAIC.2018.8516801

  53. Yakovlev, S., Pichugina, O., Yarovaya, O.: Polyhedral-spherical configurations in discrete optimization problems. J. Autom. Inf. Sci. 51, 26–40 (2019). https://doi.org/10.1615/JAutomatInfScien.v51.i1.30

    Article  Google Scholar 

  54. Yemelichev, V.A., Kovalev, M.M., Kravtsov, M.K.: Polytopes, Graphs and Optimisation. Cambridge University Press, Cambridge (1984)

    Google Scholar 

  55. Xia, Y., Gharibi, W.: On improving convex quadratic programming relaxation for the quadratic assignment problem. J. Comb. Optim. 30, 647–667 (2013)

    Article  MathSciNet  Google Scholar 

  56. Zgurovsky, M.Z., Pavlov, A.A.: Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. Springer, Cham (2019)

    Book  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National Aerospace University “Kharkiv Aviation Institute”, 17 Chkalova Street, Kharkiv, 61070, Ukraine

    Oksana Pichugina & Sergiy Yakovlev

Authors
  1. Oksana Pichugina
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sergiy Yakovlev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Oksana Pichugina .

Editor information

Editors and Affiliations

  1. Department of Artificial Intelligence, Lviv Polytechnic National University, Lviv, Ukraine

    Natalya Shakhovska

  2. Institute of Computer Science and Information Technologies, Lviv Polytechnic National University, Lviv, Ukraine

    Mykola O. Medykovskyy

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Pichugina, O., Yakovlev, S. (2020). Quadratic Optimization Models and Convex Extensions on Permutation Matrix Set. In: Shakhovska, N., Medykovskyy, M.O. (eds) Advances in Intelligent Systems and Computing IV. CSIT 2019. Advances in Intelligent Systems and Computing, vol 1080. Springer, Cham. https://doi.org/10.1007/978-3-030-33695-0_17

Download citation

Publish with us

Policies and ethics

Search

Navigation