# Enforce connectedness for an IP over a grid

 2 Lets say we have an n-by-n 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: 001100 001100 001000 001000 111111 000000  but the following is not: 001100 001100 000000 000000 000110 001110  asked 14 Jul '13, 06:01 Petter 23●7 accept rate: 0% 4-vertex-connected or 4-edge-connected? How is that first solution 4-connected? I assume you are given a graph as input? (14 Jul '13, 14:46) Austin Buchanan BTW, if you are referring to a grid graph, then no solution will be 4-connected. (14 Jul '13, 14:57) Austin Buchanan Austin: all 1s in the first solution can be reached from any other 1 by moving up, down left and right in the grid. (15 Jul '13, 07:55) Petter I realize that "4-connected" can refer to other things than what I have in mind. I'll remove that word. (15 Jul '13, 07:59) Petter

 3 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 2.5k●3●10 accept rate: 8% Thanks; I'll have a look! (15 Jul '13, 07:56) Petter
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: