Graph partitioning problem is a classical NP-hard problem.The improvement of graph partitioning results by vertex migration is an important class of methods for graph partitioning.The goal of graph partitioning is get...Graph partitioning problem is a classical NP-hard problem.The improvement of graph partitioning results by vertex migration is an important class of methods for graph partitioning.The goal of graph partitioning is getting a partition with the least number of cut edges,while also satisfying the capacity limit of the partition.In this paper,an optimization model for vertex migration is proposed,considering the influence between neighboring vertices,so that the objective function value of the model is exactly equal to the amount of cut edge variation.The model is converted into a mixed 0-1 linear programming by introducing variables.Then,a heuristic iterative algorithm is designed,in which the mixed 0-1 linear programming model is transformed into a series of small-scale models that contain less integer variables.In the experiment,the method in this paper is simulated and compared with balanced label propagation methods and their related methods.The improvement effect of these methods based on three different initialization methods is analyzed.Extensive numerical experiments on five commonly used datasets validate the effectiveness and efficiency of the proposed method.展开更多
为实现交叉口时空资源的高效利用,对交叉口车道布局与信号控制协同优化问题进行了研究。首先,基于美国国家电气制造商协会(National Electric Manufacturers Association,NEMA)的双环标准相位,考虑饱和流量随车道数增加的递减效应,以信...为实现交叉口时空资源的高效利用,对交叉口车道布局与信号控制协同优化问题进行了研究。首先,基于美国国家电气制造商协会(National Electric Manufacturers Association,NEMA)的双环标准相位,考虑饱和流量随车道数增加的递减效应,以信号周期最小化为模型的目标,以车道布局、相位时长、饱和流量、交通流量、流量比、饱和度为模型的约束条件,建立了交叉口车道布局与信号控制方案协同优化的0-1混合整数线性规划(binary-mix-integer-linear-program,BMILP)模型。其次,使用分支定界法,快速得到模型的全局最优解。最后,选取南京市的北京东路-丹凤街交叉口,设定了3组不同的流量组合,对模型进行了实例验证。结果表明:模型可根据交叉口交通流量的分布特征,生成相应的车道布局和信号配时方案,无须预设特定的车道布局模式,且能灵活配置共享车道和右转相位;同时,对模型的最大可接受饱和度参数进行了敏感性分析,讨论了该参数和信号周期、相位饱和度等优化结果的关系。展开更多
In this paper, the problem of program performance scheduling with accepting strategy is studied. Considering the uncertainty of actual situation, the duration of a program is expressed as a bounded interval. Firstly, ...In this paper, the problem of program performance scheduling with accepting strategy is studied. Considering the uncertainty of actual situation, the duration of a program is expressed as a bounded interval. Firstly, we decide which programs are accepted. Secondly, the risk preference coefficient of the decision maker is introduced. Thirdly, the min-max robust optimization model of the uncertain program show scheduling is built to minimize the performance cost and determine the sequence of these programs. Based on the above model, an effective algorithm for the original problem is proposed. The computational experiment shows that the performance’s cost (revenue) will increase (decrease) with decision maker’s risk aversion.展开更多
基金supported by the National Key Research and Development Program of China(No.2022YFA1003900).
文摘Graph partitioning problem is a classical NP-hard problem.The improvement of graph partitioning results by vertex migration is an important class of methods for graph partitioning.The goal of graph partitioning is getting a partition with the least number of cut edges,while also satisfying the capacity limit of the partition.In this paper,an optimization model for vertex migration is proposed,considering the influence between neighboring vertices,so that the objective function value of the model is exactly equal to the amount of cut edge variation.The model is converted into a mixed 0-1 linear programming by introducing variables.Then,a heuristic iterative algorithm is designed,in which the mixed 0-1 linear programming model is transformed into a series of small-scale models that contain less integer variables.In the experiment,the method in this paper is simulated and compared with balanced label propagation methods and their related methods.The improvement effect of these methods based on three different initialization methods is analyzed.Extensive numerical experiments on five commonly used datasets validate the effectiveness and efficiency of the proposed method.
文摘为实现交叉口时空资源的高效利用,对交叉口车道布局与信号控制协同优化问题进行了研究。首先,基于美国国家电气制造商协会(National Electric Manufacturers Association,NEMA)的双环标准相位,考虑饱和流量随车道数增加的递减效应,以信号周期最小化为模型的目标,以车道布局、相位时长、饱和流量、交通流量、流量比、饱和度为模型的约束条件,建立了交叉口车道布局与信号控制方案协同优化的0-1混合整数线性规划(binary-mix-integer-linear-program,BMILP)模型。其次,使用分支定界法,快速得到模型的全局最优解。最后,选取南京市的北京东路-丹凤街交叉口,设定了3组不同的流量组合,对模型进行了实例验证。结果表明:模型可根据交叉口交通流量的分布特征,生成相应的车道布局和信号配时方案,无须预设特定的车道布局模式,且能灵活配置共享车道和右转相位;同时,对模型的最大可接受饱和度参数进行了敏感性分析,讨论了该参数和信号周期、相位饱和度等优化结果的关系。
文摘In this paper, the problem of program performance scheduling with accepting strategy is studied. Considering the uncertainty of actual situation, the duration of a program is expressed as a bounded interval. Firstly, we decide which programs are accepted. Secondly, the risk preference coefficient of the decision maker is introduced. Thirdly, the min-max robust optimization model of the uncertain program show scheduling is built to minimize the performance cost and determine the sequence of these programs. Based on the above model, an effective algorithm for the original problem is proposed. The computational experiment shows that the performance’s cost (revenue) will increase (decrease) with decision maker’s risk aversion.
