2022, issue 4, p. 15-32

Received 19.11.2022; Revised 15.12.2022; Accepted 20.12.2022

Published 29.12.2022; First Online 28.02.2023

https://doi.org/10.34229/2707-451X.22.4.2

Previous  |  FULL TEXT  |  Next

 

UDC 519.168

On the Use of Gray Codes for Solving 0-1 Combinatorial Problems of Optimization in Environmental and Economic Systems

Oleksandr Trofymchuk 1 ORCID ID favicon Big,   Volodymyr Vasyanin 1 * ORCID ID favicon Big,   Volodymyr Sokolov 2 ORCID ID favicon Big,   Arkadii Chikrii 3 ORCID ID favicon Big,   Liudmyla Ushakova 1 ORCID ID favicon Big

1 Institute of Telecommunications and Global Information Space of the NAS of Ukraine, Kyiv

2 Borys Grinchenko Kyiv University, Ukraine

3 V.M.Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. The application of binary-reflected (mirror, reflexive) Gray codes for solving combinatorial problems with pseudo-Boolean functions (polynomials from Boolean variables) is considered. A recursive Ehrlich algorithm is given for generating a sequence of lines n-bit Gray codes, in which each subsequent line differs from the previous one by only one digit (bit). As an example of the effectiveness of the use of these codes, the solution of two combinatorial problems with Boolean variables with a complete enumeration of solutions is considered, and it is shown how these codes can be used to efficiently calculate the values of the objective function and constraints. The results of an experimental study are presented, which show that Gray codes can be practically applied in branching schemes, for example, in the branch and bound method, when the number of variables in the branching nodes of the decision algorithm does not exceed 35.

Purpose. The purpose of the article is to show the developers of algorithms and programs how to apply Gray codes in various branching schemes of the decision algorithm, for example, in the branch and bound method, when the number of binary (Boolean) variables at the nodes of the  tree is small (less than 35).

The technique. The research methodology is based on a computational experiment for solving the 0-1 knapsack problem with the proposed algorithm of exhaustive search the solution with partial and full recalculation of the values of objective function and constraint of the problem. During the experiment, the accuracy of solving the problem by a “greedy” heuristic algorithm with time complexity O(n2) was also checked.

Results. As a result of the experiment, it was found that the algorithm with a partial recalculation of the objective function and restrictions can be used for practical calculations in branching schemes, when the number of variables in the nodes of the branching tree does not exceed 35. The algorithm with partial recalculation is faster than the algorithm with full recalculation on average by 7 times. The heuristic "greedy" algorithm can be applied in practice to solve the 0-1 problem of a knapsack of large dimension (more than 10,000 items), when need to obtain an approximate value of the objective function at the limited computing resources.

Scientific novelty and practical significance. The novelty of the work lies in the proposed approach to solving combinatorial optimization problems with pseudo-Boolean functions using Gray codes. The efficiency of the proposed algorithm with a partial recalculation of the values of the objective function and constraints is shown, and its can be applied in practice in various branching schemes of the decision algorithm.

 

Keywords: Gray codes, combinatorial optimization problems, problem solving time.

 

Cite as: Trofymchuk O., Vasyanin V., Sokolov V., Chikrii A., Ushakova L. On the Use of Gray Codes for Solving 0-1 Combinatorial Problems of Optimization in Environmental and Economic Systems. Cybernetics and Computer Technologies. 2022. 4. P. 15–32. https://doi.org/10.34229/2707-451X.22.4.2

 

