Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Towards Strong Duality in Integer Programming

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D.E. Bell J.F. Shapiro (1977) ArticleTitleA convergent dualy theory for integer programming Operations Research 25 419–434

    Google Scholar 

  2. D. Dentcheva W. Romisch (2004) ArticleTitleDuality gaps in nonconvex stochastic optimization Mathematical Programming 101 515–535 Occurrence Handle10.1007/s10107-003-0496-1

    Article  Google Scholar 

  3. M.L. Fisher (1981) ArticleTitleThe Lagrangian relaxation method for solving integer programming problems Management Science 27 1–18

    Google Scholar 

  4. M.L. Fisher J.F. Shapiro (1974) ArticleTitleConstructive duality in integer Programming SIAM Journal on Applied Mathematics 27 31–52 Occurrence Handle10.1137/0127003

    Article  Google Scholar 

  5. A.M. Geoffrion (1974) ArticleTitleLagrangian relaxation for integer programming Mathematical Programming Study 2 82–114

    Google Scholar 

  6. M. Guignard S. Kim (1987) ArticleTitleLagrangian decomposition: A model yielding stronger Lagrangian relaxation bounds Mathematical Programming 33 262–273

    Google Scholar 

  7. K. Holmberg (1994) ArticleTitleCross decomposition applied to integer programming problems: Duality gaps and convexification in parts Operations Research 42 657–668 Occurrence Handle10.1287/opre.42.4.657

    Article  Google Scholar 

  8. C. Lemaréchal A. Renaud (2001) ArticleTitleA geometric study of duality gaps, with applications Mathematical Programming 90 399–427 Occurrence Handle10.1007/PL00011429

    Article  Google Scholar 

  9. D. Li (1995) ArticleTitleZero duality gap for a class of nonconvex optimization problems Journal of Optimization Theory and Applications 85 309–324 Occurrence Handle10.1007/BF02192229

    Article  Google Scholar 

  10. D. Li (1999) ArticleTitleZero duality gap in integer programming: P-norm surrogate constraint method Operations Research Letters 25 89–96 Occurrence Handle10.1016/S0167-6377(99)00039-5

    Article  Google Scholar 

  11. D. Li X.L. Sun (2000) ArticleTitleSuccess guarantee of dual search in nonlinear integer programming: P-th Power Lagrangian Method Journal of Global Optimization 18 235–254 Occurrence Handle10.1023/A:1008325116400

    Article  Google Scholar 

  12. D. Li D.J. White (2000) ArticleTitleP-th power Lagrangian method for integer programming Annals of Operations Research 98 151–170 Occurrence Handle10.1023/A:1019252306512

    Article  Google Scholar 

  13. P. Michelon N. Maculan (1991) ArticleTitleLagrangian decomposition for integer nonlinear programming with linear constraints Mathematical Programming 52 303–313 Occurrence Handle10.1007/BF01582893

    Article  Google Scholar 

  14. P. Michelon N. Maculan (1993) ArticleTitleLagrangian methods for 0-1 quadratic programming Discrete Applied Mathematics 42 257–269 Occurrence Handle10.1016/0166-218X(93)90049-T

    Article  Google Scholar 

  15. K. Murota (1998) ArticleTitleDiscrete convex analysis Mathematical Programming 83 313–371 Occurrence Handle10.1016/S0025-5610(98)00010-0

    Article  Google Scholar 

  16. G.L. Nemhauser L.A. Wolsey (1988) Integer and Combinatorial Optimization John Wiley & Sons New York

    Google Scholar 

  17. S. Sen J.L. Higle J.R. Birge (2000) ArticleTitleDuality gaps in stochastic integer programming Journal of Global Optimization 18 189–194 Occurrence Handle10.1023/A:1008314824754

    Article  Google Scholar 

  18. J.F. Shapiro (1979) ArticleTitleA survey of Lagrangian techniques for discrete optimization Annals of Discrete Mathematics 5 113–138 Occurrence Handle10.1016/S0167-5060(08)70346-7

    Article  Google Scholar 

  19. X.L. Sun D. Li (2000) ArticleTitleAsymptotic strong duality for bounded integer programming: A logarithmic-exponential dual formulation Mathematics of Operations Research 25 625–644 Occurrence Handle10.1287/moor.25.4.625.12114

    Article  Google Scholar 

  20. H.P. Williams (1996) ArticleTitleDuality in mathematics and linear and integer programming Journal of Optimization Theory and Applications 90 257–278 Occurrence Handle10.1007/BF02189998

    Article  Google Scholar 

  21. L.A. Wolsey (1981) ArticleTitleInteger programming duality: Price functions and sensitivity analysis Mathematical Programming 20 173–195 Occurrence Handle10.1007/BF01589344

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, NT, Hong Kong

    D. Li

  2. Department of Mathematics, Shanghai University, Baoshan, Shanghai, 200444, P. R. China

    X. L. Sun

Authors
  1. D. Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. X. L. Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to D. Li.

Additional information

Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Li, D., Sun, X.L. Towards Strong Duality in Integer Programming. J Glob Optim 35, 255–282 (2006). https://doi.org/10.1007/s10898-005-3838-0

Download citation

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-005-3838-0

Keywords

Search

Navigation