Topology Knapsack Problem for Geometry Optimization

The knapsack problem is a classic NP-Hard optimization challenge with wide-ranging applications in computer science, such as resource allocation. While several variants have been developed, including the 0/1, fractional, and multi-dimensional knapsack problems, no existing model simultaneously optimizes multiple attributes like rarity, importance, and preference alongside the weight and volume of items. The multi-dimensional knapsack problem is the closest approach, but it still fails to fully address this complex optimization challenge. This paper implements the topology knapsack problem, a novel variant integrating high-dimensional datasets and multiple attributes for each item. The goal is to maximize the total "topo value" by optimally selecting items based on these diverse attributes. Experimental results using both virtual and real-world datasets demonstrate that the topology knapsack problem outperforms traditional knapsack models in terms of diversity and uniformity of the selected item set. It also shows superior performance compared to popular community detection algorithms. Employing t-SNE for dimensionality reduction and K-means for clustering provides an effective solution for multi-attribute optimization. The results indicate notable improvements over existing methods and suggest the potential for future applications in more complex decision-making problems.