7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – inc42 Jan 5 at 14:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Jan 5 at 14:31
  • $\begingroup$ 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. $\endgroup$ – inc42 Jan 5 at 17:03
  • 2
    $\begingroup$ You will need to exactly quantify (define) the measure of compactness in order to form a well-specified optimization problem. $\endgroup$ – Mark L. Stone Jan 5 at 17:35
  • $\begingroup$ 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? $\endgroup$ – inc42 Jan 6 at 21:16
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – inc42 Jan 5 at 17:19
  • $\begingroup$ 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, ...) $\endgroup$ – Marco Lübbecke Jan 5 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.