Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-26T07:49:09.336Z Has data issue: false hasContentIssue false
  • English
  • Français

Integer programming approaches for minimum stabbingproblems

Published online by Cambridge University Press:  07 March 2014

Breno Piva ,
Cid C. de Souza ,
Yuri Frota  and
Luidi Simonetti
Breno Piva
Affiliation:
Universidade Federal de Sergipe, Departamento de Computação, Cidade Universitária Prof. Aloísio Campos, 49100-000 São Cristóvão (SE), Brazil.. [email protected] Universidade Estadual de Campinas, Instituto de Computação, Av. Albert Einstein 1251, 13083-852 Campinas (SP), Brazil.; [email protected]
Cid C. de Souza
Affiliation:
Universidade Estadual de Campinas, Instituto de Computação, Av. Albert Einstein 1251, 13083-852 Campinas (SP), Brazil.; [email protected]
Yuri Frota
Affiliation:
Universidade Federal Fluminense, Instituto de Computação, R. Passo da Pátria 156, Bloco E, 24210-240 Niterói (RJ), Brazil.; [email protected],[email protected]
Luidi Simonetti
Affiliation:
Universidade Federal Fluminense, Instituto de Computação, R. Passo da Pátria 156, Bloco E, 24210-240 Niterói (RJ), Brazil.; [email protected],[email protected]
Get access

Abstract

The problem of finding structures with minimum stabbing number has received considerableattention 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 theplane. The complexity of the mstr remains open whilst the other two are known tobe 𝓝𝓟-hard. This paper presents integer programming(ip) formulations for these three problems, that allowed us to solve them tooptimality through ip branch-and-bound (b&b) or branch-and-cut(b&c) algorithms. Moreover, these models are the basis for the developmentof Lagrangian heuristics. Computational tests were conducted with instances taken from theliterature where the performance of the Lagrangian heuristics were compared with that ofthe exact b&b and b&c algorithms. The results reveal that theLagrangian heuristics yield solutions with minute, and often null, duality gaps forinstances 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 problemsare considered and where provably optimal solutions are given.

Keywords

Integer ProgrammingLagrangian RelaxationStabbing ProblemsBranch-and-BoundBranch-and-Cut
Type
Research Article
Information
RAIRO - Operations Research , Volume 48 , Issue 2: Isco 2012, guest editors Nelson Maculan, A. Ridha Mahjoub, Eduardo Uchoa , April 2014 , pp. 211 - 233
Copyright
© EDP Sciences, ROADEF, SMAI, 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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.
J. Beasley, Lagrangean relaxation, in Modern Heuristic Techniques for Combinatorial Problems. McGraw-Hill (1993) 243–303.
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.
Berg, M. and Kreveld, M., Rectilinear decompositions with low stabbing number. Infor. Proc. Lett. 52 (1994) 215–221. Google Scholar
de Loera, J.A., Hosten, S., Santos, F. and Sturmfels, B., The polytope of all triangulations of a point configuration. Documenta Math. 1 (1996) 103–119. Google Scholar
E. Demaine, J. Mitchell and J. O’Rourke, The open problems project. Available online (acessed in January 2010). http://maven.smith.edu/˜orourke/TOPP/.
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.
Edmonds, J., Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Stand. B 69 (1965) 125–130. Google Scholar
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.
Fekete, S., Lübbecke, M. and Meijer, H., Minimizing the stabbing number of matchings, trees, and triangulations. Discrete Comput. Geometry 40 (2008) 595–621. Google Scholar
Fischetti, M., Gonzalez, J.J.S. and Toth, P., Solving the orienteering problem through branch-and-cut. INFORMS J. Comput. 10 133–148, 1998. Google Scholar
Grötschel, M. and Holland, O., Solving matching problems with linear programming. Math. Program. 33 (1985) 243–259. Google Scholar
Koch, T. and Martin, A., Solving Steiner tree problems in graphs to optimality. Networks 33 (1998) 207–232. Google Scholar
Kolmogorov, V., Blossom V: a new implementation of a minimum cost perfect matching algorithm. Math. Program. Comput. 1 (2009) 43–67. Google Scholar
Magnanti, T.L. and Wolsey, L.A., Optimal trees. Handbooks in Operations Research and Management Science 7 (1995) 503–615. Google Scholar
Mitchell, J. and O’Rourke, J., Computational geometry. SIGACT News 32 (2001) 63–72. CrossRef
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).
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.
Mulzer, W. and Rote, G., Minimum-weight triangulation is NP-hard. J. ACM 55 (2008) 1–11. Google Scholar
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.
Padberg, M.W. and Rao, M.R., Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7 (1982) 67–80. Google Scholar
B. Piva and C.C. de Souza, The minimum stabbing triangulation problem: IP models and computational evaluation. ISCO (2012) 36–47.
G. Reinelt, TSPLIB. Available online (acessed in March 2011). http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
Shewchuk, J.R., Stabbing Delaunay tetrahedralizations. Discrete and Comput. Geometry 32 (2002) 343. Google Scholar
M. Solomon, VRPTW benchmark problems. Available online (acessed in August 2011). http://w.cba.neu.edu/˜msolomon/problems.htm.
C.D. Tóth, Orthogonal subdivisions with low stabbing numbers, Vol. 3608. Lect. Notes in Comput. Sci. Springer, Berlin/Heidelberg (2005) 256–268.
L.A. Wolsey, Integer Programming. John Wiley & Sons (1998).