References

           1.     Martello S., Toth P. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990.

           2.     Drezner Z. Facility Location. A Survey of Applications and Methods. Springer, 1995.

           3.     Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization. John Wiley & Sons, Inc., 1999.

           4.     Schrijver. Combinatorial optimization. Polyhedra and efficiency. Berlin: Springer, 2003.

           5.     Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Springer-Verlag Berlin Heidelberg, 2004. https://doi.org/10.1007/978-3-540-24777-7

           6.     Korte B., Vygen J. Combinatorial Optimization. Theory and Algorithms. Springer, 2005.

           7.     Hifi M., Michrafy M., Sbihi A. Heuristic algorithms for the multiple-choice multidimensional knapsack problem. J. of Oper. Res. Soc. 2004. 55 (12). P. 1323–1332. https://doi.org/10.1057/palgrave.jors.2601796

           8.     Akbar M.M., Rahman M.S., Kakobad M., Manning E.G., Shoja G.C. Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls. Comp. and Oper. Res. 2006. 33 (5). P. 1259–1273. https://doi.org/10.1016/j.cor.2004.09.016

           9.     Shahriar Z., Akbar M.M., Rahman M.S., Newton M. M. A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem. The J. of Supercomputing. 2008. 43 (3). P. 257–280. https://doi.org/10.1007/s11227-007-0144-2

       10.     Lazarev A.A., Werner F. A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems. Computers & Mathematics with Applications. 2009. 58 (4). P. 619–631. https://doi.org/10.1016/j.camwa.2009.06.008

       11.     Leblet H.J., Simon G. Hard multidimensional multiple choice knapsack problems: an empirical study. Comp. and Oper. Res. 2010. 37 (1). P. 172–181. https://doi.org/10.1016/j.cor.2009.04.006

       12.     Posypkin M.A., Sin S.T.T. Comparative analysis of the efficiency of various dynamic programming algorithms for the knapsack problem. Computer Science. 2016 IEEE NW Russia Young Researchers in Electrical and Electronic Engineering Conference (EIConRusNW). 2016. https://doi.org/10.1109/EIConRusNW.2016.7448182

       13.     Gary M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co. New York, NY, USA, 1979.

       14.     Hammer P.L., Rudeanu S. Boolean Methods in Operations Research and Related Areas. Berlin, Springer-Verlag; New York, Heidelberg, 1968. https://doi.org/10.1007/978-3-642-85823-9

       15.     Beresnev V.L., Ageev A.A. Minimization Algorithms for Some Classes of Polynomials in Boolean Variables. Modeli i metody optimizatsii. 1988. No. 10. P. 5–17. (in Russian)

       16.     Boros E., Hammer P.L. Pseudo-Boolean Optimization. Discrete Applied Mathematics. 2002. 123 (1–3). P. 155–225. https://doi.org/10.1016/S0166-218X(01)00341-9

       17.     Crama Y., Hammer P.L. Boolean Functions: Theory, Algorithms, and Applications. New York, Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511852008

       18.     Vasyanin V.A., Ushakova L.P. Gray codes in combinatorial optimization problems. Matematicheskoye modelirovaniye v ekonomike. 2019. No. 1–2. P. 63–69. (in Russian).

       19.     Trofymchuk O.M., Vasyanin V.A. Choosing the Capacity of Arcs with Constraint on Flow Delay Time. Cybernetics and Systems Analysis. 2019. 55 (4). P. 561–569. https://doi.org/10.1007/s10559-019-00165-0

       20.     Trofymchuk O.M., Vasyanin V.A. Simulation of Packing, Distribution and Routing of Small-Size Discrete Flows in a Multicommodity Network. Journal of Automation and Information Sciences. 2015. 47 (7). P. 15–30. https://doi.org/10.1615/JAutomatInfScien.v47.i7.30

       21.     Vasyanin V.A. Problem of Distribution and Routing of Transport Blocks with Mixed Attachments and Its Decomposition. Journal of Automation and Information Sciences. 2015. 47 (2). P. 56–69. https://doi.org/10.1615/JAutomatInfScien.v47.i2.60

       22.     Vasyanin V.A., Trofymchuk O.M., Ushakova L.P. Economic-mathematical models of the problem of distribution of flows in a multicommodity communication network. Matematicheskoye modelirovaniye v ekonomike. 2016. No. 2. P. 5–21. (in Russian)

       23.     Gray F. Pulse code communication. U.S. Patent 2632058, March 17, 1953.

       24.     Gardner M. Mathematical Puzzles and Entertainment: 2nd ed., corrected and supplemented / Translation from English. Moscow: "Peace", 1999. (in Russian)

       25.     Knuth E. The Art of Computer Programming. Volume 4A / Combinatorial Algorithms. Part 1. Addison Wesley Longman, Inc., 2011.

       26.     Bitner J.R., Ehrlich G., Reingold E.M. Efficient Generation of the Binary Reflected Gray Code and its Applications. Comm. ACM. 1976. No. 19. P. 517–521. https://doi.org/10.1145/360336.360343

       27.     Kuzurin N.N., Fomin S.A. Effective algorithms and computing complexity. M.: MPTI, 2008. (in Russian)

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT  |  Next

 

 

 

© Website and Design. 2019-2024,

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine,

National Academy of Sciences of Ukraine.