Thread Subject:

infeasible solution with bintprog

Hi everyone

I am trying to solve an assignment problem with bintprog.
For example, i want to affect a number of houses X to a number of persons Y with constraints. For example, a person can specify a limit max price to buy with.
So, i can be in cases where there are enough houses for the persons but due to this constraint some persons won't have a house affected because it is above their budget.

I want to have here the list of persons who got houses and which ones did they get and also the persons who didn't get any.

But what i am getting is a message of infeasible solution.
It works fine when there is an assignment for each person.

Does bintprog only return a result if there is an assignment for each person?
How can i do it?

Thanks for helping.

P.S: i followed the example of office assignment in the demo
http://www.mathworks.fr/help/toolbox/optim/ug/brn4nmy.html#brn4nnf-1
and i checked that i have no errors

On 11 Jul., 11:00, "matlab " <keep_smiling2...@yahoo.fr> wrote:
> Hi everyone
>
> I am trying to solve an assignment problem with bintprog.
> For example, i want to affect a number of houses X to a number of persons Y with constraints. For example, a person can specify a limit max price to buy with.
> So, i can be in cases where there are enough houses for the persons but due to this constraint some persons won't have a house affected because it is above their budget.
>
> I want to have here the list of persons who got houses and which ones did they get and also the persons who didn't get any.
>
> But what i am getting is a message of infeasible solution.
> It works fine when there is an assignment for each person.
>
> Does bintprog only return a result if there is an assignment for each person?
> How can i do it?
>
> Thanks for helping.
>
> P.S: i followed the example of office assignment in the demohttp://www.mathworks.fr/help/toolbox/optim/ug/brn4nmy.html#brn4nnf-1
> and i checked that i have no errors

Let x_ij = 1, if house i is assigned to person j and 0 otherwise.
Let p_i be the prize for house i and b_j the budget for person j.

Then in order to maximize the number of assignments, you will have to
implement the following model:
max sum_i sum_j x_ij
s.t.
sum_i x_ij <= 1 (j=1,...,number of people)
sum_j x_ij <= 1 (i=1,...,number of houses)
sum_i x_ij*p_i <= b_j (j=1,...,number of people)
x_ij = 0 or x_ij = 1

This problem will always have a solution since (0,0,...,0) is a
feasible point.

Best wishes
Torsten.

Thanks for the answer

> Let x_ij = 1, if house i is assigned to person j and 0 otherwise.
> Let p_i be the prize for house i and b_j the budget for person j.
>
> Then in order to maximize the number of assignments, you will have to
> implement the following model:
> max sum_i sum_j x_ij
> s.t.
> sum_i x_ij <= 1 (j=1,...,number of people)
> sum_j x_ij <= 1 (i=1,...,number of houses)
> sum_i x_ij*p_i <= b_j (j=1,...,number of people)
> x_ij = 0 or x_ij = 1
>
> This problem will always have a solution since (0,0,...,0) is a
> feasible point.
>
> Best wishes
> Torsten.

I did similar thing,
However, instead of sum_i x_ij <= 1, i've put sum_i x_ij = 1 so this probably caused the infeasibility since it implied that each person gets exactly one house.
Now, i changed it into an inequality like you wrote, but now i get x=(0,0,..0) for all solutions even those which has one

On 11 Jul., 12:08, "matlab " <keep_smiling2...@yahoo.fr> wrote:
> Thanks for the answer
>
>
>
>
>
> > Let x_ij = 1, if house i is assigned to person j and 0 otherwise.
> > Let p_i be the prize for house i and b_j the budget for person j.
>
> > Then in order to maximize the number of assignments, you will have to
> > implement the following model:
> > max sum_i sum_j x_ij
> > s.t.
> > sum_i x_ij <= 1 (j=1,...,number of people)
> > sum_j x_ij <= 1 (i=1,...,number of houses)
> > sum_i x_ij*p_i <= b_j (j=1,...,number of people)
> > x_ij = 0 or x_ij = 1
>
> > This problem will always have a solution since (0,0,...,0) is a
> > feasible point.
>
> > Best wishes
> > Torsten.
>
> I did similar thing,
> However, instead of sum_i x_ij <= 1, i've put sum_i x_ij = 1 so this probably caused the infeasibility since it implied that each person gets exactly one house.
> Now, i changed it into an inequality like you wrote, but now i get x=(0,0,..0) for all solutions even those which has one- Zitierten Text ausblenden -
>
> - Zitierten Text anzeigen -

Did you take the vector f in the objective function to be
(-1,-1,...,-1) ?

Best wishes
Torsten.

 
> Did you take the vector f in the objective function to be
> (-1,-1,...,-1) ?
>
> Best wishes
> Torsten.

I have to put f =(-1 -1...-1) , if i want to maximize the function, right?
 however in my case, i have used in f a preference matrix where a person has preferences for closer houses (based on distances i have) and so my objective is to minimize the sum not maximize it.

