Ir al contenido

Documat

Neural benders decomposition for mixed-integer programming

  • Rahimeh Neamatian Monemi [4] ; Shahin Gelareh [1] ; Nelson Maculan [2] ; Yu-Hong Dai [3]
    1. [1] Artois University

      Artois University

      Arrondissement d’Arras, Francia

    2. [2] Universidade Federal do Rio de Janeiro

      Universidade Federal do Rio de Janeiro

      Brasil

    3. [3] University of Chinese Academy of Sciences

      University of Chinese Academy of Sciences

      China

    4. [4] Sharkey Predictim Globe, Villeneuve-d’Ascq, France
    Mostrar afiliaciones +
  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. 3, 2025, págs. 548-579
  • Idioma: inglés
  • DOI: 10.1007/s11750-024-00691-x
  • Enlaces
  • Resumen

    • In this study, we propose an imitation learning framework to enhance the Benders decomposition method. This work aims to learn how to select dual values when there is a choice to be made among alternatives. To attain this objective, we mimic successful experts via two policies. In the first one, we replicate a technique for selecting non-dominated dual solutions and learn from each iteration of Benders. In the second policy, our objective is to determine a trajectory that expedites the attainment of the final subproblem’s dual solution. This approach is can be applied on a specific (or a specific class of) problem. From among different problems on which this technique has been examined, we report computational experiments on two successful cases of real-world problems. Our results confirm that incorporating these learned policies significantly enhances the efficiency of the solution process, although the first policy often outperforms the second one.

  • Referencias bibliográficas
    • Amos B, Kolter JZ (2021) Optnet: differentiable optimization as a layer in neural networks. arXiv:1703.00443
    • Babaki B, Jena SD, Charlin L (2022) Neural column generation for capacitated vehicle routing. In: AAAI22 workshop on machine learning for...
    • Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs....
    • Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper Res 54:454–463
    • Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4:238–252
    • Benders J (2005) Partitioning procedures for solving mixed-variables programming problems. Comput Manag Sci 2:3–19
    • Bodur M, Luedtke JR (2017) Mixed-integer rounding enhanced benders decomposition for multiclass service-system staffing and scheduling with...
    • Bodur M, Dash S, Günlük O, Luedtke J (2017) Strengthened benders cuts for stochastic integer programs with continuous recourse. INFORMS J...
    • Borozan S, Giannelos S, Falugi P, Moreira A, Strbac G (2023) A machine learning-enhanced benders decomposition approach to solve the transmission...
    • Bruna J, Zaremba W, Szlam A, Lecun Y (2014) Spectral networks and locally connected networks on graphs. In: International conference on learning...
    • Cartis C, Nicholas IMG (2009) Finding a point in the relative interior of a polyhedron, with applications to compressed sensing. In: Gribonval...
    • Codato G, Fischetti M (2006a) Combinatorial Benders’ cuts for mixed-integer linear programming. Oper Res 54:756
    • Codato G, Fischetti M (2006b) Combinatorial benders’ cuts for mixed-integer linear programming. Oper Res 54:756–766. https://doi.org/10.1287/opre.1060.0286
    • Conforti M, Wolsey L (2018) âeœfacetâe separation with one linear program. Math Program 178. https:// doi.org/10.1007/s10107-018-1299-8
    • Danach K, Gelareh S, Neamatian Monemi R (2019) The capacitated single-allocation p-hub location routing problem: a lagrangian relaxation and...
    • Ding JY, Zhang C, Shen L, Li S, Wang B, Xu Y, Song L (2019) Accelerating primal solution findings for mixed integer programs based on solution...
    • Du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math 194:229–237
    • Fischetti M, Salvagnin D, Zanette A (2010) A note on the selection of benders’ cuts. Math Program 124:175–182. https://doi.org/10.1007/s10107-010-0365-7
    • Fischetti M, Ljubi´c I, Sinnl M (2016) Benders decomposition without separability: a computational study for capacitated facility location...
    • Frangioni A (2002) Generalized bundle methods. SIAM J Optim 13:117–156
    • Gasse M, Chételat D, Ferroni N, Charlin L, Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Curran...
    • Geoffrion A (1972) Generalized benders decomposition. J Optim Theory Appl 10:237–260. https://doi.org/ 10.1007/BF00934810
    • Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper Res 9:849–859
    • Gondzio J, González-Brevis P (2015) A new warmstarting strategy for the primal-dual column generation method. Math Program 152:113–146
    • Gondzio J, González-Brevis P, Munari P (2013) New developments in the primal-dual column generation technique. Eur J Oper Res 224:41–51
    • Gondzio J, González-Brevis P, Munari P (2016) Large-scale optimization with the primal-dual column generation method. Math Program Comput...
    • Gori M, Monfardini G, Scarselli F (2005) A new model for earning in raph domains, vol 2, pp 729–734. https://doi.org/10.1109/IJCNN.2005.1555942
    • Gschwind T, Irnich S (2016) Dual inequalities for stabilized column generation revisited. INFORMS J Comput 28:175–194
    • Hooker J, Ottosson G (2003) Logic-based benders’ decomposition. Math Program Ser B 96:33–60. https:// doi.org/10.1007/s10107-003-0375-9
    • Hosseini M, Turner J (2021) Deepest cuts for benders decomposition. arXiv:2110.08448
    • Jia H, Shen S (2021) Benders cut classification via support vector machines for solving two-stage stochastic programs. INFORMS J Optim 3:278–297
    • Keuper M, Lukasik J, Singh M, Yarkony J (2019) Massively parallel benders decomposition for correlation clustering. arXiv preprint arXiv:1902.05659
    • Kingma DP, Ba J, (2014) Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980
    • Lee M, Ma N, Yu G, Dai H (2020) Accelerating generalized benders decomposition for wireless resource allocation. IEEE Trans Wirel Commun 20:1233–1247
    • Lokhande VS, Wang S, Singh M, Yarkony J (2020) Accelerating column generation via flexible dual optimal inequalities with application to entity...
    • Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper Res 53:1007–1023
    • Magnanti T, Wong R (1981) Accelerating Benders decomposition: algorithmic enhancement and model selection criteria. Oper Res 29:464–484
    • Mak S, Mana K, Zehtabi P, Cashmore M, Magazzeni D, Veloso M (2023) Towards accelerating benders decomposition via reinforcement learning surrogate...
    • Marsten RE, Hogan WW, Blankenship JW (1975) The boxstep method for large-scale optimization. Oper Res 23:389–405
    • Meurdesoif OBL, Vanderbeck SMP (2005) Comparison of bundle and classical column generation
    • Neamatian Monemi R, Gelareh S, Maculan N (2023) A machine learning based branch-cut-and-benders for dock assignment and truck scheduling problem...
    • Papadakos N (2008) Practical enhancements to the Magnanti–Wong method. Oper Res Lett 36:444–449
    • Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column...
    • Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The benders decomposition algorithm: A literature review. Eur J Oper Res 259:801–817
    • Rousseau LM, Gendreau M, Feillet D (2007) Interior point stabilization for column generation. Oper Res Lett 35:660–668
    • Saharidis GK, Ierapetritou MG (2010) Improving benders decomposition using maximum feasible subsystem (MFS) cut generation strategy. Comput...
    • Scarselli F, Gori M, Tsoi AC, Hagenbuchner M, Monfardini G (2009) The graph neural network model. IEEE Trans Neural Netw 20:61–80. https://doi.org/10.1109/TNN.2008.2005605
    • Sherali HD, Lunday BJ (2013) On generating maximal nondominated benders cuts. Ann Oper Res 210:57– 72. https://api.semanticscholar.org/CorpusID:26374786
    • Van Ackooij W, Frangioni A (2018) Incremental bundle methods using upper models. SIAM J Optim 28:379–410
    • Wang S, Ihler A, Kording K, Yarkony J (2018) Accelerating dynamic programs via nested benders decomposition with application to multi-person...
    • Zakeri G, Philpott AB, Ryan DM (2000) Inexact cuts in benders decomposition. SIAM J Optim 10:643–657. https://doi.org/10.1137/S1052623497318700
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno