The 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 𝓝𝓟-hard. 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.

Keywords: integer programming, lagrangian relaxation, stabbing problems, branch-and-bound, branch-and-cut

@article{RO_2014__48_2_211_0, author = {Piva, Breno and de Souza, Cid C. and Frota, Yuri and Simonetti, Luidi}, title = {Integer programming approaches for minimum stabbing problems}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {211--233}, publisher = {EDP-Sciences}, volume = {48}, number = {2}, year = {2014}, doi = {10.1051/ro/2014008}, mrnumber = {3264376}, zbl = {1295.90021}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2014008/} }

TY - JOUR AU - Piva, Breno AU - de Souza, Cid C. AU - Frota, Yuri AU - Simonetti, Luidi TI - Integer programming approaches for minimum stabbing problems JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2014 SP - 211 EP - 233 VL - 48 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2014008/ DO - 10.1051/ro/2014008 LA - en ID - RO_2014__48_2_211_0 ER -

%0 Journal Article %A Piva, Breno %A de Souza, Cid C. %A Frota, Yuri %A Simonetti, Luidi %T Integer programming approaches for minimum stabbing problems %J RAIRO - Operations Research - Recherche Opérationnelle %D 2014 %P 211-233 %V 48 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2014008/ %R 10.1051/ro/2014008 %G en %F RO_2014__48_2_211_0

Piva, Breno; de Souza, Cid C.; Frota, Yuri; Simonetti, Luidi. Integer programming approaches for minimum stabbing problems. RAIRO - Operations Research - Recherche Opérationnelle, Volume 48 (2014) no. 2, pp. 211-233. doi : 10.1051/ro/2014008. http://archive.numdam.org/articles/10.1051/ro/2014008/

[1] Stabbing triangulations by lines in 3D, in Proceedings of the eleventh annual symposium on Computational geometry, SCG '95, New York, NY, USA. ACM (1995) 267-276.

, and ,[2] Lagrangean relaxation, in Modern Heuristic Techniques for Combinatorial Problems. McGraw-Hill (1993) 243-303.

,[3] Implementations of the LMT heuristic for minimum weight triangulation, in Proceedings of the Fourteenth Annual Symposium on Computational Geometry, SCG '98, New York, NY, USA ACM (1998) 96-105.

and ,[4] Rectilinear decompositions with low stabbing number. Infor. Proc. Lett. 52 (1994) 215-221. | MR | Zbl

and ,[5] The polytope of all triangulations of a point configuration. Documenta Math. 1 (1996) 103-119. | MR | Zbl

, , and ,[6] The open problems project. Available online (acessed in January 2010). http://maven.smith.edu/˜orourke/TOPP/.

, and ,[7] A (usually) connected subgraph of the minimum weight triangulation, in Proceedings of the 12th Annual ACM Symposyum on Computational Geometry (1996) 204-213.

and ,[8] Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Stand. B 69 (1965) 125-130. | MR | Zbl

,[9] Minimizing the stabbing number of matchings, trees, and triangulations, in SODA edited by J. Munro. SIAM (2004) 437-446. | MR | Zbl

, and ,[10] Minimizing the stabbing number of matchings, trees, and triangulations. Discrete Comput. Geometry 40 (2008) 595-621. | MR | Zbl

, and ,[11] Solving the orienteering problem through branch-and-cut. INFORMS J. Comput. 10 133-148, 1998. | MR | Zbl

, and ,[12] Solving matching problems with linear programming. Math. Program. 33 (1985) 243-259. | MR | Zbl

and ,[13] Solving Steiner tree problems in graphs to optimality. Networks 33 (1998) 207-232. | MR | Zbl

and ,[14] V. Kolmogorov, Blossom V: a new implementation of a minimum cost perfect matching algorithm. Math. Program. Comput. 1 (2009) 43-67. | MR | Zbl

[15] Optimal trees. Handbooks in Operations Research and Management Science 7 (1995) 503-615. | MR | Zbl

and ,[16] Computational geometry. SIGACT News 32 (2001) 63-72.

and ,[17] Computing geometric structures of low stabbing number in the plane, in Proc. 17th Annual Fall Workshop on Comput. Geometry and Visualization. IBM Watson (2007).

and ,[18] Index of /m˜ulzer/pubs/mwtsoftware/old/ipelets. Available online (accessed in March 2011). http://page.mi.fu-berlin.de/mulzer/pubs/mwt˙software/old/ipelets/LMTSkeleton.tar.gz.

,[19] Minimum-weight triangulation is NP-hard. J. ACM 55 (2008) 1-11. | MR

and ,[20] Uma abordagem de programação inteira para o problema da triangulação de custo mínimo. Master's thesis, Institute of Computing, University of Campinas, Campinas, Brazil (1997). In Portuguese.

,[21] Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7 (1982) 67-80. | MR | Zbl

and ,[22] The minimum stabbing triangulation problem: IP models and computational evaluation. ISCO (2012) 36-47. | MR

and ,[23] TSPLIB. Available online (acessed in March 2011). http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.

,[24] Stabbing Delaunay tetrahedralizations. Discrete and Comput. Geometry 32 (2002) 343. | MR | Zbl

,[25] VRPTW benchmark problems. Available online (acessed in August 2011). http://w.cba.neu.edu/˜msolomon/problems.htm.

,[26] Orthogonal subdivisions with low stabbing numbers, Vol. 3608. Lect. Notes in Comput. Sci. Springer, Berlin/Heidelberg (2005) 256-268. | MR | Zbl

,[27] Integer Programming. John Wiley & Sons (1998). | MR | Zbl

,*Cited by Sources: *