pth Power Lagrangian Method for Integer Programming

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

25 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)151-170
Journal / PublicationAnnals of Operations Research
Volume98
Issue number1-4
Publication statusPublished - Dec 2000
Externally publishedYes

Abstract

When does there exist an optimal generating Lagrangian multiplier vector (that generates an optimal solution of an integer programming problem in a Lagrangian relaxation formulation), and in cases of nonexistence, can we produce the existence in some other equivalent representation space? Under what conditions does there exist an optimal primal-dual pair in integer programming? This paper considers both questions. A theoretical characterization of the perturbation function in integer programming yields a new insight on the existence of an optimal generating Lagrangian multiplier vector, the existence of an optimal primal-dual pair, and the duality gap. The proposed pth power Lagrangian method convexifies the perturbation function and guarantees the existence of an optimal generating Lagrangian multiplier vector. A condition for the existence of an optimal primal-dual pair is given for the Lagrangian relaxation method to be successful in identifying an optimal solution of the primal problem via the maximization of the Lagrangian dual. The existence of an optimal primal-dual pair is assured for cases with a single Lagrangian constraint, while adopting the pth power Lagrangian method. This paper then shows that an integer programming problem with multiple constraints can be always converted into an equivalent form with a single surrogate constraint. Therefore, success of a dual search is guaranteed for a general class of finite integer programming problems with a prominent feature of a one-dimensional dual search.

Research Area(s)

  • Convexification, Duality gap, Integer programming, Lagrangian relaxation, Primal-dual approach, pth power Lagrangian method, Surrogate constraint method

Citation Format(s)

pth Power Lagrangian Method for Integer Programming. / LI, DUAN; WHITE, DOUGLAS J.

In: Annals of Operations Research, Vol. 98, No. 1-4, 12.2000, p. 151-170.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review