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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    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. 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. 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.

    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. 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.
    6. 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).
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Zhang, Dengjun & Xie, Yifan, 2022. "Customer environmental concerns and profit margin: Evidence from manufacturing firms," Journal of Economics and Business, Elsevier, vol. 120(C).
    12. 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.
    13. Schauer, Joachim, 2016. "Asymptotic behavior of the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 255(2), pages 357-363.
    14. 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.
    15. Esswein, Carl & Billaut, Jean-Charles & Strusevich, Vitaly A., 2005. "Two-machine shop scheduling: Compromise between flexibility and makespan value," European Journal of Operational Research, Elsevier, vol. 167(3), pages 796-809, December.
    16. Maxence Delorme & Manuel Iori, 2020. "Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 101-119, January.
    17. Yuji Nakagawa & Ross J. W. James & César Rego & Chanaka Edirisinghe, 2014. "Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models," Management Science, INFORMS, vol. 60(3), pages 695-707, March.
    18. Caizhi Sun & Ling Liu & Yanting Tang, 2018. "Measuring the Inclusive Growth of China’s Coastal Regions," Sustainability, MDPI, vol. 10(8), pages 1-15, August.
    19. Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
    20. Murat Gunduz & Ayman Fahmi Naser, 2017. "Cost Based Value Stream Mapping as a Sustainable Construction Tool for Underground Pipeline Construction Projects," Sustainability, MDPI, vol. 9(12), pages 1-20, November.

    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.