Uncommon Dantzig-Wolfe Reformulation for the Temporal Knapsack Problem

References

• Arkin EM, Silverberg EB. Scheduling jobs with fixed start and end times. Discrete Appl. Math. (1987) 18(1):1–8Crossref, Google Scholar
• Bansal N, Chakrabarti A, Epstein A, Schieber B. A quasi-PTAS for unsplittable flow on line graphs. Proc. 38th Annual ACM Sympos. Theory Comput. (2006) (STOC, Seattle) 721–729Crossref, Google Scholar
• Bartlett M, Frisch AM, Hamadi Y, Miguel I, Tarim SA, Unsworth C. The temporal knapsack problem and its solution. Proc. 2nd Internat. Conf. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optim. Problems (CP-AI-OR 2005) (2005) (Springer-Verlag, Berlin) 34–48Crossref, Google Scholar
• Bergner M, Caprara A, Furini F, Lübbecke M, Malaguti E, Traversi E. Partial convexification of general MIPs by Dantzig-Wolfe reformulation. Proc. 15th Internat. Conf. Integer Programming and Combinatorial Optim. (IPCO 2011) (2011) (Springer-Verlag, Berlin) 39–51Crossref, Google Scholar
• Bonsma P, Schulz J, Wiese A. A constant factor approximation algorithm for unsplittable flow on paths. (2011) . CoRR abs/1102.3643Google Scholar
• Calinescu G, Chakrabarti A, Karloff HJ, Rabani Y. Improved approximation algorithms for resource allocation. Proc. 9th Internat. Conf. Integer Programming and Combinatorial Optim. (IPCO 2002) (2002) (Springer-Verlag, Berlin) 401–414Crossref, Google Scholar
• Caprara A, Malaguti E, Toth P. A freight service design problem for a railway corridor. Transportation Sci. (2011) 45(2):147–162Link, Google Scholar
• Chen B, Hassin R, Tzur M. Allocation of bandwidth and storage. IIE Trans. (2002) 34(5):501–507Crossref, Google Scholar
• Darmann A, Pferschy U, Schauer J. Resource allocation with time intervals. Theoret. Comput. Sci. (2010) 411(49):4217–4234Crossref, Google Scholar
• de Aragao MP, Uchoa E. Integer program reformulation for robust branch-and-cut-and-price algorithms. Proc. Conf. Math. Program in Rio: A Conf. Honour of Nelson Maculan (Rio de Janeiro) (2003) 56–61Google Scholar
• Furini F. Decomposition and reformulation of integer linear programming problems. 4OR (2012) 10(2):219–220Crossref, Google Scholar
• Gamrath G, Lübbecke ME. Experiments with a generic Dantzig-Wolfe decomposition for integer programs. Proc. 9th Internat. Sympos. Experiment. Algorithms (SEA) (2010) (Springer-Verlag, Berlin) 239–252Crossref, Google Scholar
• Hall NG, Magazine MJ. Maximizing the value of a space mission. Eur. J. Oper. Res. (1994) 78(2):224–241Crossref, Google Scholar
• IBM-CPLEXAccessed April 2011, http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/Google Scholar
• Kellerer H, Pferschy U, Pisinger D. Knapsack Problems (2004) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Lübbecke M, Desrosiers J. Selected topics in column generation. Oper. Res. (2004) 53(6):1007–1023Link, Google Scholar
• Martello S, Toth P. Knapsack Problems: Algorithms and Computer Implementations (1990) (John Wiley & Sons, Chichester, UK) Google Scholar
• Puchinger J, Raidl GR, Pferschy U. The multidimensional knapsack problem: Structure and algorithms. INFORMS J. Comput. (2010) 22(2):250–265Link, Google Scholar
• Ralphs TK, Galati MV. Decomposition and dynamic cut generation in integer linear programming. Math. Programming (2006) 106(2):251–285Crossref, Google Scholar
• SCIPAccessed April 2011, http://scip.zib.de/Google Scholar
• Sherali HD, Lee Y, Kim Y. Partial convexification cuts for 0-1 mixed-integer programs. Eur. J. Oper. Res. (2005) 165(3):625–648Crossref, Google Scholar
• Vanderbeck F, Wolsey LA, Jiinger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA. Reformulation and decomposition of integer programs. 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art (2010) (Springer-Verlag, Berlin, Heidelberg) 431–502Crossref, Google Scholar