8

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?

example of grid with value labels

inc42
  • 189
  • 2
  • 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 05 '20 at 14:14
  • 1
    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 05 '20 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 05 '20 at 17:03
  • 2
    You will need to exactly quantify (define) the measure of compactness in order to form a well-specified optimization problem. – Mark L. Stone Jan 05 '20 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 06 '20 at 21:16
  • Can you describe how you would decide which of two sets of connected cells are more compact? is it as simple as the compactness is the maximum of all row widths and heights? Or based on a ratio of largest row width or height to smallest? Something else? Some criteria might be easier for a solver to handle than others, nut you might as well start off by telling us your "dream" criterion. I suggest you edit that into your question, which will also attract viewership/potential responders to see the info you've added. – Mark L. Stone Jan 06 '20 at 22:05

1 Answers1

5

This problem occurs, in particular, as a subproblem is districting problems. You can represent your problem as a node weighted graph, where there is a node for each cell that receives the respective weight. Then you look for a maximum weight connected subgraph with compactness constraints. The (spatial) compactess is a huge topic in itself and you may find hints when looking into the political districting literature.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Marco Lübbecke
  • 5,919
  • 22
  • 64
  • Interesting! So I would model the connectedness/neighborhoods as edges between the nodes? I found "Solving the Maximum-Weight Connected Subgraph Problem to Optimality" by El-Kebir and Klau, would that be suitable for this approach (I did not see mention of constraints on a quick look)? – inc42 Jan 05 '20 at 17:19
  • yes, this seems to be a good approach; I believe that generally a MILP approach is good since you need to add extra constraints concerning "compactness" (something like bounding the diameter, enforcing large area, ...) – Marco Lübbecke Jan 05 '20 at 20:30