用线性规划优化图上扩散过程的边界控制,兼顾物理约束与几何精度。
Optimal Boundary Control of Diffusion on Graphs via Linear Programming
- 基于加权有向图建模扩散,通过线性规划求解边界控制
- 在无负递减方向下保证全局最优解存在,可行域有界
- 适用于城市街区与场馆等大型网络系统的扩散优化
我们提出一种线性规划(LP)框架,用于几何网络上的稳态扩散与通量优化。状态变量满足加权有向图上的离散扩散定律,电导率按边长缩放以保持几何保真度。边界电位作为控制量,根据线性网络拉普拉斯算子驱动内部通量。优化问题在所有边界边上施加物理上有意义的符号约束和通量上限,直接源自梯度界。这生成一个有限维线性规划,其可行集为多面体,有界性和可解性由网络数据的简单几何或代数条件决定。我们证明:在不存在负递减方向时——该条件在存在有限盒约束、通量上限或符号限制时自动满足——该线性规划存在全局最小值。识别出若干确保可行域有界的充分条件,涵盖满秩与秩亏的通量映射情况。分析将经典结果如Minkowski–Weyl分解、Hoffman界及线性规划基本定理与现代基于网络的扩散建模相连接。两个大规模实例说明该框架:(i) 一座典型大型现代城市体育场,形成单连通组件且走廊宽度相对均匀;(ii) 从大型历史市中心延伸出的复杂街道网络,构成多组件系统。
原文摘要 · Abstract (English)
We propose a linear programming (LP) framework for steady-state diffusion and flux optimization on geometric networks. The state variable satisfies a discrete diffusion law on a weighted, oriented graph, where conductances are scaled by edge lengths to preserve geometric fidelity. Boundary potentials act as controls that drive interior fluxes according to a linear network Laplacian. The optimization problem enforces physically meaningful sign and flux-cap constraints at all boundary edges, derived directly from a gradient bound. This yields a finite-dimensional LP whose feasible set is polyhedral, and whose boundedness and solvability follow from simple geometric or algebraic conditions on the network data. We prove that under the absence of negative recession directions--automatically satisfied in the presence of finite box bounds, flux caps, or sign restrictions--the LP admits a global minimizer. Several sufficient conditions guaranteeing boundedness of the feasible region are identified, covering both full-rank and rank-deficient flux maps. The analysis connects classical results such as the Minkowski--Weyl decomposition, Hoffman's bound, and the fundamental theorem of linear programming with modern network-based diffusion modeling. Two large-scale examples illustrate the framework: (i) A typical large stadium in a major modern city, which forms a single connected component with relatively uniform corridor widths, and a (ii) A complex street network emanating from a large, historical city center, which forms a multi-component system.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。