Lets say we have an nbyn grid of binary variables x_ij and a integer programming problem involving those variables (and possibly others). What is the best way of enforcing connectedness (up, down, left, right) between all x_ij which are equal to 1? That is, the following solution is feasible:
but the following is not:
asked 14 Jul '13, 06:01 Petter 
I'd start by reading the answers to this question. It is not exactly the same question, but answers may help. answered 14 Jul '13, 11:21 jfpuget Thanks; I'll have a look!
(15 Jul '13, 07:56)
Petter

4vertexconnected or 4edgeconnected? How is that first solution 4connected? I assume you are given a graph as input?
BTW, if you are referring to a grid graph, then no solution will be 4connected.
Austin: all 1s in the first solution can be reached from any other 1 by moving up, down left and right in the grid.
I realize that "4connected" can refer to other things than what I have in mind. I'll remove that word.