×

A combination of linear approximation and Lagrangian dual with a simple cut for general separable integer programming problems. (English) Zbl 1454.90032

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.

MSC:

90C10 Integer programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: Link