# Finding the optimal, spatially compact set of grid cells

I have a regular grid of cells, maybe square, maybe hexagonal.

Each cell has a numeric value associated with it.

How can I find a subset of cells that are:

• a connected, compact set and
• have an optimally high sum of values and
• made of a number n cells

using OR methods or models?

• I am completely new to the field of OR and optimization, so please guide me towards optimizing the question itself if needed. :) Also used just one tag because I am not sure about any terminology. Thanks in advance! – inc42 Jan 5 at 14:14
• How do you define "connected, compact"? There will be a tradeoff between the "compactness" (however, exactly, that is defined) of the set and how large a sum is obtained. You could formulate a single objective to combine these conflicting objectives, or optimize one of them (for instance, sum) while constraining the other (such as upper bound constraint on maximum amount off non-"compactness"). If all cell elements are nonnegative, the largest value of sum is obtained by choosing all cells; so if you wish some other answer, then "compactness" needs to be traded off against it or constrained. – Mark L. Stone Jan 5 at 14:31
• Connected meant that the resulting set of cells should not include any disconnected "island", if connectedness between cells is defined as "touching on the sides" (4 nearest neighbors) or including "touching at their corners" (8 nearest neighbors) is not important to me for now. Compact meant geometric compactness, a set of cells in a spatial circle would better than a set of cells in one long row or column. The third constraint n is a bit hidden in the text but I want to be able to specify the total number of cells to be chosen. – inc42 Jan 5 at 17:03
• You will need to exactly quantify (define) the measure of compactness in order to form a well-specified optimization problem. – Mark L. Stone Jan 5 at 17:35
• Could you point me into the right direction on how to do that in the context of OR and optimisation? I am from the GIS world where I would do geometric operations to check e.g. the "circularity" of the resulting grid set but I assume that would be too complex for a solver, right? – inc42 Jan 6 at 21:16