Just out of theoretical curiosity, is there a way to transform a 0-1 multimensional knapsack problem to a maximum clique problem? Or maybe even easier, to a maximum weighted clique problem (the weights in nodes)?
I assume that since the decision counterparts of both problems are NP-complete, and all NP-complete can be transformed to each other, there must be a way to transform their functional counterparts as well, although I don't know whether that assumption is in general true.
I have already found a way to transform a maximum weighted clique problem (if the graph is connected) to a multidimensional 0-1 knapsack by creating a variable and a restriction for each (undirected) pair, but I cannot think a way to do the inverse transformation, because the knapsack problem doesn't have a "transitive" property, in the sense that if items a
and b
fit together, and b
and c
fit together, and a
and c
fit together, doesn't mean that all three fit together at once, while the clique problem does indeed have this "transitive" property (if three nodes are connected to each other two-by-two, a solution containing all three is feasible).