Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation

详细信息    查看全文

• 作者：Daniel Porumbel
• 关键词：90C27 ; 90C11 ; 90C06
• 刊名：Mathematical Programming
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：155
• 期：1-2
• 页码：147-197
• 全文大小：1,261 KB
• 参考文献：1.Aardal, K., Nemhauser, G., Weismantel, R.: Discrete Optimization, volume 12 of Handbooks in Operations Research and Management Science. Elsevier, Amsterdam (2005)
  2.Alfandari, L., Sadki, J., Plateau, A., Nagih, A.: Hybrid column generation for large-size covering integer programs: application to transportation planning. Comput. OR 40(8), 1938–1946 (2013)MathSciNet CrossRef
  3.Barnhart, C., Johnson, E., Nemhauser, G., Savelsbergh, M., Vance, P.: Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46(3), 316–329 (1998)MATH MathSciNet CrossRef
  4.Bartolini, E., Cordeau, J.-F., Laporte, G.: Improved lower bounds and exact algorithm for the capacitated arc routing problem. Math. Program. 137(1–2), 409–452 (2013)MATH MathSciNet CrossRef
  5.Ben-Ameur, W., Neto, J.: Acceleration of cutting-plane and column generation algorithms: applications to network design. Networks 49(1), 3–17 (2007)MATH MathSciNet CrossRef
  6.Ben Amor, H., de Carvalho, J.M.V.: Cutting stock problems. In: Desaulniers, G., Desrosiers, J., Solomon, M. (eds.) Column Generation, pp. 131–161. Springer, Berlin (2005)CrossRef
  7.Briant, O., Lemaréchal, C., Meurdesoif, P., Michel, S., Perrot, N., Vanderbeck, F.: Comparison of bundle and classical column generation. Math. Program. 113(2), 299–344 (2008)MATH MathSciNet CrossRef
  8.Clautiaux, F., Alves, C., Carvalho, J.: A survey of dual-feasible and superadditive functions. Ann. Oper. Res. 179(1), 317–342 (2009)CrossRef
  9.Clautiaux, F., Alves, C., de Carvalho, J.M.V., Rietz, J.: New stabilization procedures for the cutting stock problem. INFORMS J. Comput. 23(4), 530–545 (2011)MATH MathSciNet CrossRef
  10.Fonlupt, J., Skoda, A.: Strongly polynomial algorithm for the intersection of a line with a polymatroid. In: Cook, W., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 69–85. Springer, Berlin (2009)CrossRef
  11.Fukasawa, R., Longo, H., Lysgaard, J., de Aragão, M.P., Reis, M., Uchoa, E., Werneck, R.F.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. 106(3), 491–511 (2006)MATH MathSciNet CrossRef
  12.Gilmore, P., Gomory, R.: A linear programming approach to the cutting stock problem. Oper. Res. 9, 849–859 (1961)MATH MathSciNet CrossRef
  13.Gondzio, J., González-Brevis, P., Munari, P.: New developments in the primal-dual column generation technique. Eur. J. Oper. Res. 224(1), 41–51 (2013)MATH CrossRef
  14.Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463–468 (1975)MATH MathSciNet CrossRef
  15.Irnich, S., Villeneuve, D.: The shortest-path problem with resource constraints and k-cycle elimination for k 3. INFORMS J. Comput. 18(3), 391–406 (2006)MATH MathSciNet CrossRef
  16.Kaparis, K., Letchford, A.N.: Separation algorithms for 0–1 knapsack polytopes. Math. Program. 124(1–2), 69–91 (2010)MATH MathSciNet CrossRef
  17.Letchford, A., Oukil, A.: Exploiting sparsity in pricing routines for the capacitated arc routing problem. Comput. Oper. Res. 36, 2320–2327 (2009)MATH MathSciNet CrossRef
  18.Letchford, A.N., Lodi, A.: Primal cutting plane algorithms revisited. Math. Methods OR 56(1), 67–81 (2002)MATH MathSciNet CrossRef
  19.Lübbecke, M.E., Desrosiers, J.: Selected topics in column generation. Oper. Res. 53(6), 1007–1023 (2005)MATH MathSciNet CrossRef
  20.Martinelli, R., Pecin, D., Poggi, M., Longo, H.: Column generation bounds for the capacitated arc routing problem. In: XLII SBPO (2010)
  21.McCormick, S.T.: Submodular function minimization. In: Aardal, G.N.K., Weismantel, R. (eds.) Discrete Optimization, volume 12 of Handbooks in Operations Research and Management Science, pp. 321–391. Elsevier, Amsterdam (2005)
  22.Nagano, K.: A strongly polynomial algorithm for line search in submodular polyhedra. Discrete Optim. 4(34), 349–359 (2007)MATH MathSciNet CrossRef
  23.Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32(9), 2271–2284 (2005)MATH MathSciNet CrossRef
  24.Spille, B., Weismantel, R.: Primal integer programming. In: Discrete Optimization [1], pp. 245–276
  25.Vanderbeck, F.: Computational study of a column generation algorithm for bin packing and cutting stock problems. Math. Program. 86(3), 565–594 (1999)MATH MathSciNet CrossRef
  26.Vanderbeck, F.: A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem. Manage. Sci. 47(6), 864–879 (2001)
  27.Vanderbeck, F.: Implementing mixed integer column generation. In: Desaulniers, G., Desrosiers, J., Solomon, M. (eds.) Column Generation, pp. 331–358. Springer, Berlin (2005)CrossRef
  28.Wäscher, G., Haußner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183(3), 1109–1130 (2007)MATH CrossRef
  
