Abstract
In this paper, we propose a convergent Lagrangian and objective level cut method for computing exact solution to two classes of nonlinear integer programming problems: separable nonlinear integer programming and polynomial zero-one programming. The method exposes an optimal solution to the convex hull of a revised perturbation function by successively reshaping or re-confining the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence of the Lagrangian method on a revised domain. Computational results are reported for a variety of nonlinear integer programming problems and demonstrate that the proposed method is promising in solving medium-size nonlinear integer programming problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Balas E. (1965). An additive algorithm for solving linear programs with zero-one variables. Oper. Res. 13: 517–546
Balas E. and Mazzola J.B. (1984a). Nonlinear 0-1 programming: I. Linearization techniques. Math. Program. 30: 1–21
Balas E. and Mazzola J.B. (1984b). Nonlinear 0–1 programming: II. Dominance relations and algorithms. Math. Program. 30: 22–45
Bell D.E. and Shapiro J.F. (1977). A convergent duality theory for integer programming. Oper. Res. 25: 419–434
Benson H.P. and Erenguc S.S. (1990). An algorithm for concave integer minimization over a polyhedron. Nav. Res. Logist. 37: 515–525
Bretthauer K.M., Cabot A.V. and Venkataramanan M.A. (1994). An algorithm and new penalties for concave integer minimization over a polyhedron. Nav. Res. Logist. 41: 435–454
Bretthauer K.M. and Shetty B. (1995). The nonlinear resource allocation problem. Oper. Res. 43: 670–683
Bretthauer K.M. and Shetty B. (2002). A pegging algorithm for the nonlinear resource allocation problem. Comput. Oper. Res. 29: 505–527
Chern M.S. (1992). On the computational complexity of reliability redundancy allocation in a series system. Oper. Res. Lett. 11: 309–315
Dantzig G.B. (1960). On the significance of solving linear programming with some integer variables. Econometrica 28: 30–40
Fisher M.L. (1981). The Lagrangian relaxation method for solving integer programming problems. Manage. Sci. 27: 1–18
Fisher M.L. and Shapiro J.F. (1974). Constructive duality in integer programming. SIAM J. Appl. Math. 27: 31–52
Floudas, C.A.: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, Oxford (1995)
Fortet, R.: L′algèbre de Boole et ses applications en recherche Opérationnelle. Cah. Centre d’ Étud. Rech. Opér. 1, 5–36 (1959)
Fortet and R. (1960). Applications de l′algèbre de Boole en recherche Opérationnelle. Rev. Fr. d’ Inform. Rech. Opér. 4: 17–26
Geoffrion A.M. (1967). Integer programming by implicit enumeration and Balas’ method. SIAM Rev. 9: 178–190
Geoffrion A.M. (1974). Lagrangean relaxation for integer programming. Math. Program. Study 2: 82–114
Granot F. and Hammer P.L. (1975). On the role of generalized covering problems. Cah. Centre d’ Étud. Rech. Opèr. 17: 277–289
Grossmann I.E., Kravanja Z.: Mixed-integer nonlinear programming: a survey of algorithms and applications. In: Biegler, L.T., Coleman, T.F., Conn, A.R. and F. N. Santosa (eds.) Large-Scale optimization with Applications, Part II: Optimization Design and Control. Springer, Berlin, Heidelberg, New york (1997)
Hansen P. (1979). Methods of nonlinear 0-1 programming. Ann. Discrete Math. 5: 53–70
Hansen P., Jaumard B. and Mathon V. (1993). Constrained nonlinear 0-1 programming. ORSA J. Comput. 5: 97–119
Helmberg C. and Rendl F. (1998). Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program. 82: 291–315
Hochbaum D.S. (1995). A nonlinear Knapsack problem. Oper. Res. Lett. 17: 103–110
Horst R. and Thoai N.V. (1998). An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks. OR Spektrum 20: 47–53
Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Berlin, Heidelberg, New york (1993)
Ibaraki T. and Katoh N. (1988). Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge, MA
Lemaréchal C. and Renaud A. (1998). A geometric study of duality gaps, with applications. Math. Program 90: 399–427
Li D. and Sun X.L. (2000). Success guarantee of dual search in integer programming: p-th power Lagrangian method. J. Glob. Optim. 18: 235–254
Li D. and Sun X.L. (2006). Towards strong duality in integer programming. J. Glob. Optim. 35: 255–282
Li D. and White D.J. (2000). P-th power Lagrangian method for integer programming. Ann. Oper. Res. 98: 151–170
Marsten R.E. and Morin T.L. (1978). A hybrid approach to discrete mathematical programming. Math. Program. 14: 21–40
McCormick G.P. (1975). Computability of global solutions to factorable nonconvex programs: part I convex underestimating problems. Math. Program. 10: 147–175
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)
Parker, R.G., Rardin, R.L.: Discrete Optimization. Academic, Boston (1988)
Poljak S., Rendl F. and Wolkoswicz H. (1995). A recipe for semidefinite relaxation for 0-1 quadratic programming. J. Glob. Optim. 7: 51–73
Roelofs, M., Bisschop, J.: AIMMS user’s Guide. Paragon Decision Technology. http://www.aimms.com/aimms/download/manuals/AIMMS_ 3UG.pdf (2006)
Ryoo H.S. and Sahinidis N.V. (2001). Analysis of bounds for multilinear functions. J. Glob. Optim. 19: 403–424
Ryoo H.S. and Sahinidis N.V. (2003). Global optimization of multilinear problems. J. Glob. Optim. 26: 387–418
Sahinidis, N.V.: BARON: branch and reduce optimization navigator, user’s manual ver. 4.0. Department of Chemical Engineering, University of Illinois at Urbana Champaign. http://archimedes.scs.uiuc.edu/baron/manuse.pdf (2000)
Shapiro J.F. (1979). A survey of lagrangian techniques for discrete optimization. Ann. Discrete Math. 5: 113–138
Sherali H.D. (1997). Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Math. Vietnam 22: 245–270
Sherali H.D. (1998). Global optimization of nonconvex polynomial programming problems having rational exponents. J. Glob. Optim. 12: 267–283
Sherali H.D. and Wang H. (2001). Global optimization of nonconvex factorable programming problems. Math. Program. 89: 459–478
Smith E.M. and Pantelides C.C. (1997). Global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 21: S791–S796
Sun X.L. and Li D. (2000). Asymptotic strong duality for bounded integer programming: a logarithmic-exponential dual formulation. Math. Oper. Res. 25: 625–644
Sun X.L. and Li D. (2002). Optimality condition and branch and bound algorithm for constrained redundancy optimization in series systems. Optim. Eng. 3: 53–65
Taha H.A. (1972). A Balasian-based algorithm for zero-one polynomial programming. Manage. Sci. 18: B328–B343
Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Dordrecht (2002)
Tawarmalani M. and Sahinidis N.V. (2004). Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math. Program. 99: 563–591
Watters L.J. (1967). Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper. Res. 15: 1171–1174
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, D., Wang, J. & Sun, X.L. Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method. J Glob Optim 39, 127–154 (2007). https://doi.org/10.1007/s10898-006-9128-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-006-9128-7