A linear input dependence model for interdependent networks

This repository contains raw data generated for use in Kaul and Rumpf 2021 (referenced below), and includes the results from a series of computational trials that compare the behaviors of binary and linear input dependence models for interdependent flow networks. A large number of artificial test networks was generated, solved exactly using the binary input dependence model, solved exactly using the linear relaxation, and then solved approximately using a randomized rounding algorithm based on the solution of the linear relaxation. The results from these trials suggest that the linear relaxation typically produces objective values extremely similar to the binary model while being significantly less computationally expensive, and that the linear relaxation can be used as part of a randomized rounding scheme to produce near-optimal feasible solutions to the binary model usually within only a few attempts, although these results can vary significantly by network. Moreover, the linear relaxation and randomized rounding schemes tend to perform better and to produce results closer to the binary model when the density of interdependent arcs is relatively low. See the README included in the data set for a full description.

本仓库包含为Kaul与Rumpf 2021年研究（参考文献见下文）生成的原始数据，同时收录了一系列计算试验的结果——这些试验用于对比相依流网络（interdependent flow networks）下的二进制输入依赖模型与线性输入依赖模型的表现。研究团队生成了大量人工测试网络，分别使用二进制输入依赖模型（binary input dependence model）对其进行精确求解，采用线性松弛（linear relaxation）完成精确求解，随后基于线性松弛的求解结果，通过随机舍入算法（randomized rounding algorithm）实现近似求解。上述试验结果表明，线性松弛通常可生成与二进制模型极为相近的目标函数值，同时计算成本显著更低；此外，线性松弛可作为随机舍入方案的组成部分，仅需少量尝试即可为二进制模型生成近似最优的可行解，不过这些结果会因网络差异存在显著波动。进一步而言，当相依弧（interdependent arcs）的密度相对较低时，线性松弛与随机舍入方案的表现往往更优，生成的结果也更贴近二进制模型。完整说明请参阅数据集内附带的README文件。