×

Exact algorithm for the surrogate dual of an integer programming problem: Subgradient method approach. (English) Zbl 0911.90304

Summary: One of the critical issues in the effective use of surrogate relaxation for an integer programming problem is how to solve the surrogate dual within a reasonable amount of computational time. We present an exact and efficient algorithm for solving the surrogate dual of an integer programming problem. Our algorithm follows the approach which S. Sarin, M. H. Karwan and R. L. Rardin [Nav. Res. Logist. 34, No. 3, 431-450 (1987; Zbl 0656.90068)] introduced in their surrogate dual multiplier search algorithms. The algorithms of Sarin et al. adopt an ad-hoc stopping rule in solving subproblems and cannot guarantee the optimality of the solutions obtained. Our work shows that this heuristic nature can actually be eliminated. Convergence proof for our algorithm is provided. Computational results show the practical applicability of our algorithm.

MSC:

90C30 Nonlinear programming
49J52 Nonsmooth analysis

Citations:

Zbl 0656.90068
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dyer, M. E., Calculating Surrogate Constraints, Mathematical Programming. Vol. 19, pp. 255–278, 1980. · Zbl 0464.90067 · doi:10.1007/BF01581647
[2] Greenberg, H. J., and Pierskalla, W. P, Surrogate Mathematical Programming, Operations Research, Vol. 18, pp. 924–939, 1970. · Zbl 0232.90059 · doi:10.1287/opre.18.5.924
[3] Karwan, M. H., and Rardin, R. L., Some Relationships between Lagrangian and Surrogate Duality in Integer Programming, Mathematical Programming, Vol. 17, pp. 320–334, 1979. · Zbl 0421.90056 · doi:10.1007/BF01588253
[4] Glover, F., Surrogate Constraint Duality in Mathematical Programming, Operations Research, Vol. 23, pp. 434–451, 1975. · Zbl 0314.90093 · doi:10.1287/opre.23.3.434
[5] Ram, B., and Karwan, M. H., A Result in Surrogate Duality for Certain Integer Programming Problems, Mathematical Programming, Vol. 43, pp. 103–106, 1989. · Zbl 0675.90065 · doi:10.1007/BF01582282
[6] Gavish, B., and Pirkul, H., Efficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality, Mathematical Programming, Vol. 31, pp. 78–105, 1985. · Zbl 0571.90065 · doi:10.1007/BF02591863
[7] Karwan, M. H., and Rardin, R. L., Surrogate Dual Multiplier Search Procedures in Integer Programming, Operations Research, Vol. 32, pp. 52–69, 1984. · Zbl 0538.90060 · doi:10.1287/opre.32.1.52
[8] Sarin, S., Karwan, M. H., and Rardin, R. L., A New Surrogate Dual Multiplier Search Procedure, Naval Research Logistics, Vol. 34, pp. 431–450, 1987. · Zbl 0656.90068 · doi:10.1002/1520-6750(198706)34:3<431::AID-NAV3220340309>3.0.CO;2-P
[9] Polyak, B. T., Minimization of Unsmooth Functionals, USSR Computational Mathematics and Mathematical Physics, Vol. 9, pp. 14–29, 1969. · Zbl 0229.65056 · doi:10.1016/0041-5553(69)90061-5
[10] Camerini, P. M., Fratta, L., and Maffioli, F., On Improving Relaxation Methods by Modified Gradient Techniques, Mathematical Programming Study, Vol. 3, pp. 26–34, 1975. · Zbl 0357.90031 · doi:10.1007/BFb0120697
[11] Kim, S., Koh, S., and Ahn, H., Two-Direction Subgradient Method for Nondifferentiable Optimization Problems, Operations Research Letters, Vol. 6, pp. 43–46, 1987. · Zbl 0626.90066 · doi:10.1016/0167-6377(87)90008-3
[12] Kim, S., and Ahn, H., Convergence of a Generalized Subgradient Method for Nondifferentiable Convex Optimization, Mathematical Programming, Vol. 50, pp. 75–80, 1991. · Zbl 0722.90054 · doi:10.1007/BF01594925
[13] Kim, S., Ahn, H., and Cho, S.-C., Variable Target Value Subgradient Method, Mathematical Programming, Vol. 49, pp. 359–369, 1991. · Zbl 0825.90754 · doi:10.1007/BF01588797
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.