Integer programming approaches for minimum stabbing problems

Breno Piva; Cid C. de Souza; Yuri Frota; Luidi Simonetti

RAIRO - Operations Research - Recherche Opérationnelle (2014)

  • Volume: 48, Issue: 2, page 211-233
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Piva, Breno, et al. "Integer programming approaches for minimum stabbing problems." RAIRO - Operations Research - Recherche Opérationnelle 48.2 (2014): 211-233. <http://eudml.org/doc/275026>.

@article{Piva2014,
abstract = {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 &#x1d4dd;&#x1d4df;-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.},
author = {Piva, Breno, de Souza, Cid C., Frota, Yuri, Simonetti, Luidi},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {integer programming; lagrangian relaxation; stabbing problems; branch-and-bound; branch-and-cut; Lagrangian relaxation},
language = {eng},
number = {2},
pages = {211-233},
publisher = {EDP-Sciences},
title = {Integer programming approaches for minimum stabbing problems},
url = {http://eudml.org/doc/275026},
volume = {48},
year = {2014},
}

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
PB - EDP-Sciences
VL - 48
IS - 2
SP - 211
EP - 233
AB - 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 &#x1d4dd;&#x1d4df;-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.
LA - eng
KW - integer programming; lagrangian relaxation; stabbing problems; branch-and-bound; branch-and-cut; Lagrangian relaxation
UR - http://eudml.org/doc/275026
ER -

References

top
  1. [1] P. Agarwal, B. Aronov and S. Suri, 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. 
  2. [2] J. Beasley, Lagrangean relaxation, in Modern Heuristic Techniques for Combinatorial Problems. McGraw-Hill (1993) 243–303. 
  3. [3] R. Beirouti and J. Snoeyink, 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. 
  4. [4] M. Berg and M. Kreveld, Rectilinear decompositions with low stabbing number. Infor. Proc. Lett.52 (1994) 215–221. Zbl0823.68037MR1302595
  5. [5] J.A. de Loera, S. Hosten, F. Santos and B. Sturmfels, The polytope of all triangulations of a point configuration. Documenta Math.1 (1996) 103–119. Zbl0852.52007MR1386049
  6. [6] E. Demaine, J. Mitchell and J. O’Rourke, The open problems project. Available online (acessed in January 2010). http://maven.smith.edu/˜orourke/TOPP/. 
  7. [7] M.T. Dickerson and M.H. Montague, A (usually) connected subgraph of the minimum weight triangulation, in Proceedings of the 12th Annual ACM Symposyum on Computational Geometry (1996) 204–213. 
  8. [8] J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Stand. B 69 (1965) 125–130. Zbl0141.21802MR183532
  9. [9] S. Fekete, M. Lübbecke and H. Meijer, Minimizing the stabbing number of matchings, trees, and triangulations, in SODA edited by J. Munro. SIAM (2004) 437–446. Zbl1167.90628MR2291082
  10. [10] S. Fekete, M. Lübbecke and H. Meijer, Minimizing the stabbing number of matchings, trees, and triangulations. Discrete Comput. Geometry40 (2008) 595–621. Zbl1167.90628MR2453330
  11. [11] M. Fischetti, J.J.S. Gonzalez and P. Toth, Solving the orienteering problem through branch-and-cut. INFORMS J. Comput. 10 133–148, 1998. Zbl1034.90523MR1637551
  12. [12] M. Grötschel and O. Holland, Solving matching problems with linear programming. Math. Program.33 (1985) 243–259. Zbl0579.90069MR816104
  13. [13] T. Koch and A. Martin, Solving Steiner tree problems in graphs to optimality. Networks33 (1998) 207–232. Zbl1002.90078MR1645419
  14. [14] V. Kolmogorov, Blossom V: a new implementation of a minimum cost perfect matching algorithm. Math. Program. Comput. 1 (2009) 43–67. Zbl1171.05429MR2520443
  15. [15] T.L. Magnanti and L.A. Wolsey, Optimal trees. Handbooks in Operations Research and Management Science7 (1995) 503–615. Zbl0839.90135MR1420874
  16. [16] J. Mitchell and J. O’Rourke, Computational geometry. SIGACT News32 (2001) 63–72. 
  17. [17] J. Mitchell and E. Packer, Computing geometric structures of low stabbing number in the plane, in Proc. 17th Annual Fall Workshop on Comput. Geometry and Visualization. IBM Watson (2007). 
  18. [18] W. Mulzer, 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. [19] W. Mulzer and G. Rote, Minimum-weight triangulation is NP-hard. J. ACM55 (2008) 1–11. Zbl1311.05134MR2417038
  20. [20] A.P. Nunes, 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. [21] M.W. Padberg and M.R. Rao, Odd minimum cut-sets and b-matchings. Math. Oper. Res.7 (1982) 67–80. Zbl0499.90056MR665219
  22. [22] B. Piva and C.C. de Souza, The minimum stabbing triangulation problem: IP models and computational evaluation. ISCO (2012) 36–47. Zbl1312.90041MR3006014
  23. [23] G. Reinelt, TSPLIB. Available online (acessed in March 2011). http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/. 
  24. [24] J.R. Shewchuk, Stabbing Delaunay tetrahedralizations. Discrete and Comput. Geometry 32 (2002) 343. Zbl1092.52007MR2081629
  25. [25] M. Solomon, VRPTW benchmark problems. Available online (acessed in August 2011). http://w.cba.neu.edu/˜msolomon/problems.htm. 
  26. [26] C.D. Tóth, Orthogonal subdivisions with low stabbing numbers, Vol. 3608. Lect. Notes in Comput. Sci. Springer, Berlin/Heidelberg (2005) 256–268. Zbl1161.68819MR2200328
  27. [27] L.A. Wolsey, Integer Programming. John Wiley & Sons (1998). Zbl0930.90072MR1641246

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.