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

Xiaochuan Shi, Lei Wu, Xiaoliang MengSustainability 2017 · DOI

TL;DR

This paper introduces a novel optimization model, the Quadratic Knapsack Problem with Conflict Graphs (QKPCG), designed for optimizing environmental economic policies in protection zones. To tackle the complexity of this problem, they develop a Large Neighborhood Search (LNS) metaheuristic that efficiently finds high-quality solutions, outperforming a standard integer programming solver.

What Problem Does This Paper Address?

Governments worldwide are increasingly implementing policies for environmental protection zones to balance economic development with ecological safety. Designing and optimizing these policies, especially with the influx of data from stakeholders and public input, presents a significant challenge. Traditional optimization models struggle with the complex interdependencies and constraints inherent in such real-world scenarios. This paper addresses this gap by proposing a new mathematical model, the Quadratic Knapsack Problem with Conflict Graphs (QKPCG), which captures these complexities. QKPCG is a variant of the knapsack problem family, incorporating quadratic profit terms (representing synergistic benefits of item combinations) and conflict graphs (representing incompatible items that cannot be selected together). This model is particularly relevant for optimizing development planning within limited natural resources while ensuring the stability of natural ecosystems.

Methods

The authors tackle the NP-hard QKPCG by developing a metaheuristic based on Large Neighborhood Search (LNS). Their approach consists of two main phases:

  1. Starting Solution Procedure (2PH): This phase first simplifies the QKPCG to a Knapsack Problem with Conflict Graphs (KPCG) by ignoring the quadratic profit terms. It then solves this simplified problem by first finding a maximum weight independent set (ILPWIS) and then using this set to solve a binary knapsack problem (ILPK). This yields a feasible, though not necessarily optimal, solution for the original QKPCG.
  2. Neighborhood Search-Based Metaheuristic (NSBM): This phase refines the solution obtained from 2PH. It employs a local search mechanism that iteratively builds and explores neighborhoods of the current solution. A key aspect is the use of a random building strategy (Algorithm 3) that randomly removes items to create subproblems, allowing the search to escape local optima. The overall NSBM (Algorithm 4) iteratively applies the starting solution procedure and the local search to explore the solution space and find high-quality solutions within a given runtime limit.

Datasets

The paper evaluates their proposed NSBM algorithm on a set of newly generated benchmark instances. These instances, referred to as 1qkpcg–9qkpcg, are designed to mimic the structure of real-world problems and are generated by adapting techniques used in prior work for quadratic terms and disjunctive constraints. The dataset comprises 45 instances with varying numbers of items (100, 150, 200) and densities (2%, 4%, 8%).

Key Insights and Ideas

  • Modeling Real-World Conflicts: The QKPCG model effectively captures the nuanced relationships in policy design, where selecting certain combinations of "items" (e.g., investments or resource uses) can yield synergistic benefits (quadratic profit) but also create conflicts or resource limitations (conflict graphs).
  • LNS for Complex Optimization: The paper demonstrates that a Large Neighborhood Search approach, particularly with a random building strategy, is effective for navigating the complex solution space of the QKPCG, allowing it to escape local optima that might trap simpler local search methods.
  • Efficiency Beyond Exact Solvers: The results highlight that while exact solvers like GLPK can find optimal solutions, their computational cost is prohibitive for large instances. The proposed metaheuristic offers a practical trade-off, delivering high-quality solutions within significantly shorter runtimes.

Key Results

The NSBM algorithm was tested against the GLPK solver on the generated benchmark instances. The results show that:

  • NSBM consistently achieved better or comparable objective values to GLPK, especially when considering the time limits imposed on NSBM.
  • For a runtime limit of 50 seconds, NSBM improved upon GLPK's best solutions in 44 out of 45 instances.
  • As the time limit increased (100s and 200s), NSBM's performance became even more robust, dominating GLPK on all cases for the longer time limits.
  • The computational effort required by NSBM was significantly less than that of GLPK, demonstrating its efficiency for practical applications.

Limitations and Future Work

  • Limitations: The paper acknowledges that while their metaheuristic provides high-quality solutions, it does not guarantee optimality. The performance of NSBM is also dependent on parameter tuning (β, r, γ), which controls the exploration of solution spaces.
  • Future Work: The authors suggest that further research could explore more sophisticated neighborhood structures or hybrid approaches to potentially improve solution quality or further reduce computation time. The applicability of the QKPCG model to other domains beyond environmental policy optimization could also be investigated.

Summary updated

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.
BibTeX
@inproceedings{shi2017new,
  author = {Xiaochuan Shi and Lei Wu and Xiaoliang Meng},
  title = {{A New Optimization Model for the Sustainable Development: Quadratic Knapsack Problem with Conflict Graphs}},
  booktitle = {Sustainability},
  year = {2017},
  doi = {10.3390/su9020236},
}
Figure