Wang, Fenlan A combination of linear approximation and Lagrangian dual with a simple cut for general separable integer programming problems. (English) Zbl 1454.90032 Pac. J. Optim. 16, No. 3, 441-459 (2020). Summary: In this paper, a new simple and exact algorithm is presented for general separable integer programming problems. The algorithm incorporates a special domain cut into the branch and bound method. The domain cut technique removes some regions that don’t contain optimal solutions to the primal problem from the hyper-rectable, which makes the presented algorithm in this paper different from the traditional branch and bound method. Also the duality gap can be reduced in the domain cut process. The lower bound can be calculated easily by solving a linear programming problem and its Lagrangian dual problem. The computational experiments are reported for two kinds of convex, concave or nonconvex and nonconcave objective functions respectively in the paper. The numerical comparison with the traditional branch and bound method for a quadratic polynomial convex objective function is given and the comparison results show the algorithm is encouraging. Cited in 1 Document MSC: 90C10 Integer programming 90C26 Nonconvex programming, global optimization 90C30 Nonlinear programming Keywords:separable integer programming; linear approximation; Lagrangian dual; branch and bound; duality gap PDFBibTeX XMLCite \textit{F. Wang}, Pac. J. Optim. 16, No. 3, 441--459 (2020; Zbl 1454.90032) Full Text: Link