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

Question

M Coen 2016-1-10

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/263306-how-to-use-disjoint-constraints-with-intlinprog-two-variables-can-t-have-the-same-solution-x1-x2

评论： M Coen 2016-1-11

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Torsten 2016-1-11

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/263306-how-to-use-disjoint-constraints-with-intlinprog-two-variables-can-t-have-the-same-solution-x1-x2#answer_205764

编辑：Torsten 2016-1-11

在 MATLAB Online 中打开

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.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

M Coen 2016-1-11

thanks!

请先登录，再进行评论。

Answer 2

Walter Roberson 2016-1-11

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/263306-how-to-use-disjoint-constraints-with-intlinprog-two-variables-can-t-have-the-same-solution-x1-x2#answer_205726

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 个评论
显示 1更早的评论隐藏 1更早的评论

Walter Roberson 2016-1-11

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 2016-1-11