Smallest cost in weighted directed graph with combinations

Question

I am trying to develop an algorithm that can traverse a graph with intermediary/all or nothing(?) nodes.

The problem is that there are companies B, C and D that are bidding on projects X, Y and Z. The companies can do individual bids for any of the projects, or they can say that they will complete a combination of projects for a total of x dollars. However this combination is all or nothing and cannot be split. I need to find the path with the least cost for all of X, Y and Z from the initial A (manager) node, that takes into account the combination of costs.

The following graph illustrates the problem that I am trying to solve:

A typical graph traversal algorithm would say that for A -> X the path A -> B -> X with cost 5, for A -> Y the path A -> C -> Y with cost 4 and for the path A -> Z the path A -> C -> Z with cost 6 should be taken. Making the cumulative total be 15.

However, introducing the idea of an intermediary/combination node, would say that for A -> X the path that should be taken would be A -> B -> X with cost 5. Then for A -> Y and A -> Z it should share the cost and take A -> D -> DL -> Y combined with A -> D -> DL -> Z with the lump sum of 8. This would result in the lesser cost of 13.

Some general notes are that this is a very small example of the overall problem that I am trying to solve. At any given time there can be many companies and many projects (100+), and additionally, there can be may bids/edges between the companies and projects and there can be many combinations/lump sum bids.

The could explain the problem best using a graph but it doesn't necessarily mean that it is the best solution. It almost seems to me to be graphing up front, but then introducing the combination nodes makes it seem like a derivative of the knapsack problem. I appreciate any help or direction.

edit Typically there will be 20 companies and anywhere from 20-100 categories. Typically the number of bids will be (companies) * (categories) where 20% of the bids are combinations. So if there are 2000 bids approximately 400 could be a combination bid. The number of projects in a combination could make up only min + 1 or all of the categories.

Answer 1

You can formulate problems like this as an integer program and apply off-the-shelf tools to find (near) optimal solutions.

The example is rendered something like this (the exact syntax depends on the tool).

minimize 5*BX + 10*BZ + 4*CY + 6*CZ + 10*DX + 7*DYZ
subject to
BX + DX = 1  # project X is done once
CY + DYZ = 1  # project Y is done once
BZ + CZ + DYZ = 1  # project Z is done once
binary variables BX, BZ, CY, CZ, DX, DYZ in {0, 1}

The interpretation of, e.g., DYZ is that D is awarded the package of contracts for Y and Z if and only if DYZ has value 1.

Answer 2

Your problem is called weighted set cover. Each set corresponds to a bid (a combination bid corresponds to a set of size larger than one; a single bid corresponds to a set of size one). The cost/weight of each set is the dollar amount of that bid. You then want to find a set cover -- a combination of sets whose union covers all of the projects -- i.e., a combination of bids that ensures all projects will be completed.

As a result, your problem is NP-hard, and you should not expect any algorithm that efficiently finds the optimal solution for all possible problem instances. You'll probably have to give up something: either accept that the algorithm might not be fast for arbitrarily-large problem instances; or that it might give incorrect answers for some problem instances; or accept sub-optimal solutions; or find some special structure in your problem instances that you can exploit.

The weighted set cover problem has been studied in some depth. If you want an exact solution, the standard approach is to use integer linear programming. If you want an approximation algorithm (an efficient algorithm to get a solution that probably won't be optimal but will be not-too-far from optimal), you can use the standard greedy algorithm -- though in practice this probably won't be useful, as it means you might pay a $\log n$ factor more than necessary, where $n$ is the total number of projects to be completed.