Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are present...Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.展开更多
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.展开更多
Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems a...Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.展开更多
为实现交叉口时空资源的高效利用,对交叉口车道布局与信号控制协同优化问题进行了研究。首先,基于美国国家电气制造商协会(National Electric Manufacturers Association,NEMA)的双环标准相位,考虑饱和流量随车道数增加的递减效应,以信...为实现交叉口时空资源的高效利用,对交叉口车道布局与信号控制协同优化问题进行了研究。首先,基于美国国家电气制造商协会(National Electric Manufacturers Association,NEMA)的双环标准相位,考虑饱和流量随车道数增加的递减效应,以信号周期最小化为模型的目标,以车道布局、相位时长、饱和流量、交通流量、流量比、饱和度为模型的约束条件,建立了交叉口车道布局与信号控制方案协同优化的0-1混合整数线性规划(binary-mix-integer-linear-program,BMILP)模型。其次,使用分支定界法,快速得到模型的全局最优解。最后,选取南京市的北京东路-丹凤街交叉口,设定了3组不同的流量组合,对模型进行了实例验证。结果表明:模型可根据交叉口交通流量的分布特征,生成相应的车道布局和信号配时方案,无须预设特定的车道布局模式,且能灵活配置共享车道和右转相位;同时,对模型的最大可接受饱和度参数进行了敏感性分析,讨论了该参数和信号周期、相位饱和度等优化结果的关系。展开更多
文摘Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.
基金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.
基金Project supported by the National Natural Science Foundation oChina (Grant os.79970107 and 10271073)
文摘Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.
文摘为实现交叉口时空资源的高效利用,对交叉口车道布局与信号控制协同优化问题进行了研究。首先,基于美国国家电气制造商协会(National Electric Manufacturers Association,NEMA)的双环标准相位,考虑饱和流量随车道数增加的递减效应,以信号周期最小化为模型的目标,以车道布局、相位时长、饱和流量、交通流量、流量比、饱和度为模型的约束条件,建立了交叉口车道布局与信号控制方案协同优化的0-1混合整数线性规划(binary-mix-integer-linear-program,BMILP)模型。其次,使用分支定界法,快速得到模型的全局最优解。最后,选取南京市的北京东路-丹凤街交叉口,设定了3组不同的流量组合,对模型进行了实例验证。结果表明:模型可根据交叉口交通流量的分布特征,生成相应的车道布局和信号配时方案,无须预设特定的车道布局模式,且能灵活配置共享车道和右转相位;同时,对模型的最大可接受饱和度参数进行了敏感性分析,讨论了该参数和信号周期、相位饱和度等优化结果的关系。
