Abstract
Discretized formulations have proved to be useful for modeling combinatorial optimizations. The main focus of this work is on how to strengthen the linear programming relaxation of a given discretized formulation. More precisely, we will study and strengthen subproblems that arise in these formulations. In one case we will focus on the so-called knapsack reformulation which is based on viewing these models as the intersection of two polyhedra, one of them being a specialized knapsack problem. We will show that strong inequalities used in previous works are a special case of inequalities implied by the knapsack formulation. In the second case we will analyze a star-like subproblem and will provide an extended formulation for this problem as well as a set of inequalities on the original space, implied by the inequalities of the extended formulation. We will use a generalization of the Degree Constrained Spanning Tree problem as a setting for this study. In the present work, besides contextualizing these enhancements in terms of discretized models presented in previous works, we also compare and combine together them, for the first time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Albareda-Sambola M, Fernández E, Saldanha da Gama F (2011) The facility location problem with Bernoulli demands. Omega 39:335–345
Belotti P, Brunetta L, Malucelli F (2007) Multicommodity network design with discrete node costs. Networks 49:90–99
Constantino M, Gouveia L (2007) Reformulation by discretization: application to Economic Lot Sizing. Oper Res Lett 35(5):645–650
Correia I, Gouveia L, Saldanha da Gama F (2008) Solving the variable size bin packing problem with discretized formulations. Comput Oper Res 35(6):2103–2113
Correia I, Gouveia L, Saldanha da Gama F (2010) Discretized formulations for capacitated location problems with modular distribution costs. Eur J Oper Res 204(2):237–244
Croxton K, Gendron B, Magnanti T (2003) A comparison of mixed-integer programming models for non-convex piecewise linear cost minimization problems. Manag Sci 49:1268–1273
Cunha A, Lucena A (2007) Lower and upper bounds for the degree-constrained minimum spanning tree problem. Networks 50(1):55–66
Dahl G, Foldnes N, Gouveia L (2004) A note on hop-constrained walk polytopes. Oper Res Lett 32:345–349
Dahl G, Gouveia L (2004) On the directed hop-constrained shortest path problem. Oper Res Lett 32:15–22
Duhamel C, Gouveia L, Moura P, Souza M (2011, to appear) Minimum cost degree constrained spanning trees with node-degree costs. Networks. doi:10.1002/net.20445
Frangioni A, Gendron B (2009) 0–1 reformulations of the network loading problem. Discrete Appl Math 157(6):1229–1241
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. San Francisco
Gouveia L (1995) A 2n constraint formulation for the capacitated minimal spanning tree problem. Oper Res 43:130–141
Gouveia L, Moura P (2008) On discretized models for capacitated concentrator location problems: using double discretization. In: Proceedings from the EWGLAXVII conference, Elche, Spain
Gouveia L, Moura P (2010) Spanning trees with node degree dependent costs and knapsack reformulations. Electron Notes Discrete Math 36:985–992
Gouveia L, Moura P, Sousa A (2011) Prize collecting Steiner trees with node degree dependent costs. Comput Oper Res 38(1):234–245
Gouveia L, Saldanha da Gama F (2006) On the capacitated concentrator location problem: a reformulation by discretization. Comput Oper Res 33:1242–1258
Gouveia L, Voß S (1995) Classification of formulations for the (time-dependent) traveling salesman problem. Eur J Oper Res 83:69–82
Höller H, Voß S (2006) A heuristic approach for combined equipment-planning and routing in multi-layer SDH/WDM networks. Eur J Oper Res 171(3):787–796
Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin
Magnanti T, Wolsey L (1995) In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL (eds) Handbooks in operational research and management science: optimal trees
Martins P (2010) Extended and discretized formulations for the maximum clique problem. Comput Oper Res 37:1348–1358
Moura P (2009) Problema da Árvore de Suporte de Custo Mínimo com Restrição de Grau e Custos Associados aos Nodos. PhD thesis, Faculty of Sciences, University of Lisbon, Portugal, December
Uchoa E, Fukasawa R, Lysgaard J, Pessoa A, Poggi de Aragão M, Andrade D (2008) Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Math Program 112(2):443–472
Wolsey L (1998) Integer programming. Wiley, New York
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gouveia, L., Moura, P. Enhancing discretized formulations: the knapsack reformulation and the star reformulation. TOP 20, 52–74 (2012). https://doi.org/10.1007/s11750-011-0212-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-011-0212-x