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's gravatar image

Petter
236
accept rate: 0%

edited 15 Jul '13, 08:00

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

I'd start by reading the answers to this question. It is not exactly the same question, but answers may help.

link

answered 14 Jul '13, 11:21

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

Thanks; I'll have a look!

(15 Jul '13, 07:56) Petter
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×231
×101
×5

Asked: 14 Jul '13, 06:01

Seen: 954 times

Last updated: 15 Jul '13, 08:00

OR-Exchange! Your site for questions, answers, and announcements about operations research.