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

1 view (last 30 days)
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.

Accepted Answer

Torsten
Torsten on 11 Jan 2016
Edited: Torsten on 11 Jan 2016
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.

More Answers (1)

Walter Roberson
Walter Roberson on 11 Jan 2016
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
  3 Comments
Walter Roberson
Walter Roberson on 11 Jan 2016
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

Sign in to comment.

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!