×

Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method. (English) Zbl 1151.90027

Summary: 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.

MSC:

90C10 Integer programming
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming

Software:

AIMMS; BARON
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balas E. (1965). An additive algorithm for solving linear programs with zero-one variables. Oper. Res. 13: 517–546 · Zbl 0194.19903 · doi:10.1287/opre.13.4.517
[2] Balas E. and Mazzola J.B. (1984a). Nonlinear 0-1 programming: I. Linearization techniques. Math. Program. 30: 1–21 · Zbl 0553.90067 · doi:10.1007/BF02591796
[3] Balas E. and Mazzola J.B. (1984b). Nonlinear 0–1 programming: II. Dominance relations and algorithms. Math. Program. 30: 22–45 · Zbl 0553.90068
[4] Bell D.E. and Shapiro J.F. (1977). A convergent duality theory for integer programming. Oper. Res. 25: 419–434 · Zbl 0381.90079 · doi:10.1287/opre.25.3.419
[5] Benson H.P. and Erenguc S.S. (1990). An algorithm for concave integer minimization over a polyhedron. Nav. Res. Logist. 37: 515–525 · Zbl 0714.90072 · doi:10.1002/1520-6750(199008)37:4<515::AID-NAV3220370406>3.0.CO;2-X
[6] 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 · Zbl 0830.90106 · doi:10.1002/1520-6750(199404)41:3<435::AID-NAV3220410309>3.0.CO;2-6
[7] Bretthauer K.M. and Shetty B. (1995). The nonlinear resource allocation problem. Oper. Res. 43: 670–683 · Zbl 0857.90090 · doi:10.1287/opre.43.4.670
[8] Bretthauer K.M. and Shetty B. (2002). A pegging algorithm for the nonlinear resource allocation problem. Comput. Oper. Res. 29: 505–527 · Zbl 0995.90057 · doi:10.1016/S0305-0548(00)00089-7
[9] Chern M.S. (1992). On the computational complexity of reliability redundancy allocation in a series system. Oper. Res. Lett. 11: 309–315 · Zbl 0767.90021 · doi:10.1016/0167-6377(92)90008-Q
[10] Dantzig G.B. (1960). On the significance of solving linear programming with some integer variables. Econometrica 28: 30–40 · Zbl 0089.16101 · doi:10.2307/1905292
[11] Fisher M.L. (1981). The Lagrangian relaxation method for solving integer programming problems. Manage. Sci. 27: 1–18 · Zbl 0466.90054 · doi:10.1287/mnsc.27.1.1
[12] Fisher M.L. and Shapiro J.F. (1974). Constructive duality in integer programming. SIAM J. Appl. Math. 27: 31–52 · Zbl 0299.90010 · doi:10.1137/0127003
[13] Floudas, C.A.: Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, Oxford (1995) · Zbl 0886.90106
[14] 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) · Zbl 0093.32704
[15] 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
[16] Geoffrion A.M. (1967). Integer programming by implicit enumeration and Balas’ method. SIAM Rev. 9: 178–190 · Zbl 0213.44702 · doi:10.1137/1009031
[17] Geoffrion A.M. (1974). Lagrangean relaxation for integer programming. Math. Program. Study 2: 82–114 · Zbl 0395.90056
[18] Granot F. and Hammer P.L. (1975). On the role of generalized covering problems. Cah. Centre d’ Étud. Rech. Opèr. 17: 277–289
[19] 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) · Zbl 0884.65058
[20] Hansen P. (1979). Methods of nonlinear 0-1 programming. Ann. Discrete Math. 5: 53–70 · Zbl 0426.90063 · doi:10.1016/S0167-5060(08)70343-1
[21] Hansen P., Jaumard B. and Mathon V. (1993). Constrained nonlinear 0-1 programming. ORSA J. Comput. 5: 97–119 · Zbl 0777.90033
[22] Helmberg C. and Rendl F. (1998). Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program. 82: 291–315 · Zbl 0919.90112
[23] Hochbaum D.S. (1995). A nonlinear Knapsack problem. Oper. Res. Lett. 17: 103–110 · Zbl 0838.90092 · doi:10.1016/0167-6377(95)00009-9
[24] 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 · Zbl 0897.90096 · doi:10.1007/BF01545530
[25] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Berlin, Heidelberg, New york (1993) · Zbl 0704.90057
[26] Ibaraki T. and Katoh N. (1988). Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge, MA · Zbl 0786.90067
[27] Lemaréchal C. and Renaud A. (1998). A geometric study of duality gaps, with applications. Math. Program 90: 399–427 · Zbl 1039.90087 · doi:10.1007/PL00011429
[28] 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 · Zbl 1052.90047 · doi:10.1023/A:1008325116400
[29] Li D. and Sun X.L. (2006). Towards strong duality in integer programming. J. Glob. Optim. 35: 255–282 · Zbl 1097.90068 · doi:10.1007/s10898-005-3838-0
[30] Li D. and White D.J. (2000). P-th power Lagrangian method for integer programming. Ann. Oper. Res. 98: 151–170 · Zbl 0990.90075 · doi:10.1023/A:1019252306512
[31] Marsten R.E. and Morin T.L. (1978). A hybrid approach to discrete mathematical programming. Math. Program. 14: 21–40 · Zbl 0388.90055 · doi:10.1007/BF01588949
[32] McCormick G.P. (1975). Computability of global solutions to factorable nonconvex programs: part I convex underestimating problems. Math. Program. 10: 147–175 · Zbl 0349.90100 · doi:10.1007/BF01580665
[33] Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067
[34] Parker, R.G., Rardin, R.L.: Discrete Optimization. Academic, Boston (1988) · Zbl 0652.90068
[35] Poljak S., Rendl F. and Wolkoswicz H. (1995). A recipe for semidefinite relaxation for 0-1 quadratic programming. J. Glob. Optim. 7: 51–73 · Zbl 0843.90088 · doi:10.1007/BF01100205
[36] Roelofs, M., Bisschop, J.: AIMMS user’s Guide. Paragon Decision Technology. http://www.aimms.com/aimms/download/manuals/AIMMS_ 3UG.pdf (2006)
[37] Ryoo H.S. and Sahinidis N.V. (2001). Analysis of bounds for multilinear functions. J. Glob. Optim. 19: 403–424 · Zbl 0982.90054 · doi:10.1023/A:1011295715398
[38] Ryoo H.S. and Sahinidis N.V. (2003). Global optimization of multilinear problems. J. Glob. Optim. 26: 387–418 · Zbl 1052.90091 · doi:10.1023/A:1024700901538
[39] 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)
[40] Shapiro J.F. (1979). A survey of lagrangian techniques for discrete optimization. Ann. Discrete Math. 5: 113–138 · Zbl 0411.90054 · doi:10.1016/S0167-5060(08)70346-7
[41] Sherali H.D. (1997). Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Math. Vietnam 22: 245–270 · Zbl 0914.90205
[42] Sherali H.D. (1998). Global optimization of nonconvex polynomial programming problems having rational exponents. J. Glob. Optim. 12: 267–283 · Zbl 0905.90146 · doi:10.1023/A:1008249414776
[43] Sherali H.D. and Wang H. (2001). Global optimization of nonconvex factorable programming problems. Math. Program. 89: 459–478 · Zbl 0985.90073 · doi:10.1007/PL00011409
[44] Smith E.M. and Pantelides C.C. (1997). Global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 21: S791–S796
[45] 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 · Zbl 0977.90028 · doi:10.1287/moor.25.4.625.12114
[46] 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 · Zbl 1035.90087 · doi:10.1023/A:1016541912439
[47] Taha H.A. (1972). A Balasian-based algorithm for zero-one polynomial programming. Manage. Sci. 18: B328–B343 · Zbl 0244.90029 · doi:10.1287/mnsc.18.6.B328
[48] 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) · Zbl 1031.90022
[49] Tawarmalani M. and Sahinidis N.V. (2004). Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math. Program. 99: 563–591 · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[50] Watters L.J. (1967). Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper. Res. 15: 1171–1174 · doi:10.1287/opre.15.6.1171
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.