SpringerLink
Log in

Lexicographic Equivalence in Mixed Combinatorial Optimization of Linear-Fractional Functions on Arrangements

  • Published:
Cybernetics and Systems Analysis Aims and scope

Abstract

The paper substantiates the method of constructing the lexicographic equivalence to solve mixed combinatorial optimization problems on arrangements with linear-fractional objective function and linear additional constraints. The method involves directed search of equivalence classes obtained by splitting polyhedral set using equivalence relation. The authors propose exact methods as well as an approximate one. The approximate method allows getting the objective function value that differs from the optimum by no more than a predetermined value.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I. V. Sergienko and M. F. Kaspshitskaya, Models and Methods of Computer Solution of Combinatorial Optimization Problems [in Russian], Naukova Dumka, Kyiv (1981).

    MATH  Google Scholar 

  2. M. Z. Zgurovsky and A. A. Pavlov, Decision Making in Network Systems with Limited Resources [in Russian], Naukova Dumka, Kyiv (2010).

    Google Scholar 

  3. A. V. Panishev and D. D. Plechistyi, Models and Methods of Optimization in the Traveling Salesman Problem [in Russian], ZHGTU, Zhytomyr (2006).

    Google Scholar 

  4. I. V. Sergienko, L. F. Hulianytskyi, and S. I. Sirenko, “Classification of applied methods of combinatorial optimization,” Cybern. Syst. Analysis, Vol. 45, No. 5, 732–741 (2009).

    Article  MathSciNet  MATH  Google Scholar 

  5. L. F. Hulyanytskyi and S. I. Sirenko, “ACO-H metaheuristic combinatorial optimization method,” J. Autom. Inform. Sci., Vol. 42, Issue 7, 30–42 (2010).

    Article  Google Scholar 

  6. G. P Donets and L. M Kolechkina, Extremum Problems on Combinatorial Configurations in Ukrainian, RVV PUET, Poltava (2011), URL: http://dspace.puet.edu.ua/handle/123456789/560.

  7. Yu. G. Stoyan and S. V. Yakovlev, Mathematical Models and Optimization Methods of Geometrical Design [in Russian], Naukova Dumka, Kyiv (1986).

    Google Scholar 

  8. Yu. G. Stoyan and O. O. Yemets, Theory and Methods of Euclidean Combinatorial Optimization [in Ukrainian], Inst. Syst. Doslidzhen’ Osvity, Kyiv (1993), URL: http://dspace.puet.edu.ua/handle/123456789/487.

  9. O. O. Emets, O. V. Roskladka, and S. S. Nedobachii, “Irreducible system of constraints for a general polyhedron of arrangements,” Ukr. Math. J., Vol. 55, No. 1, 1–12 (2003).

    Article  MATH  Google Scholar 

  10. O. A. Yemets and T. N. Barbolina, Combinatorial Optimization on Arrangements in Russian, Naukova Dumka, Kyiv (2008), URL: http://dspace.puet.edu.ua/handle/123456789/473.

  11. O. A. Yemets and T. N. Barbolina, “Solution of Euclidean combinatorial optimization problems by the method of construction of lexicographic equivalence,” Cybern. Syst. Analysis, Vol. 40, No. 5, 726–734 (2004).

    Article  MATH  Google Scholar 

  12. T. N. Barbolina, “Solution of mixed combinatorial optimization problems on arrangements by the method of construction of lexicographic equivalence,” Cybern. Syst. Analysis, Vol. 49, No. 6, 922–931 (2013).

    Article  MathSciNet  MATH  Google Scholar 

  13. O. A. Yemets and O. A. Chernenko, Optimization of Linear-Fractional Functions on Arrangements in Russian, Naukova Dumka, Kyiv (2011), URL: http://dspace.puet.edu.ua/handle/123456789/467.

  14. O. A. Yemets, T. N. Barbolina, and O. A. Chernenko, “Solving optimization problems with linear-fractional objective functions and additional constraints on arrangements,” Cybern. Syst. Analysis, Vol. 42, No. 5, 680–685 (2006).

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Poltava University of Economics and Trade, Poltava, Ukraine

    O. O. Iemets

  2. V. G. Korolenko Poltava National Pedagogical University, Poltava, Ukraine

    T. M. Barbolina

Authors
  1. O. O. Iemets
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. T. M. Barbolina
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to O. O. Iemets.

Additional information

Translated from Kibernetika i Sistemnyi Analiz, No. 2, March–April, 2017, pp. 94–106.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Iemets, O.O., Barbolina, T.M. Lexicographic Equivalence in Mixed Combinatorial Optimization of Linear-Fractional Functions on Arrangements. Cybern Syst Anal 53, 244–254 (2017). https://doi.org/10.1007/s10559-017-9924-8

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10559-017-9924-8

Keywords

Search

Navigation