How to use disjoint constraints with intlinprog? Two variables can't have the same solution (x1-x2 != 0)
1 vue (au cours des 30 derniers jours)
Afficher commentaires plus anciens
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.
0 commentaires
Réponse acceptée
Torsten
le 11 Jan 2016
Modifié(e) : Torsten
le 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.
Plus de réponses (1)
Walter Roberson
le 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 commentaires
Walter Roberson
le 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
Voir également
Catégories
En savoir plus sur Solver Outputs and Iterative Display dans Help Center et File Exchange
Produits
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!