×

zbMATH — the first resource for mathematics

Branching in branch-and-price: A generic scheme. (English) Zbl 1229.90100
Summary: Developing a branching scheme that is compatible with the column generation procedure can be challenging. Application specific and generic schemes have been proposed in the literature, but they have their drawbacks. One generic scheme is to implement standard branching in the space of the compact formulation to which the Dantzig-Wolfe reformulation was applied. However, in the presence of multiple identical subsystems, the mapping to the original variable space typically induces symmetries. An alternative, in an application specific context, can be to expand the compact formulation to offer a wider choice of branching variables. Other existing generic schemes for use in branch-and-price imply modifications to the pricing problem. This is a concern because the pricing oracle on which the method relies might become obsolete beyond the root node. This paper presents a generic branching scheme in which the pricing oracle of the root node remains of use after branching (assuming that the pricing oracle can handle bounds on the subproblem variables). The scheme does not require the use of an extended formulation of the original problem. It proceeds by recursively partitioning the subproblem solution set. Branching constraints are enforced in the pricing problem instead of being dualized via Lagrangian relaxation, and the pricing problem is solved by a limited number of calls to the pricing oracle. This generic scheme builds on previously proposed approaches and unifies them. We illustrate its use on the cutting stock and bin packing problems. This is the first branch-and-price algorithm capable of solving such problems to integrality without modifying the subproblem or expanding its variable space.

MSC:
90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barnhart C., Hane C.A., Vance P.H.: Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. 48(2), 318–326 (2000)
[2] Barnhart C., Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P., Vance P.H.: Branch-and-price: column generation for huge integer programs. Oper. Res. 46, 316–329 (1998) · Zbl 0979.90092
[3] Belov, G., Letchford, A.N., Uchoa, E.: A node-flow model for the 1D stock cutting: Robust branch-cut-and-price. Tech. report RPEP, vol. 5, no. 7. Universidade Federal Fluminense (2005)
[4] Briant O., Lemaréchal C., Meurdesoif Ph., Michel S., Perrot N., Vanderbeck F.: Comparison of bundle and classical column generation. Math. Progr. 113(2), 299–344 (2008) · Zbl 1152.90005
[5] Chabrier, A.: Génération de Colonnes et de Coupes utilisant des sous-problèmes de plus court chemin. Thèse de doctorat, Université d’Angers (2003)
[6] Desaulniers, G., Desrosiers, J., Langevin, A., Marcotte, O., Savard, G., Soumis, F., Solomon, M.: GENCOL, a mathematical optimizer. http://www.crt.umontreal.ca/\(\sim\)gencol/gceng.html (1990)
[7] Eisenbrand F., Shmonin G.: Carathéodory bounds for integer cones. Oper. Res. Lett. 34(5), 564–568 (2006) · Zbl 1152.90662
[8] Gendreau, M., Dejaxm, P., Feillet, D., Gueguen, C.: Vehicle routing with time windows and split deliveries, Working Paper (2005)
[9] Geoffrion A.: Lagrangian relaxation for integer programming. Math. Prog. St. 2, 82–114 (1974) · Zbl 0395.90056
[10] Horowitz E., Sahni S.: Computing partitions with applications to the knapsack problem. J. ACM 21, 277–292 (1974) · Zbl 0329.90046
[11] Ladányi L., Ralphs T.K., Trotter L.E. Jr: Branch, cut, and price: sequential and parallel. In: Jünger, M., Naddef, D. (eds) Computational Combinatorial Optimization, pp. 223–269. Springer, New York (1998) · Zbl 1052.90107
[12] Parker M., Ryan D.M.: A column generation algorithm for brandwidth packing. Telecommun. Syst. 2, 185–195 (1994)
[13] Puchinger, J., Stuckey, P.J., Wallace, M., Brand, S.: From high-level model to branch-and-price solution in G12. CPAIOR 2008, The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, vol. 5015 of LNCS, pp. 218–232. Springer, New York (2008) · Zbl 1142.90503
[14] Ryan, D.M., Foster, B.A.: An integer programming approach to scheduling. In: Wren, A. (eds.) Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, pp. 269–280. North-Holland (1981)
[15] Savelsbergh, M.W.P., Nemhauser, G.L.: Functional description of MINTO, a mixed INTeger optimizer. Report COC-91-03A, Georgia Institute of Technology, Atlanta (1993) · Zbl 0806.90095
[16] Thienel, S.: ABACUS–a branch-and-cut system. Ph.D. Thesis, Universität zu Köln (1995) · Zbl 0911.90282
[17] Valério de Carvalho J.: Exact solution of bin packing problems using column generation and branch-and-bound. Ann. Oper. Res 86, 629–659 (1999) · Zbl 0922.90113
[18] Vance P.H.: Branch-and-price algorithms for the one-dimensional cutting stock problem. Comput. Optim. Appl. 9(3), 211–228 (1998) · Zbl 0897.90161
[19] Vanderbeck F.: Computational study of a column generation algorithm for bin packing and cutting stock problems. Math. Prog. 86, 565–594 (1999) · Zbl 0949.90066
[20] Vanderbeck F.: On Dantzig–Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48, 111–128 (2000) · Zbl 1106.90360
[21] Vanderbeck F.: Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem. Oper. Res. 48, 915–926 (2000) · Zbl 1106.90373
[22] Vanderbeck F.: Extending Dantzig’s bound to the bounded multi-class binary knapsack problem. Math. Prog. 94(1), 125–136 (2002) · Zbl 1023.90054
[23] Vanderbeck F.: Implementing mixed integer column generation. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds) Column Generation, Kluwer, Dordrecht (2005) · Zbl 1246.90108
[24] Vanderbeck, F.: BaPCod–a generic branch-and-price code. depot APP 08-120018-000 IDDN (2008). http://wiki.bordeaux.inria.fr/realopt/
[25] Vanderbeck F., Savelsbergh M.W.P.: A Generic view of Dantzig–Wolfe decomposition in mixed integer programming. Oper. Res. Let. 34(3), 296–306 (2006) · Zbl 1109.90062
[26] Villeneuve D., Desrosiers J., Lübbecke M.E., Soumis F.: On compact formulations for integer programs solved by column generation. Ann. Oper. Res. 139(1), 375–388 (2005) · Zbl 1091.90052
[27] Xpress-MP: User guide and reference manual, release 18.10. Dash Optim. (2007)
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.