Are there examples of spatially explicit MIP problems?

Question

Disclosure: I am an MSc student in economics, but not an expert by any means in OR.

I am trying to model a spatial MIP problem of an invasive species similar to this academic paper, however, my problem differs in that it models the control of a forest pest moving throughout an $i \times j$ grid killing trees and facing management control constraints. I am using Python and the CPLEX Solver to model and solve my problem.

Conceptually what happens in my problem is that the beetle population moves throughout the gridded landscape and kills a proportion of trees in a cell, but in each time period there is a chance that the beetles will be detected and possibly eradicated. The wall that I am having difficulty in understanding is how you would go about bringing in a spatial element into the problem.

I have found some examples of MIP problems that revolve around production decisions, but I have not found any problems that incorporate a spatial grid element in the development of the problem. I have typed phrases such as the following in Google with no prevail of finding examples remotely similar (many academic articles do not release code, so that sucks):

"CPLEX spatial optimization Python" "Python Bioeconomic Optimization" "CPLEX Cellular Automata optimization" ... I have a hunch my search terms are not optimal...

So I am hoping that someone might be able to point me towards information regarding spatially explicit MIP problems. I apologize if this is not appropriate for the forum, I just don't really know where else to turn to.

Answer 1

You might find the following interesting:

• Beyer et al., "Solving conservation planning problems with integer linear programming", Ecological Modelling 328 (2016) 14–22. They deal with planning units, and the spatial considerations may be limited to "adjacent" v. "nonadjacent" (I'm not sure).
• Haider et al., "A robust optimization approach for solving problems in conservation planning", Ecological Modelling 368 (2018) 288–297. Again, they deal with parcels (something to do with invasive species), and spatial considerations may again be limited to adjacency (something bleeding from one parcel into an adjacent parcel).
• St. John et al., "Optimizing the Geometry of Wildlife Corridors", Operations Research, 2018, vol. 66, no. 6, pp. 1471–1485. This uses polygonal decomposition of the relevant space, rather than a lattice of points, and spatial considerations include contiguous paths and the widths of those paths.

Tangentially related to conservation, I'm coauthor of a conference paper on placement of pollution sensors. The spatial domain is treated as a grid of points, and spatial concerns include probability of detecting a pollution event (tied to the distance from each sensor to the event) and communication between sensors (basically creating a path from every sensor, through other sensors, to a base, with distance limits on the links).

Answer 2

I just searched in Google Scholar for spatial integer programming and found the following (maybe related, as I am not an expert in this area) papers:

The authors in [1] modeled landfill sitting analysis using spatial data and enhanced their results using a factor they called 'compactness'. You can consider this paper like a facility location problem as LarrySnyder610 mentioned in his comment.

The second paper [2] that I found related to your question, presents MIP formulations that optimize the spatial layout of management actions for providing wildlife habitat, over time.

In the third study [3], the authors propose a design method that considers the ecological role of the spatial arrangement of reserve sites in relation to the long-term persistence of metapopulations of the target species. They mentioned three MIP models in the paper aiming for three different objectives that they have, then illustrate the applications fo those models in a case study. This study proposed a design method that accounts for the spatial context of reserve designs by emphasizing the ecological function of the spatial arrangement of reserve sites.

I hope you find these papers helpful.

[1] Lin, Hung-Yueh, and Jehng-Jung Kao. "Enhanced spatial model for landfill siting analysis." Journal of environmental engineering 125.9 (1999): 845-851.

[2] Hof, John, et al. "An integer programming approach for spatially and temporally optimizing wildlife populations." Forest Science 40.1 (1994): 177-191.

[3] Jiang, Yong, Stephen K. Swallow, and Peter WC Paton. "Designing a spatially-explicit nature reserve network based on ecological functions: an integer programming approach." Biological Conservation 140.3-4 (2007): 236-249.