Column-Generation in Integer Linear Programming

Nelson Maculan; Marcos de Mendonça Passini; José André de Moura Brito; Irene Loiseau

RAIRO - Operations Research (2010)

  • Volume: 37, Issue: 2, page 67-83
  • ISSN: 0399-0559

Abstract

top
We present an exact method for integer linear programming problems that combines branch and bound with column generation at each node of the search tree. For the case of models involving binary column vectors only, we propose the use of so-called geometrical cuts to be added to the subproblem in order to eliminate previously generated columns. This scheme could be applied to general integer problems without specific structure. We report computational results on a successful application of this approach to a telecommunications network planning problem.

How to cite

top

Maculan, Nelson, et al. "Column-Generation in Integer Linear Programming." RAIRO - Operations Research 37.2 (2010): 67-83. <http://eudml.org/doc/105283>.

@article{Maculan2010,
abstract = { We present an exact method for integer linear programming problems that combines branch and bound with column generation at each node of the search tree. For the case of models involving binary column vectors only, we propose the use of so-called geometrical cuts to be added to the subproblem in order to eliminate previously generated columns. This scheme could be applied to general integer problems without specific structure. We report computational results on a successful application of this approach to a telecommunications network planning problem. },
author = {Maculan, Nelson, Marcos de Mendonça Passini, José André de Moura Brito, Loiseau, Irene},
journal = {RAIRO - Operations Research},
keywords = {Column-generation; integer programming; branch-and-price.; column generation; integer programming; branch-and-price},
language = {eng},
month = {3},
number = {2},
pages = {67-83},
publisher = {EDP Sciences},
title = {Column-Generation in Integer Linear Programming},
url = {http://eudml.org/doc/105283},
volume = {37},
year = {2010},
}

TY - JOUR
AU - Maculan, Nelson
AU - Marcos de Mendonça Passini
AU - José André de Moura Brito
AU - Loiseau, Irene
TI - Column-Generation in Integer Linear Programming
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 2
SP - 67
EP - 83
AB - We present an exact method for integer linear programming problems that combines branch and bound with column generation at each node of the search tree. For the case of models involving binary column vectors only, we propose the use of so-called geometrical cuts to be added to the subproblem in order to eliminate previously generated columns. This scheme could be applied to general integer problems without specific structure. We report computational results on a successful application of this approach to a telecommunications network planning problem.
LA - eng
KW - Column-generation; integer programming; branch-and-price.; column generation; integer programming; branch-and-price
UR - http://eudml.org/doc/105283
ER -

References

top
  1. R. Anbil, J. Forrest and W. Pulleyblank, Column generation and the airline crew pairing problem. DOC. Math. J. DMV (1998) 677-686.  Zbl0904.90082
  2. C. Barnhart, C. Hanne and P.H. Vance, Using branch-and-price and cut to solve origin destination integer multicommodity flow problems. Oper. Res.48 (2000) 318-326.  
  3. C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh and P.H. Vance, Branch-and-price: Column generation for solving huge integer programs. Oper. Res.46 (1998) 316-329.  Zbl0979.90092
  4. R. Borndorfer, M. Grotschel and A. Lobel, Scheduling duties by adptive column generation. ZIB-Report 01-02 (2001).  
  5. J. Bourjolly, G. Laporte and H. Mercure, A combinatorial column generation algorithm for the maximun stable set problem. Oper. Res. Lett. (1997).  Zbl0892.90176
  6. J.A.M. Brito, Um modelo de otimizaç ao para dimensionamento de uma rede de telecomunicaç oes, Tese de mestrado, COPPE. Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brasil (1999).  
  7. J. Bramel and D. Simchi-Levi, On the effectiveness of set covering formulations for the vehicle routing problem with time windows. Oper. Res.45 (1997) 295-301.  Zbl0890.90054
  8. S. Butt and D.M. Ryan, An optimal solution procedure for the multiple tour maximum collec tion problem using column generation. Comp. Oper. Res.26 (1999) 427-441.  Zbl0951.90007
  9. Z. Chen and W. Powell, A column generation based descomposition algorithm for a parallel machine scheduling problem. EJOR116 (1999) 220-232.  Zbl1009.90040
  10. V. Chvátal, Linear programming. W.H. Freeman and Company, New York, San Francisco (1983).  
  11. Y. Crama and J. Van de Klundert, Approximation algorithms for integer covering problems via greedy column generation. RAIRO: Oper. Res.28 (1994) 283-302.  Zbl0830.90107
  12. R. Dakin, A tree search algorithm for mixed integer programming problems. Comput. J.8 (1965) 250-255.  Zbl0154.42004
  13. G.B. Dantzig, Upper bounds, secondary constraints and block triangulary in linear programming. Econometrica23 (1995) 174-183.  Zbl0064.39501
  14. G.B. Dantzig, Linear programming and extensions. Princeton University Press, New Jersey, USA (1963).  
  15. G.B. Dantzig and P. Wolfe, Decomposition principle for linear programming. Oper. Res.8 (1960) 101-111.  Zbl0093.32806
  16. J.M.V. de Carvalho, Exact solution of cutting stock problems using column generation and branch-and-bound. Int. Trans. Oper. Res.5 (1998) 35-43.  Zbl0911.90281
  17. J. Delorme, Contributions à la résolution du problème de recouvrement : méthode de troncature, Docteur-ingenieur dissertation. Université Paris VI, Paris, France (1974).  
  18. G. Desaulniers, J. Desrosiers and M. Solomon, Accelerating strategies in Column Generation methods for vehicle routing and crew scheduling. Cahiers du Gerad G-99-36 (1999).  Zbl1017.90045
  19. G. Desaulniers, J. Desrosiers, Y. Dumas and M. Solomon, Daily Aircraft routing and Scheduling. Cahiers du Gerad G-94-21 (1994).  
  20. G. Desaulniers, J. Desrosiers and M. Solomon, Accelerating strategies in Column Generation Methods for Vehicle Routing and crew scheduling problems. Cahiers du Gerad G-99-36 (1994).  Zbl1017.90045
  21. M. Desrochers, J. Desrosiers and M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res.40 (1992) 342-353.  Zbl0749.90025
  22. J. Desrosiers, Y. Dumas, M.N. Solomon and F. Soumis, Time constrained routing and scheduling, edited by M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser, Network Routing. INFORMS - North Holland, Handbooks Oper. Res. Management Sci. 8 (1995) 35-139.  Zbl0861.90052
  23. J. Desrochers and F. Soumis, A column-generation approach to the urban transit crew scheduling problem. Transportation Sci.23 (1989) 1-13.  Zbl0668.90043
  24. J. Desrosiers, F. Soumis and M. Desrochers, Routing with time-windows by column generation. Networks14 (1984) 545-565.  Zbl0571.90088
  25. M. EbenChaime, C. Tovey and J.C. Ammons, Circuit partitioning via set partitioning and column generation. Oper. Res.44 (1996) 65-76.  Zbl0847.90095
  26. M. Gamache, F. Soumis, G. Marquis and J. Desrosiers, A column generation approach for large-scale aircrew rostering problems. Oper. Res.48 (1992) 247-263.  Zbl1041.90513
  27. P.C. Gilmore and R.E. Gomory, A linear programming approach to the cutting stock problem. Oper. Res.9 (1961) 849-859.  Zbl0096.35501
  28. P.C. Gilmore and R.E. Gomory, A linear programming approach to the cutting stock problem - Part II. Oper. Res.11 (1963) 863-888.  Zbl0124.36307
  29. P. Hansen, B. Jaumard and M.V. Poggi de Arag ao, Un algorithme primal de programmation linéaire généralisée pour les programmes mixtes. C. R. Acad. Sci. Paris Sér. I Math.313 (1991) 557-560.  
  30. B. Jaumard, P. Labit and C. Ribeiro, A Column Generation Aproach to Cell Formation Problems in Cellular Manufacturing. Cahiers du Gerad G-99-20 (1999).  
  31. B. Jaumard, C. Meyer and T. Vovor, How to combine a column and row generation method with a column or row elimination procedures - Application to a channel Assiggnment problem. Cahiers du Gerad G-99-18 (1999).  
  32. B. Jaumard, C. Meyer and T. Vovor, Column/Row Generation and Elimination Methods. Cahiers du Gerad G-99-34 (1999).  
  33. E. Johnson, A. Mehrotal and G.L. Nemhauser, Min-cut clustering. Math. Programming62 (1993) 133-152.  Zbl0807.90117
  34. L. Kroon and M. Fischetti, Crew Scheduling for Netherlands Railways ``Destination Customer" (2001).  Zbl0989.90516
  35. L.S. Lasdon, Optimization Theory for Large Systems. Macmillan, New York, USA (1970).  Zbl0224.90038
  36. A. Lobel, Vehicle scheduling in public transit and Lagrangian pricing. Management Sci.44 (1998) 1637-1649.  Zbl0989.90024
  37. O. Marcotte, The cutting stock problem and integer rounding. Math. Programming13 (1985) 82-92.  Zbl0584.90063
  38. N. Maculan, M. Fampa and P. Michelon, Programaç ao linear e inteira. Notes - COPPE/Universidade Federal do Rio de Janeiro (1999).  
  39. N. Maculan, P. Michelon and G. Plateau, Column generation in linear programming with bounding variable constraints and its applications in integer programming. Pesquisa Operacional12 (1992) 45-57.  
  40. N. Maculan, M.M. Passini, J.A.M. Brito and A. Lisser, Column generation method for network design, Transportation and Network Analysis Current Trends, edited by M. Gendreau and P. Marcotte. Kluwer Academic Publishers (2002) 165-179.  Zbl1048.90046
  41. A. Mehrotra and M. Trick, A column generation approach for graph coloring. INFORMS J. Comput.8 (1996) 344-353.  Zbl0884.90144
  42. M. Minoux, Optimal traffic assignment in a SS/TDMA frame: A new approach by set covering and column generation. RAIRO: Oper. Res.20 (1986) 273-286.  Zbl0608.90076
  43. M. Minoux, A class of combinatorial problems with polynomially solvable large scale set covering/partioning relaxations. RAIRO: Oper. Res.21 (1987) 105-136.  Zbl0644.90061
  44. G.L. Nemhauser and S. Park, A polyhedral approach to edge coloring. Oper. Res. Lett.10 (1991) 315-322.  Zbl0754.90062
  45. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization. John Wiley & Sons Inc. (1988).  Zbl0652.90067
  46. M.M. Passini, Um modelo de otimizaç ao combinatória para o dimensionamento de uma rede urbana de telecomunicaç oes, M.Sc. Thesis. COPPE, Universidade Federal do Rio de Janeiro (1996).  
  47. D.M. Ryan and B.A. Foster, An integer programming approach to scheduling, in Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling. North Holland (1981).  
  48. C. Ribeiro, M. Minoux and M.C. Penna, An optimal column-generation-with-ranking algorithm for very large scale partitioning problems in traffic assignment. Eur. J. Oper. Res.41 (1989) 232-239.  Zbl0679.90043
  49. C. Ribeiro and F. Soumis, A column generation approach to the multiple-depot vehicle scheduling problem. Oper. Res.42 (1994) 41-52.  Zbl0798.90038
  50. M. Savelsbergh, A branch-and-price algorithm for the generalized assignment problem. Oper. Res.46 (1997) 831-841.  Zbl0895.90161
  51. L.G. Simonetti, Geraç ao de colunas para o problema de empacotamento de árvores de Steiner, M.Sc. dissertation. Universidade Federal do Rio de Janeiro (2003).  
  52. A. Sutter, F. Vanderbeck and L. Wolsey, Optimal placemente of add/drop multiplexers: Heuristic and exact algorithms. Oper. Res.46 (1998) 719-728.  Zbl0987.90014
  53. E.D. Taillard, A heuristic generation method for the heterogeneous fleet VRP. RAIRO: Oper. Res.33 (1999) 1-14.  Zbl0992.90008
  54. F. Vanderbeck, Decomposition and Column Generation for Integer Programming, Thèse de doctorat en Sciences Appliquées. Université Catholique de Louvain, Louvain, Belgique (1994).  
  55. P.H. Vance, Branch-and-price algorithms for the one-dimensional cutting stock problem. Comput. Optim. Appl.9 (1998) 211-228.  Zbl0897.90161
  56. P.H. Vance, C. Barnhart, E.L. Johnson and G.L. Nemhauser, Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. Appl.3 (1994) 111-130.  Zbl0801.90080
  57. P.H. Vance, C. Barnhart, E.L. Johnson and G.L. Nemhauser, Airline crew scheduling: A new formulation and decomposition algorithm. Oper. Res.45 (1997) 188-200.  Zbl0891.90087
  58. F. Vanderbeck, Computational study of a column generation algorithm for bin packing and cut stocking problems. Math. Programming86 (1999) 565-594.  Zbl0949.90066
  59. F. Vanderbeck, On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res.48 (2000) 111-128.  Zbl1106.90360
  60. J.M. Van den Akker, J.A. Hoogeveen and S.L. van de Velde, Parallel machine scheduling by column generation. Oper. Res.47 (1999) 862-872.  Zbl0979.90051
  61. F. Vanderbeck and L. Wolsey, An exact algorithm for IP column generation. Oper. Res. Lett.19 (1996) 151-159.  Zbl0873.90074

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.