Abstract.
This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a ‘‘central’’ dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce some modifications to ACCPM. We propose a new procedure to recover primal feasibility after adding cuts and use, for the first time, a dual Newton’s method to calculate the new analytic centre after branching. Second, we discuss the integration of ACCPM within the branch-and-price algorithm. We detail the use of ACCPM as the search goes deep in the branch and bound tree, making full utilization of past information as a warm start. We exploit dual information from ACCPM to generate incumbent feasible solutions and to guide branching. Finally, the overall approach is implemented and tested for the bin-packing problem and the capacitated facility location problem with single sourcing. We compare against Cplex-MIP 7.5 as well as a classical branch-and-price algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H.: Branch-and-price : column generation for solving huge integer programs. Oper. Res. 46, 316–329 (1998)
Den Hertog, D.: Interior point approach to linear quadratic and convex programming. Kluwer, London, 1994
Desrochers, M., Desrosiers, J., Solomon, M.: A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40, 342–354 (1992)
Desrochers, M., Desrosiers, J., Soumis, F.: A column generation approach to the urban transit crew scheduling problem. Transp. Sci. 23, 1–13 (1989)
Desaulniers, G., Desrosiers, J., Ioachim, I., Solomon, M.M., Soumis, F.: A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In: Crainic, T.G., Laporte, G., (eds.), Fleet Management and Logistics. Kluwer, Boston, MA, 1998, pp. 57–93
duMerle, O.: Interior points and cutting palnes: development and implementation of methods for convex optimization and large scale structured linear programming. Ph.D Thesis, Department of Management Studies, University of Geneva, Geneva, Switzerland, 1995 (in French)
duMerle, O., Hansen, P., Jaumard, B., Mladenovic, N.: An interior point algorithm for minimum sum of squares clustering. SIAM J. Sci. Comput. 21(4), 1485–1505
Falkenauer, E.: A Hybrid grouping genetic algorithm for bin-packing. Working paper CRIF Industrial Management and Automation. CP 50, 106–4 (1994)
Geoffrion, A.M.: Lagrangean relaxation for integer programming. Math. Program. Study 2, 82–114 (1974)
Goffin, J.-L., Haurie, A., Vial, J.-P.: Decomposition and nondifferentiable optimization with the projective algorithm. Manage. Sci. 38(2), 284–302 (1992)
Goffin, J.-L., Vial, J.-P.: Convex nondifferentiable optimization: a survey focussed on the analytic center cutting plane method. GERAD Tech. Report G-99–17 1999, p. 47
Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting stock problem. Oper. Res. 9, 849–859 (1961)
Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting stock problem: Part II. Oper. Res. 11, 863–888 (1963)
Goffin, J.-L., Luo, Z.-Q., Ye, Y.: Complexity Analysis of an Interior Cutting Plane Method for Convex Feasibility Problems. SIAM J. Optim. 6, 638–652 (1996)
Goffin, J.-L., Vial, J.-P.: Multiple cuts in the analytic center cutting plane method. SIAM J. Optim. 11(1), 266–288 (1999)
Goffin, J.-L., Vial, J.-P.: On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm. Math. program. 60, 81–92 (1993)
Gondzio, J.: Warm start of the primal-dual method applied in the cutting plane scheme. Math. program. 83, 125–143 (1998)
Holmberg, K., Ronnqvist, M., Yuan, D.: An exact algorithm for the capacitated facility location problem with single sourcing. Eur. J. Oper. Res. 113, 544–559 (1999)
Johnson, E.L., Nemhauser, G., Savelsbergh, M.W.P.: Progress in linear programming-based algorithms for integer programming. An exposition. Informs JOC 12(1), 1–23 (2000)
Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)
Kelley, J.E.: The cutting plane method for solving convex programs. J. SIAM 8, 703–712 (1960)
Klincewicz, J.G., Luss, H.: A Lagrangean relaxation heuristic for capacitated facility location with single-source constraints. J. Oper. Res. Soc. 37(5), 195–500 (1986)
Lemarechal, C.: Bundle Methods in Nonsmooth Optimization. Nonsmooth Optimization, Proceedings of the IIASA Workshop March 28 – April 8, 1977, Lemarechal, C., Mifflin, R., (eds.), Pergamon Press, 1978
Martello, S., Toth, P.: Knapsack problems: Algorithms and computer implementations. Wiley Interscience Series in Discrete Mathematics and Optimization, Wiley, New York, 1990
Mitchell, J.E., Todd, M.J.: Solving combinatorial optimization problems using Karmarkar’s algorithm. Math. Program. 56, 245–284 (1992)
Mitchell, J.E.: Computational experience with an interior point cutting plane algorithm. SIAM J. Optim. 10(4), 1212–1227 (2000)
Mitchell, J.E., Borchers, B.: Using an interior point method in a branch-and-bound algorithm for integer programming, 1991. Revised 1992, Rensselaer Polytechnic Institute, Troy, N.Y.
Mitchell, J.E., Pardalos, P., Resende, M.G.C.: Interior point methods for combinatorial optimization. Handbook of Combinatorial Optimization, Volume 1, Kluwer Academic Publishers, 1998, pp. 189–297
Neebe, A.W., Rao, M.R.: An algorithm for the fixed-charge assigning users to sources problem. J. Oper. Res. Soc. 34(11), 1107–1113 (1983)
Nemirovskii, A.S., Yudin, D.B.: Problem complexity and method efficiency in optimization. John Wiley, Chichester, 1983
Nesterov, Y.: Cutting plane methods from analytic centers: efficiency estimates. Math. program., Ser. B 69, 149–176 (1996)
Pirkul, H.: Efficient algorithms for the capacitated concentrator location problem. Comput. Oper. Res. 14(3), 197–208 (1987)
Ryan, D.M., Foster, B.A.: An integer programming approach to scheduling. In: Wren, A. (ed.), computer scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, North Holland, Amsterdam, 1981, pp. 169–280
Scholl, A., Klein, R., Jurgens, C.: Bison: a fast hybrid procedure for exactly solving the one-dimensional bin-packing problem. Comput. Oper. Res. 24, 667–645 (1997)
Sonnevend, G.: An analytical center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In: Lecture Notes in Control and Information Sciences 84, Springer, New York, 1985, pp. 866–876
Valerio de Carvalho, J.M.: Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res 86, 626–659 (1999)
Vance, P.H., Johnson, E.L., Nemhauser, G.L.: Solving binary cutting stock problems using column generation and branch-and-bound. Comput. Optim. Appl. 3, 111–130 (1994)
Vanderbeck, F., Wolsey, L.A.: An exact algorithm for IP column generation. Oper. Res. Lett. 19, 151–159 (1996)
Vanderbeck, F.: Computational study of a column generation algorithm for bin-packing and cutting stock problems. Math. Program. Ser. A 86, 565–594 (1999)
Vanderbeck, F.: On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48(1), 111–128 (2000)
Ye, Y.: Interior point algorithms: Theory and analysis. John Wiley & sons, 1997
Zhang, Y.: Solving Large Scale Linear Programs by Interior-Point Methods Under the Matlab Environment. Technical report TR96-01, university of Maryland Baltimore county, 1996
Author information
Authors and Affiliations
Corresponding author
Additional information
Mathematics Subject Classification (1991): 20E28, 20G40, 20C20
Rights and permissions
About this article
Cite this article
Elhedhli, S., Goffin, JL. The integration of an interior-point cutting plane method within a branch-and-price algorithm. Math. Program., Ser. A 100, 267–294 (2004). https://doi.org/10.1007/s10107-003-0469-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0469-4