Integer Programming Approaches For Minimum Stabbing Problems

dc.creatorPiva B.
dc.creatorDe Souza C.C.
dc.creatorFrota Y.
dc.creatorSimonetti L.
dc.date2014
dc.date2015-06-25T18:04:13Z
dc.date2015-11-26T15:06:33Z
dc.date2015-06-25T18:04:13Z
dc.date2015-11-26T15:06:33Z
dc.date.accessioned2018-03-28T22:17:00Z
dc.date.available2018-03-28T22:17:00Z
dc.identifier
dc.identifierRairo - Operations Research. , v. 48, n. 2, p. 211 - 233, 2014.
dc.identifier3990559
dc.identifier10.1051/ro/2014008
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-84900574211&partnerID=40&md5=7d9696a755c16f69027e0dbd7a6fd88f
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/88140
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/88140
dc.identifier2-s2.0-84900574211
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1257259
dc.descriptionThe problem of finding structures with minimum stabbing number has received considerable attention from researchers. Particularly, [10] study the minimum stabbing number of perfect matchings (mspm), spanning trees (msst) and triangulations (mstr) associated to set of points in the plane. The complexity of the mstr remains open whilst the other two are known to be . This paper presents integer programming (ip) formulations for these three problems, that allowed us to solve them to optimality through ip branch-and-bound (b&b) or branch-and-cut (b&c) algorithms. Moreover, these models are the basis for the development of Lagrangian heuristics. Computational tests were conducted with instances taken from the literature where the performance of the Lagrangian heuristics were compared with that of the exact b&b and b&c algorithms. The results reveal that the Lagrangian heuristics yield solutions with minute, and often null, duality gaps for instances with several hundreds of points in small computation times. To our knowledge, this is the first computational study ever reported in which these three stabbing problems are considered and where provably optimal solutions are given. © 2014 EDP Sciences, ROADEF, SMAI.
dc.description48
dc.description2
dc.description211
dc.description233
dc.descriptionAgarwal, P., Aronov, B., Suri, S., Stabbing triangulations by lines in 3D (1995) Proceedings of the Eleventh Annual Symposium on Computational Geometry, SCG, 95, pp. 267-276. , New York, NY, USA. ACM
dc.descriptionBeasley, J., Lagrangean relaxation (1993) Modern Heuristic Techniques for Combinatorial Problems, pp. 243-303. , McGraw-Hill
dc.descriptionBeirouti, R., Snoeyink, J., Implementations of the LMT heuristic for minimum weight triangulation (1998) Proceedings of the Fourteenth Annual Symposium on Computational Geometry, SCG, 98, pp. 96-105. , New York, NY, USA ACM
dc.descriptionDe Berg, M., Van Kreveld, M., Rectilinear decompositions with low stabbing number (1994) Information Processing Letters, 52 (4), pp. 215-221. , DOI 10.1016/0020-0190(94)90129-5
dc.descriptionDe Loera, J.A., Hosten, S., Santos, F., Sturmfels, B., The polytope of all triangulations of a point configuration (1996) Documenta Math., 1, pp. 103-119
dc.descriptionDemaine, E., Mitchell, J., O'Rourke, J., (2010) The Open Problems Project, , http://maven.smith.edu/Eorourke/TOPP, Available online (acessed in January)
dc.descriptionDickerson, M.T., Montague, M.H., A (usually) connected subgraph of the minimum weight triangulation (1996) Proceedings of the 12th Annual ACM Symposyum on Computational Geometry, pp. 204-213
dc.descriptionEdmonds, J., Maximum matching and a polyhedron with 0,1-vertices (1965) J. Res. Nat. Bur. Stand. B, 69, pp. 125-130
dc.descriptionFekete, S., Lubbecke, M., Meijer, H., Minimizing the stabbing number of matchings, trees, and triangulations (2004) SODA, pp. 437-446. , edited by J. Munro. SIAM
dc.descriptionFekete, S., Lubbecke, M., Meijer, H., Minimizing the stabbing number of matchings, trees, and triangulations (2008) Discrete Comput. Geometry, 40, pp. 595-621
dc.descriptionFischetti, M., Gonzalez, J.J.S., Toth, P., Solving the Orienteering Problem through branch-and-cut (1998) INFORMS Journal on Computing, 10 (2), pp. 133-148
dc.descriptionGroetschel, M., Holland, O., Solving matching problems with linear programming (1985) Mathematical Programming, 33 (3), pp. 243-259
dc.descriptionKoch, T., Martin, A., Solving Steiner tree problems in graphs to optimality (1998) Networks, 33, pp. 207-232
dc.descriptionKolmogorov, V., Blossom V: A new implementation of a minimum cost perfect matching algorithm (2009) Math. Program. Comput., 1, pp. 43-67
dc.descriptionMagnanti, T.L., Wolsey, L.A., Optimal trees (1995) Handbooks in Operations Research and Management Science, 7, pp. 503-615
dc.descriptionMitchell, J., O'Rourke, J., Computational geometry (2001) SIGACT News, 32, pp. 63-72
dc.descriptionMitchell, J., Packer, E., Computing geometric structures of low stabbing number in the plane (2007) Proc. 17th Annual Fall Workshop on Comput. Geometry and Visualization, , IBM Watson
dc.descriptionMulzer, W., (2011), http://page.mi.fu-berlin.de/mulzer/pubs/mwtsoftware/old/ipelets/ LMTSkeleton.tar.gz, Index of/mEœulzer/pubs/mwtsoftware/old/ipelets Available online (accessed in March)Mulzer, W., Rote, G., Minimum-weight triangulation is NP-hard (2008) J. ACM, 55, pp. 1-11
dc.descriptionNunes, A.P., Uma abordagem de programação inteira para o problema da triangulação de custo mínimo (1997) In Portuguese, , Master's thesis, Institute of Computing, University of Campinas, Campinas, Brazil
dc.descriptionPadberg, M.W., Rao, M.R., Odd minimum cut-sets and b-matchings (1982) Math. Oper. Res., 7, pp. 67-80
dc.descriptionPiva, B., De Souza, C.C., The minimum stabbing triangulation problem: IP models and computational evaluation (2012) ISCO, pp. 36-47
dc.descriptionReinelt, G., (2011), http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95, TSPLIB. Available online (acessed in March)Shewchuk, J.R., Stabbing Delaunay tetrahedralizations (2002) Discrete and Comput. Geometry, 32, p. 343
dc.descriptionSolomon, M., (2011) VRPTW Benchmark Problems, , http://w.cba.neu.edu/Emsolomon/problems.htm, Available online (acessed in August)
dc.descriptionToth, C.D., Orthogonal subdivisions with low stabbing numbers (2005) Lecture Notes in Computer Science, 3608, pp. 256-268. , Algorithms and Data Structures: 9th International Workshop, WADS 2005. Proceedings
dc.descriptionWolsey, L.A., (1998) Integer Programming, , John Wiley & Sons
dc.languageen
dc.publisher
dc.relationRAIRO - Operations Research
dc.rightsaberto
dc.sourceScopus
dc.titleInteger Programming Approaches For Minimum Stabbing Problems
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución