Benders Cut Classification via Support Vector Machines for Solving Two-Stage Stochastic Programs

References

• Akinc U , Khumawala BM (1977) An efficient branch and bound algorithm for the capacitated warehouse location problem. Management Sci. 23(6):585–594.Link, Google Scholar
• Baltean-Lugojan R , Bonami P , Misener R , Tramontani A (2019) Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. Accessed January 14, 2021, http://www.optimization-online.org/DB_HTML/2018/11/6943.html.Google Scholar
• Beasley JE (1988) An algorithm for solving large capacitated warehouse location problems. Eur. J. Oper. Res. 33(3):314–325.Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1):238–252.Google Scholar
• Binato S , Pereira MVF , Granville S (2001) A new Benders decomposition approach to solve power transmission network design problems. IEEE Trans. Power Systems 16(2):235–240.Google Scholar
• Birge JR , Louveaux F (2011) Introduction to Stochastic Programming (Springer, New York).Google Scholar
• Cai X , McKinney DC , Lasdon LS , Watkins DW Jr (2001) Solving large nonconvex water resources management models using generalized Benders decomposition. Oper. Res. 49(2):235–245.Link, Google Scholar
• Christofides N , Beasley JE (1983) Extensions to a Lagrangean relaxation approach for the capacitated warehouse location problem. Eur. J. Oper. Res. 12(1):19–28.Google Scholar
• Cordeau J-F , Stojković G , Soumis F , Desrosiers J (2001) Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Sci. 35(4):375–388.Link, Google Scholar
• Cortes C , Vapnik V (1995) Support-vector networks. Machine Learn. 20(3):273–297.Google Scholar
• Costa AM (2005) A survey on Benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32(6):1429–1450.Google Scholar
• Crainic TG , Frangioni A , Gendron B (2001) Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Appl. Math. 112(1–3):73–99.Google Scholar
• Crainic TG , Hewitt M , Rei W (2014) Partial decomposition strategies for two-stage stochastic integer programs . Report CIRRELT-2014-13, CIRRELT, Montréal.Google Scholar
• Crainic TG , Fu X , Gendreau M , Rei W , Wallace SW (2011) Progressive hedging-based metaheuristics for stochastic network design. Networks 58(2):114–124.Google Scholar
• Dashti H , Conejo AJ , Jiang R , Wang J (2016) Weekly two-stage robust generation scheduling for hydrothermal power systems. IEEE Trans. Power Systems 31(6):4554–4564.Google Scholar
• Federgruen A , Zipkin P (1984) A combined vehicle routing and inventory allocation problem. Oper. Res. 32(5):1019–1037.Link, Google Scholar
• Gendron B , Scutellà MG , Garroppo RG , Nencioni G , Tavanti L (2016) A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks. Eur. J. Oper. Res. 255(1):151–162.Google Scholar
• Geoffrion AM , Graves GW (1974) Multicommodity distribution system design by Benders decomposition. Management Sci. 20(5):822–844.Link, Google Scholar
• He H , Daume H III , Eisner JM (2014) Learning to search in branch and bound algorithms. Ghahramani Z , Welling M , Cortes C , Lawrence N , Weinberger KQ , eds. Advances in Neural Information Processing Systems , vol. 27 (Curran Associates, Red Hook, NY), 3293–3301.Google Scholar
• Holmberg K (1990) On the convergence of cross decomposition. Math. Programming 47(1–3):269–296.Google Scholar
• Hooker JN (2007) Planning and scheduling by logic-based Benders decomposition. Oper. Res. 55(3):588–602.Link, Google Scholar
• Khalil E , Dai H , Zhang Y , Dilkina B , Song L (2017) Learning combinatorial optimization algorithms over graphs. Guyon I , Luxburg UV , Bengio S , Wallach H , Fergus R , Vishwanathan S , Garnett R , eds. Advances in Neural Information Processing Systems , vol. 30 (Curran Associates, Red Hook, NY), 6348–6358.Google Scholar
• Khalil EB , Le Bodic P , Song L , Nemhauser GL , Dilkina BN (2016) Learning to branch in mixed integer programming. Schuurmans D , Wellman M , eds. Proc. 30th AAAI Conf. Artificial Intelligence (AAAI-16) (AAAI Press, Palo Alto, CA), 724–731.Google Scholar
• Kleywegt AJ , Shapiro A , Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Google Scholar
• Klibi W , Martel A (2012) Scenario-based supply chain network risk modeling. Eur. J. Oper. Res. 223(3):644–658.Google Scholar
• Klibi W , Martel A , Guitouni A (2010) The design of robust value-creating supply chain networks: A critical review. Eur. J. Oper. Res. 203(2):283–293.Google Scholar
• Kruber M , Lübbecke ME , Parmentier A (2017) Learning when to use a decomposition. Salvagnin D , Lombardi M , eds. Integration AI OR Techniques Constraint Programming : Internat. Conf. AI OR Techniques Constraint Programming Combin. Optim. Problems (Springer, Cham, Switzerland), 202–210.Google Scholar
• Laporte G , Louveaux FV , Mercure H (1994) A priori optimization of the probabilistic traveling salesman problem. Oper. Res. 42(3):543–549.Link, Google Scholar
• Magnanti TL , Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Melkote S , Daskin MS (2001) Capacitated facility location/network design problems. Eur. J. Oper. Res. 129(3):481–495.Google Scholar
• Minoux M (1986) Mathematical Programming: Theory and Algorithms (John Wiley & Sons, Chichester, UK).Google Scholar
• Misra S , Roald L , Ng Y (2019) Learning for constrained optimization: Identifying optimal active constraint sets. Preprint, submitted January 16, https://arxiv.org/abs/1802.09639v4.Google Scholar
• Naoum-Sawaya J , Elhedhli S (2013) An interior-point Benders based branch-and-cut algorithm for mixed integer programs. Ann. Oper. Res. 210(1):33–55.Google Scholar
• Orchard-Hays W (1968) Advanced Linear-Programming Computing Techniques (McGraw-Hill, New York).Google Scholar
• Pomerleau DA (1991) Efficient training of artificial neural networks for autonomous navigation. Neural Comput. 3(1):88–97.Google Scholar
• Rahmaniani R , Crainic TG , Gendreau M , Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Google Scholar
• Raidl GR (2015) Decomposition based hybrid metaheuristics. Eur. J. Oper. Res. 244(1):66–76.Google Scholar
• Reddy S , Dragan AD , Levine S (2019) SQIL: Imitation learning via regularized behavioral cloning. Accessed January 14, 2021, https://arxiv.org/abs/1905.11108v1.Google Scholar
• Ross S , Gordon G , Bagnell D (2011) A reduction of imitation learning and structured prediction to no-regret online learning. Gordon G , Dunson D , Dudík M , eds. Proc. 14th Internat. Conf. Artificial Intelligence Statist., vol. 15 (JMLR Workshop and Conference Proceedings, Fort Lauderdale, FL), 627–635.Google Scholar
• Saravanan B , Das S , Sikri S , Kothari D (2013) A solution to the unit commitment problem—A review. Frontiers Energy 7(2):223–236.Google Scholar
• Smola AJ , Schölkopf B (2004) A tutorial on support vector regression. Statist. Comput. 14(3):199–222.Google Scholar
• Song Y , Luedtke JR , Küçükyavuz S (2014) Chance-constrained binary packing problems. INFORMS J. Comput. 26(4):735–747.Link, Google Scholar
• Tang Y , Agrawal S , Faenza Y (2020) Reinforcement learning for integer programming: Learning to cut. International Conference on Machine Learning (PMLR), 9367–9376.Google Scholar
• Vapnik V (1998) Statistical Learning Theory: 1998 , Vol. 3 (John Wiley & Sons, New York).Google Scholar
• Vapnik VN (1999) An overview of statistical learning theory. IEEE Trans. Neural Networks 10(5):988–999.Google Scholar
• Vapnik V (2013) The Nature of Statistical Learning Theory ( Springer, New York).Google Scholar
• Wolfe P (1970) Convergence theory in nonlinear programming. Abadie J , ed. Integer and Nonlinear Programming (North-Holland, Amsterdam), 1–36.Google Scholar
• Zakeri G , Philpott AB , Ryan DM (2000) Inexact cuts in Benders decomposition. SIAM J. Optim. 10(3):643–657.Google Scholar