On 11 Jul., 12:32, "matlab " <keep_smiling2...@yahoo.fr> wrote:
> > Did you take the vector f in the objective function to be
> > (-1,-1,...,-1) ?
>
> > Best wishes
> > Torsten.
>
> I have to put f =(-1 -1...-1) , if i want to maximize the function, right?
> however in my case, i have used in f a preference matrix where a person has preferences for closer houses (based on distances i have) and so my objective is to minimize the sum not maximize it.

And the sum of distances is minimized if nobody buys a house, I guess.
Then I understand that you get (0,0,...,0) as a solution ...
Reflect your objective function again.

Best wishes
Torsten.

>
> And the sum of distances is minimized if nobody buys a house, I guess.
> Then I understand that you get (0,0,...,0) as a solution ...
> Reflect your objective function again.
>
> Best wishes
> Torsten.

yes, you are absolutely right. i want to maximize the assignment while minimizing the distances.
how can i do it? I can't put this as a constraint since i don't know the lower bound (it is different from zero)

On 11 Jul., 13:20, "matlab " <keep_smiling2...@yahoo.fr> wrote:
> > And the sum of distances is minimized if nobody buys a house, I guess.
> > Then I understand that you get (0,0,...,0) as a solution ...
> > Reflect your objective function again.
>
> > Best wishes
> > Torsten.
>
> yes, you are absolutely right. i want to maximize the assignment while minimizing the distances.
> how can i do it? I can't put this as a constraint since i don't know the lower bound (it is different from zero)

Something like
min: sum_i sum_j -p_ij*x_ij
where p_ij is some preference factor of person j for house i comes to
mind (normalized such that sum_i p_ij = 1 for all j).
Maybe it is easiest first to set p_ij = (1/d_ij) / (sum_k 1/d_kj)
where d_ij is the distance between house i and person j.

Best wishes
Torsten.

>
> Something like
> min: sum_i sum_j -p_ij*x_ij
> where p_ij is some preference factor of person j for house i comes to
> mind (normalized such that sum_i p_ij = 1 for all j).
> Maybe it is easiest first to set p_ij = (1/d_ij) / (sum_k 1/d_kj)
> where d_ij is the distance between house i and person j.
>
> Best wishes
> Torsten.
>

Thanks a lot for your replies.

I have the values already normalized.
However if i do like you suggested
min: sum_i sum_j -p_ij*x_ij
 won't this be equivalent to putting f=(-1 -1 -1 ...-1) and maximizing the sum over x_ij .
I mean here the preferences over distances won't be minimized or am i wrong?

On 11 Jul., 13:53, "matlab " <keep_smiling2...@yahoo.fr> wrote:
> > Something like
> > min: sum_i sum_j -p_ij*x_ij
> > where p_ij is some preference factor of person j for house i comes to
> > mind (normalized such that sum_i p_ij = 1 for all j).
> > Maybe it is easiest first to set p_ij = (1/d_ij) / (sum_k 1/d_kj)
> > where d_ij is the distance between house i and person j.
>
> > Best wishes
> > Torsten.
>
> Thanks a lot for your replies.
>
> I have the values already normalized.
> However if i do like you suggested
> min: sum_i sum_j -p_ij*x_ij
> won't this be equivalent to putting f=(-1 -1 -1 ...-1) and maximizing the sum over x_ij .
> I mean here the preferences over distances won't be minimized or am i wrong?

No, but the overall preference (which is proportional to the sum of
inverse distances 1/d when
modelled as p_ij = (1/d_ij) / (sum_k 1/d_kj) ) is maximized.

Best wishes
Torsten.

> No, but the overall preference (which is proportional to the sum of
> inverse distances 1/d when
> modelled as p_ij = (1/d_ij) / (sum_k 1/d_kj) ) is maximized.
>
> Best wishes
> Torsten

Ok, i got it.
You were of a great help,
Thanks

"matlab " <keep_smiling2100@yahoo.fr> wrote in message
news:jtjfb3$l82$1@newscl01ah.mathworks.com...
> Hi everyone
>
> I am trying to solve an assignment problem with bintprog.
> For example, i want to affect a number of houses X to a number of persons
> Y with constraints. For example, a person can specify a limit max price to
> buy with.
> So, i can be in cases where there are enough houses for the persons but
> due to this constraint some persons won't have a house affected because it
> is above their budget.
>
> I want to have here the list of persons who got houses and which ones did
> they get and also the persons who didn't get any.

This sounds like a variant on the stable marriage problem.

http://en.wikipedia.org/wiki/Stable_marriage_problem

where houses that don't meet a person's constraints are considered to be at
the end of their preference list. If a person ends up with such a house at
the end, they don't get a house.

Try coding up the algorithm on that page and see what it gives you.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com