Consistency Cuts for Dantzig-Wolfe Reformulations

References

• Achterberg T (2009) SCIP: Solving constraint integer programs. Math. Programming Comput. 1(1):1–41.Crossref, Google Scholar
• Aguado JS (2009) Fixed charge transportation problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems. Ann. Oper. Res. 172(1):45.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Bartlett M, Frisch AM, Hamadi Y, Miguel I, Tarim SA, Unsworth C (2005) The temporal knapsack problem and its solution. Bartak R, Milano M, eds. Internat. Conf. Integration Artificial Intelligence (AI) Oper. Res. (OR) Techniques Constraint Programming, Lecture Notes in Computer Science, vol. 3524 (Springer, Berlin, Heidelberg), 34–48.Google Scholar
• Belov G, Letchford AN, Uchoa E (2005) A node-flow model for 1d stock cutting: Robust branch-cut-and-price. Technical report Universidade Federal Fluminense, Engenharia de Produção, Niterói, Brazil.Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Bergner M, Caprara A, Ceselli A, Furini F, Lübbecke ME, Malaguti E, Traversi E (2015) Automatic Dantzig–Wolfe reformulation of mixed integer programs. Math. Programming 149(1-2):391–424.Crossref, Google Scholar
• Caprara A, Furini F, Malaguti E (2013) Uncommon Dantzig-Wolfe reformulation for the temporal knapsack problem. INFORMS J. Comput. 25(3):560–571.Link, Google Scholar
• Caprara A, Malaguti E, Toth P (2011) A freight service design problem for a railway corridor. Transportation Sci. 45(2):147–162.Link, Google Scholar
• Caprara A, Furini F, Malaguti E, Traversi E (2016) Solving the temporal knapsack problem via recursive Dantzig–Wolfe reformulation. Inform. Processing Lett. 116(5):379–386.Crossref, Google Scholar
• Clautiaux F, Detienne B, Guillot G (2019) Dynamic programming approaches for the temporal knapsack problem. Preprint, submitted February 21, https://hal.archives-ouvertes.fr/hal-02044832v1.Google Scholar
• Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms, 3rd ed. (MIT Press, Cambridge, MA).Google Scholar
• Dabia S, Ropke S, Van Woensel T (2019) Cover inequalities for a vehicle routing problem with time windows and shifts. Transportation Sci. 53(5):1354–1371.Link, Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, Google Scholar
• Desaulniers G, Desrosiers J, Spoorendonk S (2011) Cutting planes for branch-and-price algorithms. Networks 58(4):301–310.Crossref, Google Scholar
• Du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1-3):229–237.Crossref, Google Scholar
• Fourer R (1984) Staircase matrices and systems. SIAM Rev. 26(1):1–70.Crossref, Google Scholar
• Fréville A, Hanafi S (2005) The multidimensional 0-1 knapsack problem—Bounds and computational aspects. Ann. Oper. Res. 139(1):195.Crossref, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Poggi de Aragão M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Gleixner A, Hendel G, Gamrath G, Achterberg T, Bastubbe M, Berthold T, Christophel P, Jarck K, Koch T, Linderoth J, Lübbecke M, Mittelmann HD, Ozyurt D, Ralphs TK, Salvagnin D, Shinano Y (2021) MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. Math. Programming Comput. (13): 443–490.Google Scholar
• Glover F, Klingman D (1988) Layering strategies for creating exploitable structure in linear and integer programs. Math. Programming 40(1-3):165–181.Crossref, Google Scholar
• Gschwind T, Irnich S (2017) Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities. OR Spectrum 39(2):541–556.Crossref, Google Scholar
• Guignard M (2003) Lagrangean relaxation. TOP 11(2):151–200.Crossref, Google Scholar
• Guignard M, Kim S (1987) Lagrangean decomposition: A model yielding stronger Lagrangean bounds. Math. Programming 39(2):215–228.Crossref, Google Scholar
• Hooker JN, Ottosson G (2003) Logic-based benders decomposition. Math. Programming Ser. B 96(1):33–60.Crossref, Google Scholar
• ILOG CPLEX Optimization Studio (2017) Deterministic time limit. Accessed April 1, 2021, https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.1/ilog.odms.cplex.help/CPLEX/Parameters/topics/DetTiLim.html.Google Scholar
• Jayakumar MD, Ramasesh RV (1994) A clustering heuristic to detect staircase structures in large scale linear programming models. Eur. J. Oper. Res. 76(1):229–239.Crossref, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Karypis KV (1998) hMETIS 1.5: A hypergraph partitioning package. Technical report, University of Minnesota, Minneapolis.Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer-Verlag, Berlin, Heidelberg).Crossref, Google Scholar
• Kohl N, Desrosiers J, Oli B, Madsen G, Solomon MM, Soumis F (1999) 2-path cuts for the vehicle routing problem with time windows. Transportation Sci. 33(1):101–116.Link, Google Scholar
• Lasdon LS (1970) Optimization Theory for Large Systems (MacMillan, New York).Google Scholar
• Lawler EL, Wood DE (1966) Branch-and-bound methods: A survey. Oper. Res. 14(4):699–719.Link, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Lübbecke ME, Puchert C (2015) Primal heuristics for mixed integer programs with a staircase structure. Technical Report, RWTH Aachen University.Google Scholar
• Mingozzi A, Roberti R (2017) 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
• Nemhauser GL, Park S (1991) A polyhedral approach to edge coloring. Oper. Res. Lett. 10(6):315–322.Crossref, Google Scholar
• Nilsson O, Sjelvgren D (1997) Variable splitting applied to modelling of start-up costs in short term hydro generation scheduling. IEEE Trans. Power Systems 12(2):770–775.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Petersen B, Pisinger D, Spoorendonk S (2008) Chvátal-gomory rank-1 cuts used in a Dantzig-Wolfe decomposition of the vehicle routing problem with time windows. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges, Operations Research/Computer Science Interfaces, vol. 43 (Springer, Boston), 397–419.Crossref, Google Scholar
• Pigatti A, De Aragao MP, Uchoa E (2005) Stabilized branch-and-cut-and-price for the generalized assignment problem. Electronic Notes Discrete Math. 19:389–395.Crossref, Google Scholar
• Poggi de Aragao M, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price algorithms. Proc. Conf. Math. Program Rio: A Conf. Honour Nelson Maculan, Rio de Janeiro, Brazil, 56–61.Google Scholar
• Savelsbergh M (1997) A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45(6):831–841.Link, Google Scholar
• Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• Spoorendonk S, Desaulniers G (2010) Clique inequalities applied to the vehicle routing problem with time windows. INFOR Inform. Systems Oper. Res. 48(1):53–67.Crossref, Google Scholar
• Tang L, Meng Y, Liu J (2011) An improved Lagrangean relaxation algorithm for the dynamic batching decision problem. Internat. J. Production Res. 49(9):2501–2517.Crossref, Google Scholar
• Van den Akker M, Hurkens CAJ, Savelsbergh MWP (2000) Time-indexed formulations for machine scheduling problems: Column generation. INFORMS J. Comput. 12(2):111–124.Link, Google Scholar
• Vanderbeck F, Savelsbergh MWP (2006) A generic view of Dantzig–Wolfe decomposition in mixed integer programming. Oper. Res. Lett. 34(3):296–306.Crossref, Google Scholar
• Vanderbeck F, Wolsey LA (2010) Reformulation and decomposition of integer programs. 50 Years of Integer Programming 1958-2008 (Springer, Berlin, Heidelberg ), 431–502.Google Scholar
• Wang J, Ralphs T (2013) Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization. Gomes C, Sellmann M, eds. Internat. Conf. AI OR Techniques Constriant Programming Combinatorial Optim. Problems, Lecture Notes in Computer Science, vol. 7874 (Springer, Berlin, Heidelberg), 394–402.Google Scholar
• Wolsey LA, Nemhauser GL (1988) Integer and Combinatorial Optimization (John Wiley & Sons, New York).Google Scholar
• Wu D, Ierapetritou MG (2003) Decomposition approaches for the efficient solution of short-term scheduling problems. Comput. Chemical Engrg. 27(8-9):1261–1276.Crossref, Google Scholar
• Zhao Y, Larsson T, Rönnberg E, Pardalos PM (2018) The fixed charge transportation problem: A strong formulation based on Lagrangian decomposition and column generation. J. Global Optim. 72(3):517–538.Crossref, Google Scholar