×

zbMATH — the first resource for mathematics

New bundle methods for solving Lagrangian relaxation dual problems. (English) Zbl 1015.90089
Summary: Bundle methods have been used frequently to solve nonsmooth optimization problems. In these methods, subgradient directions from past iterations are accumulated in a bundle, and a trial direction is obtained by performing quadratic programming based on the information contained in the bundle. A line search is then performed along the trial direction, generating a serious step if the function value is improved by \(\varepsilon\) or a null step otherwise. Bundle methods have been used to maximize the nonsmooth dual function in Lagrangian relaxation for integer optimization problems, where the subgradients are obtained by minimizing the performance index of the relaxed problem. This paper improves bundle methods by making good use of near-minimum solutions that are obtained while solving the relaxed problem. The bundle information is thus enriched, leading to better search directions and less number of null steps. Furthermore, a simplified bundle method is developed, where a fuzzy rule is used to combine linearly directions from near-minimum solutions, replacing quadratic programming and line search. When the simplified bundle method is specialized to an important class of problems where the relaxed problem can be solved by using dynamic programming, fuzzy dynamic programming is developed to obtain efficiently near-optimal solutions and their weights for the linear combination. This method is then applied to job shop scheduling problems, leading to better performance than previously reported in the literature.

MSC:
90C56 Derivative-free methods and methods using generalized derivatives
90C46 Optimality conditions and duality in mathematical programming
90B36 Stochastic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] GEOFFRION, M., Lagrangian Relaxation for Integer Programming, Mathematical Programming Studies, North Holland, Amsterdam, Netherlands, pp. 82-114, 1974.
[2] BERTSEKAS, D. P., Nonlinear Programming, 2nd Edition, Athena Scientific, Belmont, Massachusetts, 1999.
[3] ZHAO, X., LUH, P. B., and WANG, J., Surrogate Gradient Algorithm for Lagrangian Relaxation, Journal of Optimization Theory and Applications, Vol. 100, pp. 699-712, 1999. · Zbl 0949.90065 · doi:10.1023/A:1022646725208
[4] KASKAVELIS, C. A., and CARAMANIS, M. C., Efficient Lagrangian Relaxation Algorithms for Industry Size Job-Shop Scheduling Problems, IIE Transactions, Vol. 30, pp. 1085-1097, 1998.
[5] HIRIART-URRUTY, J. B., and LEMARECHAL, C., Convex Analysis and Minimization Algorithms, Vols. 1 and 2, Springer Verlag, Berlin, Germany, 1993.
[6] NEMHAUSER, G., and WOLSEY, L., Integer and Combinatorial Optimization, John Wiley and Sons, New York, NY, 1988. · Zbl 0652.90067
[7] HELD, M., WOLFE, P., and CROWDER, H., Validation of Subgradient Optimization, Mathematical Programming, Vol. 6, pp. 62-88, 1974. · Zbl 0284.90057 · doi:10.1007/BF01580223
[8] KIWIEL, K. C., Restricted Step and Levenberg-Marquardt Techniques in Proximal Bundle Methods for Nonconvex Nondifferentiable Optimization, SIAM Journal on Optimization, Vol. 6, pp. 227-249, 1996. · Zbl 0846.65028 · doi:10.1137/0806013
[9] KOHL, N. and MADSEN, O. B. G., An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation, Operations Research, Vol. 45, pp. 395-406, 1997. · Zbl 0890.90059 · doi:10.1287/opre.45.3.395
[10] MIFFLIN, R., SUN, D., and QI, L., Quasi-Newton Bundle-Type Methods for Nondifferentiable Convex Optimization, SIAM Journal on Optimization, Vol. 8, pp. 583-603, 1998. · Zbl 0927.65074 · doi:10.1137/S1052623496303329
[11] WANG, J., LUH, P. B., ZHAO, X., and WANG, J., An Optimization-Based Algorithm for Job Shop Scheduling, Sadhana, Vol. 22, pp. 241-256, 1997. · doi:10.1007/BF02744491
[12] BELLMAN, R., Applied Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1957. · Zbl 0077.13605
[13] KIWIEL, K. C., Proximal Level Bundle Methods for Convex Nondifferentiable Optimization, Saddle-Point Problems, and Variational Inequalities, Mathematical Programming, Vol. 69, pp. 89-109, 1995. · Zbl 0857.90101
[14] HOITOMT, D. J., LUH, P. B., and PATTIPATI, K. R., A Practical Approach to Job Shop Scheduling Problems, IEEE Transactions on Robotics and Automation, Vol. 9, pp. 1-13, 1993. · doi:10.1109/70.210791
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.