An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion

References

• Aissi H, Bazgan C, Vanderpooten D (2005) Complexity of the min-max and min-max regret assignment problem. Oper. Res. Lett. 33:634–640.Crossref, Google Scholar
• Aissi H, Bazgan C, Vanderpooten D (2009) Min–max and min–max regret versions of combinatorial optimization problems: A survey. Eur. J. Oper. Res. 197(2):427–438.Crossref, Google Scholar
• Ayvaz-Cavdaroglu N, Kachani S, Maglaras C (2016) Revenue management with minimax regret negotiations. Omega 63:11–22.Crossref, Google Scholar
• Beasley JE (1990) Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Cacchiani V, Hemmelmayr VC, Tricoire F (2014) A set-covering based heuristic algorithm for the periodic vehicle routing problem. Discrete Appl. Math. 163:53–64.Crossref, Google Scholar
• Candia-Véjar A, Álvarez-Miranda E, Maculan N (2011) Minmax regret combinatorial optimization problems: An algorithmic perspective. Recherche Opérationnelle 45(2):101–129.Google Scholar
• Chien CF, Zheng JN (2012) Mini–max regret strategy for robust capacity expansion decisions in semiconductor manufacturing. J. Intelligent Manufacturing 23(6):2151–2159.Crossref, Google Scholar
• Chu PC, Beasley JE (1997) A genetic algorithm for the generalised assignment problem. Comput. Oper. Res. 24(1):17–23.Crossref, Google Scholar
• Chu PC, Beasley JE (1998) A genetic algorithm for the multidimensional knapsack problem. J. Heuristics 4(1):63–86.Crossref, Google Scholar
• Coco AA, Santos AC, Noronha TF (2015) Senario-based heuristics with path-relinking for the robust set covering problem. Proc. XI Metaheuristics Internat. Conf., 1–8.Google Scholar
• Deineko VG, Woeginger GJ (2010) Pinpointing the complexity of the interval min–max regret knapsack problem. Discrete Optim. 7(4):191–196.Crossref, Google Scholar
• Dong C, Huang G, Cai Y, Xu Y (2011) An interval-parameter minimax regret programming approach for power management systems planning under uncertainty. Appl. Energy 88(8):2835–2845.Crossref, Google Scholar
• Farahani RZ, Asgari N, Heidari N, Hosseininia M, Goh M (2012) Covering problems in facility location: A review. Comput. Industrial Engrg. 62(1):368–407.Crossref, Google Scholar
• Fisher ML, Jaikumar R (1981) A generalized assignment heuristic for vehicle routing. Networks 11(2):109–124.Crossref, Google Scholar
• Furini F, Iori M, Martello S, Yagiura M (2015) Heuristic and exact algorithms for the interval min–max regret knapsack problem. INFORMS J. Comput. 27(2):392–405.Link, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, vol. 174 (W.H. Freeman, San Francisco).Google Scholar
• Godinho N, Paquete L (2019) A combinatorial branch and bound for the min-max regret spanning tree problem. Proc. Internat. Sympos. on Experiment. Algorithms (Springer, Berlin), 69–81.Google Scholar
• Karaşan OE, Pinar MC, Yaman H (2001) The robust shortest path problem with interval data. Technical report, Bilkent University, Ankara, Turkey.Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Complexity of Computer Computations (Springer, Berlin), 85–103.Crossref, Google Scholar
• Kasperski A (2008) Discrete Optimization with Interval Data (Springer, Berlin).Google Scholar
• Kasperski A, Zieliński P (2006) An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inform. Processing Lett. 97(5):177–180.Crossref, Google Scholar
• Kasperski A, Zieliński P (2016) Robust discrete optimization under discrete and interval uncertainty: A survey. Robustness Analysis in Decision Aiding, Optimization, and Analytics (Springer, Berlin), 113–143.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin).Crossref, Google Scholar
• Kouvelis P, Yu G (2013) Robust Discrete Optimization and Its Applications, vol. 14 (Springer Science & Business Media, Dordrecht, Germany).Google Scholar
• Kulik A, Shachnai H (2010) There is no eptas for two-dimensional knapsack. Inform. Processing Lett. 110(16):707–710.Crossref, Google Scholar
• Laabadi S, Naimi M, El Amri H, Achchab B (2018) The 0/1 multidimensional knapsack problem and its variants: A survey of practical models and heuristic approaches. Amer. J. Oper. Res. 8(05):395.Google Scholar
• Laguna M, Kelly JP, González-Velarde J, Glover F (1995) Tabu search for the multilevel generalized assignment problem. Eur. J. Oper. Res. 82:176–189.Crossref, Google Scholar
• Loulou R, Kanudia A (1999) Minimax regret strategies for greenhouse gas abatement: Methodology and application. Oper. Res. Lett. 25(5):219–230.Crossref, Google Scholar
• Makuchowski M (2014) Perturbation algorithm for a minimax regret minimum spanning tree problem. Oper. Res. Decisions 24(1):37–49.Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, Chichester, UK).Google Scholar
• Montemanni R (2006) A Benders decomposition approach for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 174(3):1479–1490.Crossref, Google Scholar
• Montemanni R, Gambardella LM (2005) A branch and bound algorithm for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 161(3):771–779.Crossref, Google Scholar
• Montemanni R, Barta J, Mastrolilli M, Gambardella LM (2007) The robust traveling salesman problem with interval data. Transportation Sci. 41(3):366–381.Link, Google Scholar
• Pereira J (2018) The robust (minmax regret) assembly line worker assignment and balancing problem. Comput. Oper. Res. 93:27–40.Crossref, Google Scholar
• Pereira J, Averbakh I (2011) Exact and heuristic algorithms for the interval data robust assignment problem. Comput. Oper. Res. 38(8):1153–1163.Crossref, Google Scholar
• Pereira J, Averbakh I (2013) The robust set covering problem with interval data. Ann. Oper. Res. 207(1):217–235.Crossref, Google Scholar
• Poorsepahy-Samian H, Kerachian R, Nikoo MR (2012) Water and pollution discharge permit allocation to agricultural zones: Application of game theory and min-max regret analysis. Water Resources Management 26(14):4241–4257.Crossref, Google Scholar
• Puchinger J, Raidl GR, Pferschy U (2010) The multidimensional knapsack problem: Structure and algorithms. INFORMS J. Comput. 22(2):250–265.Link, Google Scholar
• Ruland KS (1999) A model for aeromedical routing and scheduling. Internat. Trans. Oper. Res. 6(1):57–73.Crossref, Google Scholar
• Wu W, Yagiura M, Ibaraki T (2018a) Generalized assignment problem. Gonzalez TF, ed. Handbook of Approximation Algorithms and Metaheuristics: Methologies and Traditional Applications, vol. 1 (Chapman & Hall/CRC), 713–736.Google Scholar
• Wu W, Iori M, Martello S, Yagiura M (2016a) An iterated dual substitution approach for the min-max regret multidimensional knapsack problem. Proc. IEEE Internat. Conf. on Industrial Engrg. and Engrg. Management, (IEEE) 726–730, https://www.proceedings.com/32731.html.Google Scholar
• Wu W, Iori M, Martello S, Yagiura M (2018b) Exact and heuristic algorithms for the interval min-max regret generalized assignment problem. Comput. Industrial Engrg. 125:98–110.Crossref, Google Scholar
• Wu W, Iori M, Martello S, Yagiura M (2022) mmrbipy version v0.1.9. https://github.com/INFORMSJoC/2020.0301.Google Scholar
• Wu W, Hu Y, Hashimoto H, Ando T, Shiraki T, Yagiura M (2016b) A column generation approach to the airline crew pairing problem to minimize the total person-days. J. Adv. Mechanical Design, Systems, Manufacturing 10(3):JAMDSM0040.Crossref, Google Scholar
• Xidonas P, Mavrotas G, Hassapis C, Zopounidis C (2017) Robust multiobjective portfolio optimization: A minimax regret approach. Eur. J. Oper. Res. 262(1):299–305.Google Scholar
• Yaman H, Karaşan OE, Pinar MÇ (2001) The robust spanning tree problem with interval data. Oper. Res. Lett. 29(1):31–40.Crossref, Google Scholar