Abstract
Many geospatial optimization models can be formulated as multi-objective linear integer programming (LIP) models. Because geospatial optimization models are much more complicated than regular LIP models, solving large-scale geospatial LIP models may be facilitated through parallel computing. In this paper, we explore the possibility of applying geovisual analytics to promote the search of exact optimal solutions in parallel computing environments. By integrating the potential of visual analytics and high-performance computing, we developed a suite of interactive geovisual tools to dynamically steer the optimization search in an interactive manner. Using a sustainable land use design as a case study, we demonstrate the potential of our approach in solving multi-objective land use allocation problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aerts J, Eistinger E, Heuvelink G, Stewart TJ (2003) Using linear integer programming for multi-site land-use allocation. Geogr Anal 35:148–169
Aldasoro U, Garín A, Merino M, Pérez G (2012) MPI parallel programming of mixed integer optimization problemusing CPLEX with COIN-OR. Technical Report, https://addi.ehu.es/handle/10810/7274
Andrienko G, Andrienko N, Jankowski P, Keim D, Kraak M-J, MacEachren A, Wrobel S (2007) Geovisual analytics for spatial decision support: setting the research agenda. Int J Geogr Inf Sci 21(8):839–857
Applegate DL, Bixby RE, Chvatal V, Cook WJ (2006) The traveling salesman problem: a computational study. Princeton University Press, Princeton
Arciniegas G, Janssen R, Omtzigt S (2011) Map-based multicriteria analysis to support interactive land use allocation. Int J Geogr Inf Sci 25(12):1931–1947
Benichou M, Gauthier JM, Girodet P, Hehntges G, Ribiere G, Vincent O (1971) Experiments in mixed integer linear programming. Math Program 1:76–94
Beru R, Burdet C (1974) Branch and bound experiments in zero-one programming. Math Program 2:1–50
Church RL, Murray AT (2008) Business site selection, location analysis and GIS. Wiley, Hoboken
Crainic TG, Le Cun B, Roucairol C (2006) Parallel branch-and-bound algorithms. In: Talbi E-G (ed) Parallel combinatorial optimization. Wiley, Hoboken
Gorguner M (1997) VBnB: Visual Branch and Bound. Thesis (MS). Brown University
Homeister D (1996) Efficient implementations of parallel branch and cut. In Proceedings of the Fifth SIAM Conference on Optimization
International Business Machines Corp. (1991) Optimization Subroutine Library, Guide and Reference, Release 2. Document SC23-0519-02, IBM Armonk NY
Jankowski P, Fraley G (2009) A geovisual analytics approach to spatial multiple objective optimization. In 24th International Cartographic Conference - The World’s GeoSpatial Solutions, pp 15–21
Keim DA (2002) Information visualization and visual data mining. IEEE Trans Vis Comput Graph 8(1):1–8
Keim DA, Mansmann F, Schneidewind J, Thomas J, Hartmut Z et al (2008) Visual analytics: scope and challenges. In: Simoff SJ (ed) Visual data mining. Springer-Verlag, LNCS 4404, Berlin, pp 76–90
Land AH, Doig AG (1960) An automatic method of solving discrete programming problems. Econometrica 28:497–520
Ligmann-Zielinska A, Church RL, Jankowski P (2008) Geospatial optimization as a generative technique for sustainable multiobjective land-use allocation. Int J Geogr Inf Sci 22(6):601–622
Linderoth JT (1998) Topics in parallel integer optimization. Dissertation (PhD). Georgia Institute of Technology
MacEachren AM (2004) Geovisualization for knowledge construction and decision support. IEEE Comput Graph Appl 24(1):13–17
Malczewski J (2004) GIS-based land-use suitability analysis: a critical overview. Process Plan 62:3–65
Özaltın OY, Hunsaker B, Ralphs TK (2007) Visualizing Branch-and bound Algorithmst [online]. Available from: http://www.optimization-online.org/DB_FILE/2007/09/1785.pdf. Accessed 11 Jan 2015
Padberg M, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev 33:60–100
Ralphs TK, Ládanyi L, Saltzman MJ (2004) A library hierarchy for implementing scalable parallel search algorithms. J Supercomput 28:215–234
Tong D, Murray AT (2012) Spatial optimization in geography. Ann Assoc Am Geogr 102(6):1290–1309
Ward DP, Murray AT, Phinn SR (2003) Integrating spatial optimization and cellular automata for evaluating urban change. Ann Reg Sci 37:131–148
Xiao N, Bennett DA, Armstrong MP (2007) Interactive evolutionary approaches to multiobjective spatial decision making: a synthetic review. Comput Environ Urban Syst 31:232–252
Xu Y (2007) Scalable algorithms for parallel tree search. Dissertation (PhD). Lehigh University
Xu Y, Ralphs TK, Ladányi L, Saltzman MJ (2009) Computational experience with a software framework for parallel integer programming. INFORMS J Comput 21(3):383–397
Acknowledgments
This work was supported by the National Natural Science Foundation of China under Grant [Nos. 41023001, 41271400, 40901190]. We are grateful to Li Zheng, Zhuoqun Zeng and Shuai Ma at Wuhan University, who contributed to developing the program to visualize parallel computational load.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: H. A. Babaie
Rights and permissions
About this article
Cite this article
Zhang, T., Hua, G. & Ligmann-Zielinska, A. Visually-driven parallel solving of multi-objective land-use allocation problems: a case study in Chelan, Washington. Earth Sci Inform 8, 809–825 (2015). https://doi.org/10.1007/s12145-015-0214-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12145-015-0214-6