title: Maximizing minimum edge+node value in a directed graph
body: <p>I have a directed graph. Each edge has an intrinsic "weight" <code>w_ij</code>, which is fixed. Each node has a value <code>v_i</code> that can be configured, except for "root nodes" (no incoming edges) and "leaf nodes" (nooutgoing edges) whose values are fixed.</p>
  
  <p>the "adjusted by node" edge value of each edge is given by:
  <code>s_ij = w_ij + v_j - v_i</code> that is, we adjust the the value of an edge by the difference of values of its adjacent nodes. Of course, changing the values of nodes will affect the values of <code>s_ij</code>.</p>
  
  <p>I am interested in the value of <code>min{s_ij}</code>, and want to find the optimal assignment of values to nodes, so that this "bottleneck" value is maximized.</p>
  
  <p>Any ideas of how to do that?</p>
  
  <p><strong>Note:</strong> Cycles and "fixed paths" from a root to a leaf provide upper bounds for the minimum value (e.g. in a cycle, the sum of node differences is always 0, so the best you could get is the average of the edges' intrinsic weights). But because cycles and "fixed paths" may overlap, it is not clear whether the minimal upper bound is attainable. It is likely that the solution will involve finding such paths/cycles first.</p>