3
$\begingroup$

I am currently attempting to use a MIP to optimize the agglomeration of sites to fit a minimum size.

Take for example the following simplified situation of 9 sites which could be any range of sizes.

enter image description here

I need a constraint to ensure that the grouped sites work based on their connections. For example {1,2,3}, {1,2,7,8}, {1,2,8,9} all work but {1,6,3} does not because 3 is not connected to either 1 or 6 and {1,2,4,5} wouldn't work because although each site has one connection, they are not connected to each other.

If we let:
$G_{ki}$ = 1 if site i is in Group k and 0 if not.
$a_{ij}$ = 1 if site i and j are connected and 0 if not.
n = number of sites (9 in this example).

Would it be possible to write a mathematical (ideally linear) constraint to define whether a group is valid?

At a base level this leads to: $G_{ki} * G_{kj} <= a_{ij}$ which says sites i and j can only be in the same group if they are connected. But this would invalidate groups like {1,2,3} as 1 and 3 are not connected.

I then tried: $G_{ki} * G_{kj} <= a_{ij} + \sum_{L=1}^n (a_{iL} * G_{kL} * a_{Lj}) $ This works for situations like {1,2,3} as : $G_{k1} * G_{k3} <=a_{13} + a_{12} * G_{k2} * a_{23}$
but not {1,2,3,4} for 1 and 4.

While I could expand that formulation to 4 or even 5, I am hoping there is a better approach that allows for any number of sites to be in a single group.

Note that $n$ gets as high as 110 sites for the actual problem I am trying to solve.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

I don't think there is any way to get a single constraint for each group establishing contiguity.

Assume that we represent the sites as nodes in a graph, with edges between adjacent sites. The link provided by @RobPratt in a comment contains methods for constraining contiguity using flow variables. The catch in this case is that the number of flow variables will be on the order of $n$ times the number of edges in the graph (which is $O(n^2)$), so your model could get rather big rather fast.

Another approach would be to enumerate all possible contiguous groups of sites and use binary variables to select which groups are used (subject to nonoverlap constraints and whatever else is going on in your problem). Enumerating the contiguous groups is logically straightforward if possibly somewhat tedious, but it again will likely jack up the size of the model.

That leads to a couple of additional alternatives, both of which involve identifying some but hopefully not all of the contiguous groups. An exact approach uses the "branch price and cut" approach. A heuristic version works along the lines of the Gilmore-Gomory heuristic for the 1-D cutting stock problem. Basically, you start with an arbitrary set of contiguous groups, solve the LP relaxation of the problem, and use the dual solution to solve a subproblem that finds one or more new groups that are contiguous and look like they would improve the solution of the master problem. Add them in and repeat until no new groups are found, then reinstate the integrality restrictions and solve the resulting MIP.

I'll mention one other approach for completeness, but I definitely do not recommend it. You can try a version of "logical Benders decomposition", in which you add contiguity constraints on the fly as you solve a master MIP problem. When the solver has a candidate solution, it passes the solution to an "oracle" that checks whether each proposed group is contiguous and, if not, sends back one or more constraints to be added to the master problem. The catch is that these will be what are known as "no good" constraints, which are notoriously weak and likely to pile up in large numbers. Using your example, if the proposed solution said that group 1 will consist of sites 6, 7 and 8, a no-good constraint would look like $$G_{16} + G_{17} + G_{18} - \sum_{i\in \lbrace 1,\dots,5,9\rbrace} G_{1i} \le 2,$$ which invalidates that solution but not much else. You could improve the no-good constraints with a bit of work (for instance, by dropping $G_{19}$ in this example since site 9 is not contiguous to either of sites 6 or 7), but I still think the (weak) constraints would pile up awfully quickly.

$\endgroup$
3
  • $\begingroup$ Instead of no-good cuts, you could dynamically generate minimal a-b separator cuts as in Section 3.3 of the linked paper. $\endgroup$
    – RobPratt
    Commented Oct 12, 2022 at 17:28
  • $\begingroup$ @RobPratt So you are thinking that if some group in the candidate solution is not contiguous, you would (a) identify a pair of sites in the group not connected to each other, (b) solve a minimal cut model and (c) add a constraint requiring at least one of the sites in the minimal cut to belong to the group? I think this would work in theory, and a minimal cut constraint would appear to be stronger than a no-good constraint, but I'm not sure if the increased tightness would compensate for having to solve a gaggle of minimum cut problems. Might be an interesting experiment. $\endgroup$
    – prubin
    Commented Oct 12, 2022 at 18:12
  • 1
    $\begingroup$ Yes, that is the idea.. A simple way to get one such minimal cut is to compute connected components of the support graph, take a and b from different components, and take the "moat" around one component (i.e., nodes not in the component of the support graph but adjacent in the original graph to at least one node in the component) as the a-b separator. $\endgroup$
    – RobPratt
    Commented Oct 12, 2022 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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