Reduce-then-Optimize for the Fixed-Charge Transportation Problem

References

• Adlakha V , Kowalski K (2003) A simple heuristic for solving small fixed-charge transportation problems. Omega 31(3):205–211.Crossref, Google Scholar
• Adlakha V , Kowalski K , Vemuganti R (2006) Heuristic algorithms for the fixed-charge transportation problem. OPSEARCH 43(2):132–151.Crossref, Google Scholar
• Agarwal Y , Aneja Y (2012) Fixed-charge transportation problem: Facets of the projection polyhedron. Oper. Res. 60(3):638–654.Link, Google Scholar
• Alvarez AM , Louveaux Q , Wehenkel L (2017) A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1):185–195.Link, Google Scholar
• Balinski ML (1961) Fixed-cost transportation problems. Naval Res. Logist. Quart. 8(1):41–54.Crossref, Google Scholar
• Barr RS , Glover F , Klingman D (1981) A new optimization method for large scale fixed charge transportation problems. Oper. Res. 29(3):448–463.Link, Google Scholar
• Bello I , Pham H , Le QV , Norouzi M , Bengio S (2017) Neural combinatorial optimization with reinforcement learning. Internat. Conf. Learn. Representations. Google Scholar
• Bengio Y , Lodi A , Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Crossref, Google Scholar
• Böther M , Kiβig O , Taraz M , Cohen S , Seidel K , Friedrich T (2022) What’s wrong with deep learning in tree search for combinatorial optimization. Internat. Conf. Learn. Representations. Google Scholar
• Cappart Q , Chételat D , Khalil EB , Lodi A , Morris C , Veličković P (2023) Combinatorial optimization and reasoning with graph neural networks. J. Machine Learn. Res. 24(130):1–61.Google Scholar
• Cooper L , Drebes C (1967) An approximate solution method for the fixed charge problem. Naval Res. Logist. Quart. 14(1):101–113.Crossref, Google Scholar
• Crainic TG , Gendreau M (2021) Heuristics and metaheuristics for fixed-charge network design. Crainic TG, Gendreau M, Gendron B, eds. Network Design with Applications to Transportation and Logistics (Springer International Publishing, Cham, Switzerland), 91–138.Crossref, Google Scholar
• Deza A , Khalil EB (2023) Machine learning for cutting planes in integer programming: A survey. Preprint, submitted February 17, https://arxiv.org/abs/2302.09166.Google Scholar
• Ding JY , Zhang C , Shen L , Li S , Wang B , Xu Y , Song L (2020) Accelerating primal solution findings for mixed integer programs based on solution prediction. Proc AAAI Conf. Artificial Intelligence, vol. 34 (AAAI Press, Palo Alto, CA), 1452–1459.Crossref, Google Scholar
• Eckert C , Gottlieb J (2002) Direct representation and variation operators for the fixed charge transportation problem. Guervós J, Merelo JJ, Adamidis P, Beyer HG, Schwefel HP, Fernández-Villacañas JL, eds. Parallel Problem Solving from Nature—PPSN VII (Springer Berlin Heidelberg, Berlin, Heidelberg), 77–87.Google Scholar
• Fitzpatrick J , Ajwani D , Carroll P (2021) Learning to sparsify travelling salesman problem instances. Internat. Conf. Integration Constraint Programming Artificial Intelligence Oper. Res. (Springer International Publishing, Cham, Switzerland), 410–426.Google Scholar
• Gasse M , Chételat D , Ferroni N , Charlin L , Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 15580–15592.Google Scholar
• Gray P (1971) Exact solution of the fixed-charge transportation problem. Oper. Res. 19(6):1529–1538.Link, Google Scholar
• Gupta P , Khalil EB , Chételat D , Gasse M , Lodi A , Bengio Y , Kumar MP (2022) Lookback for learning to branch. Trans. Machine Learn. Res. Google Scholar
• Hildebrandt FD , Ulmer MW (2022) Supervised learning for arrival time estimations in restaurant meal delivery. Transportation Sci. 56(4):1058–1084.Link, Google Scholar
• Hirsch WM , Dantzig GB (1968) The fixed charge problem. Naval Res. Logist. Quart. 15(3):413–424.Crossref, Google Scholar
• Joshi CK , Laurent T , Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. Preprint, submitted June 4, https://arxiv.org/abs/1906.01227.Google Scholar
• Joshi CK , Cappart Q , Rousseau LM , Laurent T (2022) Learning the travelling salesperson problem requires rethinking generalization. Constraints 27:70–98.Crossref, Google Scholar
• Karalias N , Loukas A (2020) Erdős goes neural: An unsupervised learning framework for combinatorial optimization on graphs. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 6659–6672.Google Scholar
• Kennington J , Unger E (1976) A new branch-and-bound algorithm for the fixed-charge transportation problem. Management Sci. 22(10):1116–1126.Link, Google Scholar
• Khalil E , Dai H , Zhang Y , Dilkina B , Song L (2017) Learning combinatorial optimization algorithms over graphs. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Inc., Red Hook, NY), 6348–6358.Google Scholar
• Khalil EB , Le Bodic P , Song L , Nemhauser G , Dilkina B (2016) Learning to branch in mixed integer programming. Proc. AAAI Conf. Artificial Intelligence , vol. 30 (AAAI Press, Palo Alto, CA), 724–731.Google Scholar
• Kim H , Park J , Kwon C (2024) A neural separation algorithm for the rounded capacity inequalities. INFORMS J. Comput. 36(4):987–1005.Link, Google Scholar
• Kingma DP , Ba J (2014) Adam: A method for stochastic optimization. Preprint, submitted December 22, https://arxiv.org/abs/1412.6980.Google Scholar
• Kool W , van Hoof H , Welling M (2018) Attention, learn to solve routing problems! Internat. Conf. Learn. Representations. Google Scholar
• Lauri J , Dutta S , Grassia M , Ajwani D (2023) Learning fine-grained search space pruning and heuristics for combinatorial optimization. J. Heuristics 29:313–347.Crossref, Google Scholar
• Li Z , Chen Q , Koltun V (2018) Combinatorial optimization with graph convolutional networks and guided tree search. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Inc., Red Hook, NY), 537–546.Google Scholar
• Lotfi MM , Tavakkoli-Moghaddam R (2013) A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems. Appl. Soft Comput. 13(5):2711–2726.Crossref, Google Scholar
• McKeown P (1975) A vertex ranking procedure for solving the linear fixed-charge problem. Oper. Res. 23(6):1183–1191.Link, Google Scholar
• Mingozzi A , Roberti R (2018) An exact algorithm for the fixed charge transportation problem based on matching source and sink patterns. Transportation Sci. 52(2):229–238.Link, Google Scholar
• Morabit M , Desaulniers G , Lodi A (2021) Machine-learning-based column selection for column generation. Transportation Sci. 55(4):815–831.Link, Google Scholar
• Morabit M , Desaulniers G , Lodi A (2023) Machine-learning–based arc selection for constrained shortest path problems in column generation. INFORMS J. Optim. 5(2):191–210.Link, Google Scholar
• Murty KG (1968) Solving the fixed charge problem by ranking the extreme points. Oper. Res. 16(2):268–279.Link, Google Scholar
• Nair V , Bartunov S , Gimeno F , Von Glehn I , Lichocki P , Lobov I , O’Donoghue B , et al. (2020) Solving mixed integer programs using neural networks. Preprint, submitted December 23, https://arxiv.org/abs/2012.13349.Google Scholar
• Nazari M , Oroojlooy A , Snyder L , Takác M (2018) Reinforcement learning for solving the vehicle routing problem. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Palekar US , Karwan MH , Zionts S (1990) A branch-and-bound method for the fixed charge transportation problem. Management Sci. 36(9):1092–1105.Link, Google Scholar
• Papageorgiou DJ , Toriello A , Nemhauser GL , Savelsbergh MW (2012) Fixed-charge transportation with product blending. Transportation Sci. 46(2):281–295.Link, Google Scholar
• Parmentier A (2021) Learning structured approximations of operations research problems. Preprint, submitted July 9, https://arxiv.org/abs/2107.04323.Google Scholar
• Parmentier A (2022) Learning to approximate industrial problems by operations research classic problems. Oper. Res. 70(1):606–623.Link, Google Scholar
• Paulus MB , Zarpellon G , Krause A , Charlin L , Maddison C (2022) Learning to cut by looking ahead: Cutting plane selection via imitation learning. Chaudhuri K, Jegelka S, Song L, Szepesvari C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., vol. 162 (PMLR, New York), 17584–17600.Google Scholar
• Roberti R , Bartolini E , Mingozzi A (2015) The fixed charge transportation problem: An exact algorithm based on a new integer programming formulation. Management Sci. 61(6):1275–1291.Link, Google Scholar
• Sadagopan S , Ravindran A (1982) A vertex ranking algorithm for the fixed-charge transportation problem. J. Optim. Theory Appl. 37(2):221–230.Crossref, Google Scholar
• Steinberg DI (1970) The fixed charge problem. Naval Res. Logist. Quart. 17(2):217–235.Crossref, Google Scholar
• Subramanian A , Teichgraeber H (2023) The interplay between operations research and machine learning. Accessed May 17, 2023, https://pubsonline.informs.org/do/10.1287/orms.2023.02.02/full/.Google Scholar
• Sun Y , Li X , Ernst A (2019) Using statistical measures and machine learning for graph reduction to solve maximum weight clique problems. IEEE Trans. Pattern Anal. Machine Intelligence 43(5):1746–1760.Crossref, Google Scholar
• Sun Y , Ernst A , Li X , Weiner J (2021) Generalization of machine learning for problem reduction: A case study on travelling salesman problems. OR Spectrum 43(3):607–633.Crossref, Google Scholar
• Sun M , Aronson JE , McKeown PG , Drinka D (1998) A tabu search heuristic procedure for the fixed charge transportation problem. Eur. J. Oper. Res. 106(2–3):441–456.Crossref, Google Scholar
• Tayebi D , Ray S , Ajwani D (2022) Learning to prune instances of k-median and related problems. 2022 Proc. Sympos. Algorithm Engrg. Experiments (SIAM, Philadelphia), 184–194.Google Scholar
• Wang R , Hua Z , Liu G , Zhang J , Yan J , Qi F , Yang S , Zhou J , Yang X (2021) A bi-level framework for learning to solve combinatorial optimization on graphs. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Advances in Neural Information Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY), 21453–21466.Google Scholar
• Zhang X , Chen L , Gendreau M , Langevin A (2022) Learning-based branch-and-price algorithms for the vehicle routing problem with time windows and two-dimensional loading constraints. INFORMS J. Comput. 34(3):1419–1436.Link, Google Scholar
• Zhou J , Cui G , Hu S , Zhang Z , Yang C , Liu Z , Wang L , Li C , Sun M (2020) Graph neural networks: A review of methods and applications. AI Open 1:57–81.Crossref, Google Scholar