Abstract

There have been several combinations of the knapsack problem and the shortest paths on weighted graph problems in different researches. The combination is often used to describe the choices made during the knapsack problem stages using dynamic programming methods, by using the knapsack graph. But these researches consider only two aspects of weight and value for an item/vertex. The objective of this paper is to address a different kind of problem in which we are taking into consideration three properties: item weight, item value and edge weight (that connects two items, but its weight is not depended on its vertices). The problem presented here is finding the most efficient path between two vertices of this specific kind of graph, in three aspects- minimal edge wise, maximum knapsack value wise, and a combination of maximal efficiency of both properties. This is done through an object oriented method, in which every path of the graph, between two chosen vertices, has comparable attributes, that gives us the ability to prefer a certain path from another. An algorithm for finding these optimal paths is presented here, along with specific explanations on its decision stages, and several examples for it. The results were achieved an exact paradigm for the integrated problem, taking into consideration any desired aspect, and achieving optimal choices per each attribute.

Keyword

Knapsack problem, Shortest paths on weighted graphs, Dijkstra's algorithm, 0-1 knapsack problem, Graph theory, Dynamic programming, All paths between two vertices in a graph.

Cite this article

Refference

[1][1]Poirriez V, Yanev N, Andonov R. A hybrid algorithm for the unbounded knapsack problem. Discrete Optimization. 2009;6(1):110-24.

[2][2]Abraham I, Fiat A, Goldberg AV, Werneck RF. Highway dimension, shortest paths, and provably efficient algorithms. In proceedings of the ACM-SIAM symposium on discrete algorithms 2010 (pp. 782-93). Society for Industrial and Applied Mathematics.

[3][3]Ensthaler L, Giebe T. Subsidies, Knapsack auctions and dantzig’s greedy heuristic. 2009.

[4][4]Pisinger D, Sigurd M. Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS Journal on Computing. 2007;19(1):36-51.

[5][5]Yan, M. http://math.mit.edu/~rothvoss/18.304.3PM/Presentations/1-Melissa.pdf. Accessed 23 May 2016.

[6][6]Mehlhorn K, Sanders P. Algorithms and data structures: the basic toolbox. Springer Science & Business Media; 2008.

[7][7]Druken BK. A hike through the forest: the knapsack problem in graph theory. Senior Honors Projects. 2008.

[8][8]Pferschy U, Schauer J. The knapsack problem with conflict graphs. Journal of Graph Algorithms and Applications. 2009;13(2):233-49.

[9][9]Jiang Z, Hu X, Gao S. A parallel ford-fulkerson algorithm for maximum flow problem. In proceedings of the international conference on parallel and distributed processing techniques and applications 2013 (pp. 70-3). WorldComp.