IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2021i1p47-d710212.html
   My bibliography  Save this article

Search Graph Magnification in Rapid Mixing of Markov Chains Associated with the Local Search-Based Metaheuristics

Author

Listed:
  • Ajitha K. B. Shenoy

    (Department of Information and Communication Technology, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal 576104, India)

  • Smitha N. Pai

    (Department of Information and Communication Technology, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal 576104, India)

Abstract

The structural property of the search graph plays an important role in the success of local search-based metaheuristic algorithms. Magnification is one of the structural properties of the search graph. This study builds the relationship between the magnification of a search graph and the mixing time of Markov Chain (MC) induced by the local search-based metaheuristics on that search space. The result shows that the ergodic reversible Markov chain induced by the local search-based metaheuristics is inversely proportional to magnification. This result indicates that it is desirable to use a search space with large magnification for the optimization problem in hand rather than using any search spaces. The performance of local search-based metaheuristics may be good on such search spaces since the mixing time of the underlying Markov chain is inversely proportional to the magnification of search space. Using these relations, this work shows that MC induced by the Metropolis Algorithm (MA) mixes rapidly if the search graph has a large magnification. This indicates that for any combinatorial optimization problem, the Markov chains associated with the MA mix rapidly i.e., in polynomial time if the underlying search graph has large magnification. The usefulness of the obtained results is illustrated using the 0 / 1 -Knapsack Problem, which is a well-studied combinatorial optimization problem in the literature and is NP-Complete. Using the theoretical results obtained, this work shows that Markov Chains (MCs) associated with the local search-based metaheuristics like random walk and MA for 0 / 1 -Knapsack Problem mixes rapidly.

Suggested Citation

  • Ajitha K. B. Shenoy & Smitha N. Pai, 2021. "Search Graph Magnification in Rapid Mixing of Markov Chains Associated with the Local Search-Based Metaheuristics," Mathematics, MDPI, vol. 10(1), pages 1-17, December.
    • Handle: RePEc:gam:jmathe:v:10:y:2021:i:1:p:47-:d:710212
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/1/47/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/1/47/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Dulebenets, Maxim A., 2019. "A Delayed Start Parallel Evolutionary Algorithm for just-in-time truck scheduling at a cross-docking facility," International Journal of Production Economics, Elsevier, vol. 212(C), pages 236-258.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mohammad Amin Amani & Mohammad Mahdi Nasiri, 2023. "A novel cross docking system for distributing the perishable products considering preemption: a machine learning approach," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-32, July.
    2. Bingtao Quan & Sujian Li & Kuo-Jui Wu, 2022. "Optimizing the Vehicle Scheduling Problem for Just-in-Time Delivery Considering Carbon Emissions and Atmospheric Particulate Matter," Sustainability, MDPI, vol. 14(10), pages 1-19, May.
    3. Yunes Almansoub & Ming Zhong & Asif Raza & Muhammad Safdar & Abdelghani Dahou & Mohammed A. A. Al-qaness, 2022. "Exploring the Effects of Transportation Supply on Mixed Land-Use at the Parcel Level," Land, MDPI, vol. 11(6), pages 1-28, May.
    4. Oluwatosin Theophilus & Maxim A. Dulebenets & Junayed Pasha & Olumide F. Abioye & Masoud Kavoosi, 2019. "Truck Scheduling at Cross-Docking Terminals: A Follow-Up State-Of-The-Art Review," Sustainability, MDPI, vol. 11(19), pages 1-23, September.
    5. Hubert Ruta & Tomasz Krakowski & Paweł Lonkwic, 2022. "Optimisation of the Magnetic Circuit of a Measuring Head for Diagnostics of Steel-Polyurethane Load-Carrying Belts Using Numerical Methods," Sustainability, MDPI, vol. 14(5), pages 1-19, February.
    6. Yupeng Zhou & Jinshu Li & Yang Liu & Shuai Lv & Yong Lai & Jianan Wang, 2020. "Improved Memetic Algorithm for Solving the Minimum Weight Vertex Independent Dominating Set," Mathematics, MDPI, vol. 8(7), pages 1-17, July.
    7. Byungjun Ju & Minsu Kim & Ilkyeong Moon, 2021. "Vehicle Routing Problem Considering Reconnaissance and Transportation," Sustainability, MDPI, vol. 13(6), pages 1-19, March.
    8. Cheng-Long Wei & Gai-Ge Wang, 2020. "Hybrid Annealing Krill Herd and Quantum-Behaved Particle Swarm Optimization," Mathematics, MDPI, vol. 8(9), pages 1-23, August.
    9. Tamvada, Srinivas Subramanya & Mansouri, Bahareh & Hassini, Elkafi & Pribytkov, Theodore, 2021. "An integer programming model and directed Steiner-forest based heuristic for routing less-than-truckload freight," International Journal of Production Economics, Elsevier, vol. 232(C).
    10. Alma Rodríguez & Avelina Alejo-Reyes & Erik Cuevas & Francisco Beltran-Carbajal & Julio C. Rosas-Caro, 2020. "An Evolutionary Algorithm-Based PWM Strategy for a Hybrid Power Converter," Mathematics, MDPI, vol. 8(8), pages 1-18, July.
    11. Bo Peng & Yuan Zhang & Yuvraj Gajpal & Xiding Chen, 2019. "A Memetic Algorithm for the Green Vehicle Routing Problem," Sustainability, MDPI, vol. 11(21), pages 1-20, October.
    12. Francesco Russo & Giuseppe Fortugno & Marco Merante & Domenica Savia Pellicanò & Maria Rosaria Trecozzi, 2021. "Updating National Air Passenger Demand from Traffic Counts: The Case of a Secondary Airport in an Underdeveloped Region," Sustainability, MDPI, vol. 13(15), pages 1-16, July.
    13. Mengke Li & Yongkui Shi & Bobin Zhu, 2022. "Research on Multi-Center Mixed Fleet Distribution Path Considering Dynamic Energy Consumption Integrated Reverse Logistics," Sustainability, MDPI, vol. 14(11), pages 1-27, May.
    14. Hua Wang & Hafeezullah Memon & Syed Hamad Hassan Shah & Madjidov Shakhrukh, 2019. "Development of a Quantitative Model for the Analysis of the Functioning of Integrated Textile Supply Chains," Mathematics, MDPI, vol. 7(10), pages 1-14, October.
    15. Imen Hamdi & Imen Boujneh, 2022. "Particle swarm optimization based-algorithms to solve the two-machine cross-docking flow shop problem: just in time scheduling," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 947-969, September.
    16. Masoud Kavoosi & Maxim A. Dulebenets & Junayed Pasha & Olumide F. Abioye & Ren Moses & John Sobanjo & Eren E. Ozguven, 2020. "Development of Algorithms for Effective Resource Allocation among Highway–Rail Grade Crossings: A Case Study for the State of Florida," Energies, MDPI, vol. 13(6), pages 1-28, March.
    17. Antonio Martínez Raya & Víctor M. González-Sánchez, 2021. "Efficiency and Sustainability of Regional Aviation on Insular Territories of the European Union: A Case Study of Public Service Obligations on Scheduled Air Routes among the Balearic Islands," Sustainability, MDPI, vol. 13(7), pages 1-31, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2021:i:1:p:47-:d:710212. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.