Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Fmincon: nonlinear binary problem
Replies: 10   Last Post: Apr 12, 2013 7:07 AM

 Messages: [ Previous | Next ]
 Torsten Posts: 1,717 Registered: 11/8/10
Re: Fmincon: nonlinear binary problem
Posted: Apr 12, 2013 7:07 AM

"Anna" wrote in message <kk8mt6\$svi\$1@newscl01ah.mathworks.com>...
> > > I was just thinking that all these 3 constraints can be written as one
> > >
> > > x_ik+x_jk>=2*z_ijk, right?
> > >

> >
> > This condition does not exclude the case that z_ijk=0 although both x_ik and x_jk are equal to 1. So z_ijk is not equal to x_ik*x_jk. It depends on your objective function if z_ijk will automatically be chosen to be 1 if x_ik=1 and x_jk = 1.

>
> True!
>

> >
> > > "Torsten" wrote in message <kk60l8\$l9i\$1@newscl01ah.mathworks.com>...
> > > > Because you substitute x_ik*x_jk = min(x_ik,x_jk) , I think you will need z_ijk:
> > > > z_ijk <= x_ik
> > > > z_ijk <= x_jk
> > > > z_ijk >= x_ik + x_jk - 1

> > >
> > > Good point Torsten. Theoretically, I would need to index z over k but from other constraints I also know that there may be at most one k for which z_ijk=1 and I don't need to know the detailed information which k it is, but only the indication whether it happens at all. Would indexing z_ij be correct in that case? It's important to me to limit the size of the variables as well.

> >
> > I don't think that this is possible. Imagine there are indices k1 and k2 such that, for fixed i and j, x_ik1*x_jk1 = 1 and x_ik2*x_jk2 = 0. Then, if you only introduce z_ij, your problem becomes infeasible.

>
> The original nonlinear objective was
> obj=sum(i) sum (j) sum(k) x_ik*x_jk*p_ij
>
> Maybe my explanation was not clear, I intend to replace sum(k) x_ik*x_jk=z_ij for every i and j. Would that be fine? It seems to me that all the previously proposed constraints should hold. Thank you for all your comments.
>
> Regards,
> Anna

Assume there exists a k1 with x_ik1*x_jk1 = 1 and x_ik*x_jk = 0 for all k not equal to k1.
Then z_ij should be equal to 1 according to your definition.
But then at least one of the inequalities
z_ij <= x_ik
z_ij <= x_jk
for k not equal to k1 is then violated - constraints you intended to impose on the z_ij.
Or do I miss something ?

Best wishes
Torsten.

Date Subject Author
4/9/13 Guest
4/9/13 Bruno Luong
4/9/13 Alan Weiss
4/10/13 Anna
4/11/13 Johan Lofberg
4/11/13 Anna
4/11/13 Torsten
4/11/13 Anna
4/12/13 Torsten
4/12/13 Anna
4/12/13 Torsten