IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v9y2017i2p236-d89803.html
   My bibliography  Save this article

A New Optimization Model for the Sustainable Development: Quadratic Knapsack Problem with Conflict Graphs

Author

Listed:
  • Xiaochuan Shi

    (International School of Software, Wuhan University, 37 Luoyu Road, Wuhan 430079, China)

  • Lei Wu

    (Wenlan School of Business, Zhongnan University of Economics and Law, 182 Nanhu Avenue, Wuhan 430073, China)

  • Xiaoliang Meng

    (International School of Software, Wuhan University, 37 Luoyu Road, Wuhan 430079, China)

Abstract

New information technology constantly improves the efficiency of social networks. Using optimization and decision models in the context of large data sets attracts extensive attention. This paper investigates a novel mathematical model for designing and optimizing environmental economic policies in a protection zone. The proposed model is referred to as the quadratic knapsack problem with conflict graphs, which is a new variant of the knapsack problem family. Due to the investigated problem processing a high complex structure, in order to solve efficiently the problem, we develop a metaheuristic which is based on the large neighborhood search. The proposed method embeds a construction procedure into a sophistical neighborhood search. For more details, the construction procedure takes charge of finding a starting solution while the investigated neighborhood search is used to generate and explore the solution space issuing from the provided starting solution. In order to highlight our theoretical model, we evaluate the model on a set of complex benchmark data sets. The obtained results demonstrate that the investigated algorithm is competitive and efficient compared to legacy algorithms.

Suggested Citation

  • Xiaochuan Shi & Lei Wu & Xiaoliang Meng, 2017. "A New Optimization Model for the Sustainable Development: Quadratic Knapsack Problem with Conflict Graphs," Sustainability, MDPI, vol. 9(2), pages 1-10, February.
    • Handle: RePEc:gam:jsusta:v:9:y:2017:i:2:p:236-:d:89803
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/9/2/236/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2071-1050/9/2/236/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Sang-Oh Shim & KyungBae Park, 2016. "Technology for Production Scheduling of Jobs for Open Innovation and Sustainability with Fixed Processing Property on Parallel Machines," Sustainability, MDPI, vol. 8(9), pages 1-10, September.
    2. BangRae Lee & DongKyu Won & Jun-Hwan Park & LeeNam Kwon & Young-Ho Moon & Han-Joon Kim, 2016. "Patent-Enhancing Strategies by Industry in Korea Using a Data Envelopment Analysis," Sustainability, MDPI, vol. 8(9), pages 1-17, September.
    3. Dongoun Lee & Seungho Kim & Sangyong Kim, 2016. "Development of Hybrid Model for Estimating Construction Waste for Multifamily Residential Buildings Using Artificial Neural Networks and Ant Colony Optimization," Sustainability, MDPI, vol. 8(9), pages 1-14, September.
    4. Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
    5. Jianglong Li & Boqiang Lin, 2016. "Green Economy Performance and Green Productivity Growth in China’s Cities: Measures and Policy Implication," Sustainability, MDPI, vol. 8(9), pages 1-21, September.
    6. Billionnet, Alain & Soutif, Eric, 2004. "An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 157(3), pages 565-575, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Li, Mingjie & Hao, Jin-Kao & Wu, Qinghua, 2024. "A flow based formulation and a reinforcement learning based strategic oscillation for cross-dock door assignment," European Journal of Operational Research, Elsevier, vol. 312(2), pages 473-492.
    2. Víctor Yepes & José V. Martí & José García, 2020. "Black Hole Algorithm for Sustainable Design of Counterfort Retaining Walls," Sustainability, MDPI, vol. 12(7), pages 1-18, April.
    3. Isma Dahmani & Mhand Hifi, 2021. "A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs," Annals of Operations Research, Springer, vol. 298(1), pages 125-147, March.

    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. JinHyo Joseph Yun & Tan Yigitcanlar, 2017. "Open Innovation in Value Chain for Sustainability of Firms," Sustainability, MDPI, vol. 9(5), pages 1-8, May.
    2. Isma Dahmani & Mhand Hifi, 2021. "A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs," Annals of Operations Research, Springer, vol. 298(1), pages 125-147, March.
    3. M Büther, 2010. "Reducing the elastic generalized assignment problem to the standard generalized assignment problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1582-1595, November.
    4. Yi Yang & Jie Li & Guobin Zhu & Qiangqiang Yuan, 2019. "Spatio–Temporal Relationship and Evolvement of Socioeconomic Factors and PM 2.5 in China During 1998–2016," IJERPH, MDPI, vol. 16(7), pages 1-24, March.
    5. Yu, Chenyang & Tan, Yuanfang & Zhou, Yu & Zang, Chuanxiang & Tu, Chenglin, 2022. "Can functional urban specialization improve industrial energy efficiency? Empirical evidence from China," Energy, Elsevier, vol. 261(PA).
    6. Joanna Godlewska & Edyta Sidorczuk-Pietraszko, 2019. "Taxonomic Assessment of Transition to the Green Economy in Polish Regions," Sustainability, MDPI, vol. 11(18), pages 1-25, September.
    7. Sune Lauth Gadegaard & Andreas Klose & Lars Relund Nielsen, 2018. "An improved cut-and-solve algorithm for the single-source capacitated facility location problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 1-27, March.
    8. Shang, Hua & Jiang, Li & Pan, Xianyou & Pan, Xiongfeng, 2022. "Green technology innovation spillover effect and urban eco-efficiency convergence: Evidence from Chinese cities," Energy Economics, Elsevier, vol. 114(C).
    9. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Post-Print halshs-03322716, HAL.
    10. Shuichiro Kajima & Yuta Uchiyama & Ryo Kohsaka, 2020. "Intellectual Property Strategies for Timber and Forest Products: The Case of Regional Collective Trademark Applications by Japanese Forestry Associations," Sustainability, MDPI, vol. 12(5), pages 1-16, March.
    11. Akinc, Umit, 2006. "Approximate and exact algorithms for the fixed-charge knapsack problem," European Journal of Operational Research, Elsevier, vol. 170(2), pages 363-375, April.
    12. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2019. "Interdiction Games and Monotonicity, with Application to Knapsack Problems," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 390-410, April.
    13. Fabio Furini & Emiliano Traversi, 2019. "Theoretical and computational study of several linearisation techniques for binary quadratic problems," Annals of Operations Research, Springer, vol. 279(1), pages 387-411, August.
    14. M Hifi & M Michrafy, 2006. "A reactive local search-based algorithm for the disjunctively constrained knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(6), pages 718-726, June.
    15. Liu, Yipeng & Koehler, Gary J., 2010. "Using modifications to Grover's Search algorithm for quantum global optimization," European Journal of Operational Research, Elsevier, vol. 207(2), pages 620-632, December.
    16. Sbihi, Abdelkader, 2010. "A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 339-346, April.
    17. Zhang, Dengjun & Xie, Yifan, 2022. "Customer environmental concerns and profit margin: Evidence from manufacturing firms," Journal of Economics and Business, Elsevier, vol. 120(C).
    18. Büther, Marcel, 2007. "Reducing the elastic generalized assignment problem to the standard generalized assignment problem," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 632, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    19. Schauer, Joachim, 2016. "Asymptotic behavior of the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 255(2), pages 357-363.
    20. Büther, Marcel & Briskorn, Dirk, 2007. "Reducing the 0-1 knapsack problem with a single continuous variable to the standard 0-1 knapsack problem," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 629, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    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:jsusta:v:9:y:2017:i:2:p:236-:d:89803. 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.