# Smallest cost in weighted directed graph with combinations

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.

• How many projects would you be analyzing at a given time? As in, would O(n!) be acceptable? – Vikhram Jan 27 '17 at 21:31
• @Vikhram It could theoretically be an unlimited number of projects, but realistically it would probably be 20~ companies and 100~ projects. – kyle Jan 27 '17 at 21:33
• What's teh typical number of "combination nodes" in the graph? Is it 20*100*0.20? (if there are 20 companies and 100 projects)? That seems like an overestimate and probably it should be 20*100*0.20/k where k is the average number of projects per combination, but it's not clear what k is. – D.W. Jan 30 '17 at 17:54
• @D.W. if there are 20 companies bidding on 100 projects, there could be up to 2000 bids, and out of those 2000 bids nearly 400 (20% of the total) bids would be a combination/lump sum. In the combination it could contain anywhere from 1% to 100% of the projects (unfortunately this doesn't simplify the problem). It could be where a company says that they want to pay X amount for the entire deal and would do all of the projects or a company could say they would pay Y amount for a small subset of the total projects. – kyle Jan 30 '17 at 19:18

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.

• This is definitely interesting and something that I will look into, thank you. Does this handle performance well if we greatly increase the variables, say that that there are 100 companies that bid on 1000 projects? – kyle Jan 27 '17 at 21:30
• @kyle You may have trouble finding a provable optimum, but I expect that performance will be quite good. One of the nice things about integer program solvers is that they give you a posteriori bounds on how well they're doing. – David Eisenstat Jan 27 '17 at 21:37
• This is currently the approach that I will be taking; however, I feel that there are more possible/optimal solutions (even though it is NP-hard) to this problem so I would like to keep the post open. If there aren't additional suggestions, I will accept this answer. Thank you @David Eisenstat – kyle Jan 30 '17 at 19:23

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.

• Thank you this is very insightful. I was looking through my algorithms book but couldn't find why the linear programming worked, but understand the weighted set aspect gave me a lot of insight. – kyle Jan 30 '17 at 20:36