How to use disjoint constraints with intlinprog? Two variables can't have the same solution (x1-x2 != 0)

Hi,

I have a a number of people which have to go into rooms in pairs. If two people know each other they cannot go into the same room (and some cost function to maximize). I was trying to use intlinprog and having the solution vector be the people, where the value of the vector at each position is the room each person goes to.

Eg:

x1 (Joe)
x2 (Mary)

There are 3 rooms. So the bounds are:

   1 <= x1,x2 <= 3

Joe knows Mary so my constraint would be:

x1-x2 != 0

Since they have to go to different rooms. How do I add this constraint to intlinprog? Any light shed on this ways to solve this problem would be greatly appreciated.

Answer 1

[Torsten]

x_ij decision variable ; x_ij = 1 if person i enters room j, x_ij=0 else.

For Mary and Joe and three rooms this means that the three inequalities

   x_Mary,1 + x_Joe,1 <= 1
   x_Mary,2 + x_Joe,2 <= 1
   x_Mary,3 + x_Joe,3 <= 1

must hold.

Best wishes

Torsten.

[M Coen]

thanks!

Answer 2

[Walter Roberson]

It turns out you cannot solve those kinds of problems using linear programming. There is a good argument shown at http://math.stackexchange.com/questions/37075/how-can-not-equals-be-expressed-as-an-inequality-for-a-linear-programming-model

[M Coen]

Ok so should I just write my own search algorithm? What about fmincon? Any way it does integer programming?

[Walter Roberson]

fmincon does not handle integer programming.

ga supports integer programming, but is not certain to find the global minima.

One thing you can do is divide up into regions each of which is convex, and find the solution on each region, and then pick the best solution.

Also if the problem is symmetric in change of variables, if cost(A,B) = cost(B,A), then instead of imposing an inequality constraint A<>B, impose A<B which is valid for linear programming. It is [1 -1]*[A;B] <= -eps(realmin) . Or since A and B are integer, [1 -1]*[A;B] <= -1

[M Coen]

ok great, thanks!