• 作者单位：Daniel Porumbel (1)
  
  1. CEDRIC CS Lab, CNAM, 292 Rue Saint-Martin, 75141, Paris Cedex 03, France
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

A recurrent task in mathematical programming consists of optimizing polytopes with prohibitively many constraints, e.g., the primal polytope in cutting-planes methods or the dual polytope in column generation (CG). We present a method to optimize such polytopes using the following intersection sub-problem: given ray \({\mathbf r}\in \mathbb {Z}^n\), find the maximum \({t^*}\ge 0\) such that \({t^*}{\mathbf r}\) is feasible. We interpret \({\mathbf 0_n}\rightarrow {\mathbf r}\) as a direction of growth from the origin \({\mathbf 0_n}\); \({t^*}{\mathbf r}\) is the intersection point between \({\mathbf 0_n}\rightarrow {\mathbf r}\) and the polytope boundary. To ease the exposition, the first part of the paper is devoted to the general context of a (primal or dual) polytope with rational data such that: (i) the intersection sub-problem can be effectively solved in practice for input rays \({\mathbf r}\in \mathbb {Z}^n\) and (ii) \({\mathbf 0_n}\) is feasible. By iterating over such rays \({\mathbf r}\), our method produces a sequence of feasible solutions \({t^*}{\mathbf r}\) that we prove to be finitely convergent. From Section 3 on, we focus on dual polytopes in CG formulations. Typically, if the CG (separation) sub-problem can be solved by dynamic programming (DP), so can be the intersection sub-problem. The proposed integer ray method (IRM) only uses integer rays, and so, the intersection sub-problem can be solved using a DP scheme based on states indexed by integer ray values. We show that under such conditions, the intersection sub-problem can be even easier than the CG sub-problem, especially when no other integer data is available to index states in DP, i.e., if the CG sub-problem input consists of fractional (or large-range) values. As such, the IRM can tackle scaled instances (with large-range weights) of capacitated problems that seem prohibitively hard for classical CG. This is confirmed by numerical experiments on various capacitated Set-Covering problems: Capacitated Arc-Routing, Cutting-Stock and other three versions of Elastic Cutting-Stock (i.e., a problem class that includes Variable Size Bin Packing). Mathematics Subject Classification 90C27 90C11 90C06