We consider a linear relaxation of a generalized minimum-cost network flow problem with binary input dependencies. In this model the flows through certain arcs are bounded by linear (or more generally, piecewise linear concave) functions of the flows through other arcs. This formulation can be used to model interrelated systems in which the components of one system require the delivery of material from another system in order to function (for example, components of a subway system may require delivery of electrical power from a separate system). We propose and study randomized rounding schemes for how this model can be used to approximate solutions to a related mixed integer linear program for modeling binary input dependencies. The introduction of side constraints prevents this problem from being solved using the well-known network simplex algorithm, however by characterizing its basis structure we develop a generalization of network simplex algorithm that can be used for its {computationally} efficient solution.
翻译:我们认为,在二元输入依赖性下,普遍的最低成本网络流量问题可以直线放松。在这个模型中,通过某些弧流的流量受通过其他弧流的线性(或更一般地说,小线性线性线性线性)功能的约束。这一配方可用于模拟相互关联的系统,其中,一个系统的部件需要从另一个系统交付材料才能运作(例如,地铁系统的部件可能需要从一个单独的系统交付电力)。我们建议并研究随机四舍五入的组合办法,以了解如何利用这一模型来大致解决一个相关的混合整数线性程序,以模拟二元输入依赖性。由于引入侧面限制,这一问题无法通过众所周知的网络简单算法来解决,然而,通过描述其基础结构,我们开发了网络简单算法的通用化,可用于[投入 有效解 。