Abstract
In this paper, we address a class of arc-flow mathematical programming models that use a pseudo-polynomial number of variables and constraints. In [7], the authors have shown that such models can be used in practice to solve a vehicle routing problem using an aggregation algorithm. The purpose of this paper is to study the theoretical quality of the solutions and relaxations obtained when an aggregation is applied to such pseudo-polynomial flow models. We show that the approximation ratio and worst-case performance obtained by the heuristics and the relaxations depend on the concept of conflict-difference cliques. We then give an algorithm to compute the best aggregation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Christophides, N., Mingozzi, A., Toth, P.: State-space relaxation procedures for the computation of bounds to routing problems. Networks 11, 145–164 (1981)
Valério de Carvalho, J.M.: Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research 86, 629–659 (1999)
Valério de Carvalho, J.M.: LP models for bin packing and cutting stock problems. European Journal of Operational Research 141(2), 253–273 (2002)
Garey, M.R., Johnson, D.S.: Computers and intractability, a guide to the theory of NP-completeness. Freeman, New York (1979)
Lancia, G., Rinaldi, F., Serafini, P.: A time-indexed lp-based approach for min-sum job-shop problems. Annals of Operations Research 186, 175–198 (2011)
Lawler, E.L.: Optimal sequencing of a single machine subject to precedence constraints. Management Science, 544–546 (1973)
Macedo, R., Alves, C., Valério de Carvalho, J., Clautiaux, F., Hanafi, S.: Solving exactly the vehicle routing problem with time windows and multiple routes using a pseudo-polynomial model. European Journal of Operational Research 214(3), 457–545 (2011)
Macedo, R., Alves, C., Valério de Carvalho, J.M.: Arc-flow model for the two-dimensional guillotine cutting stock problem. Computers & Operations Research 37(6), 991–1001 (2010)
Gendreau, M., Azi, N., Potvin, J.-Y.: An exact algorithm for a single-vehicle routing problem with time windows and multiple routes. European Journal of Operational Research 178, 755–766 (2007)
Pessoa, A., Uchoa, E., de Aragão, M., Rodrigues, R.: Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Mathematical Programming Computation 2, 259–290 (2010)
Rogers, D.F., Plante, R.D., Wong, R.T., Evans, J.R.: Aggregation and disaggregation techniques and methodology in optimization. Operations Research 39(4), 553–582 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Voge, ME., Clautiaux, F. (2012). Theoretical Investigation of Aggregation in Pseudo-polynomial Network-Flow Models. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds) Combinatorial Optimization. ISCO 2012. Lecture Notes in Computer Science, vol 7422. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32147-4_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-32147-4_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32146-7
Online ISBN: 978-3-642-32147-4
eBook Packages: Computer ScienceComputer Science (R0)