Success guarantee of dual search in integer programming: p-th power Lagrangian method

Although the Lagrangian method is a powerful dual search approach in intege r programming, it often fails to identify an optimal solution of the primal problem. The p-th power Lagrangian method developed in this paper offers a success guarantee for the dual search in generating an optimal solution of the primal integer programming problem in an equivalent setting via two ke y transformations. One other prominent feature of the p-th power Lagrangian method is that the dual search only involves a one-dimensional search with in [0,1]. Some potential applications of the method as well as the issue of its implementation are discussed.