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 -&gt; X the path A -&gt; B -&gt; X with cost 5, for A -&gt; Y the path A -&gt; C -&gt; Y with cost 4 and for the path A -&gt; Z the path A -&gt; C -&gt; 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 -&gt; X the path that should be taken would be A -&gt; B -&gt; X with cost 5.  Then for A -&gt; Y and A -&gt; Z it should share the cost and take A -&gt; D -&gt; DL -&gt; Y combined with A -&gt; D -&gt; DL -&gt; 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.
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.