Variant of Constants in Subgradient Optimization Method over Planar 3-Index Assignment Problems

[摘要] A planar 3-index assignment problem (P3AP) of sizenis an NP-complete problem. Its global optimal solution can be determined by a branch and bound algorithm. The efficiency of the algorithm depends on the best lower and upper bound of the problem. The subgradient optimization method, an iterative method, can provide a good lower bound of the problem. This method can be applied to the root node or a leaf of the branch and bound tree. Some conditions used in this method may result in one of those becoming optimal. The formulas used in this method contain some constants that can be evaluated by computational experiments. In this paper, we show a variety of initial step length constants whose values have an effect on the lower bound of the problem. The results show that, for small problem sizes, when n < 20, the most suitable constants are best chosen in the interval [0.1, 1]. Meanwhile, the interval [0.05, 0.1] is the best interval chosen for the larger problem sizes, when n ≥ 20.

[学科分类] 计算数学

[关键词] planar 3-index assignment problem (P3AP);NP-complete;lower bound;upper bound;subgradient optimization method;computer experiment;step length constant