(1) x+y=1 where x, y are binary variables.
Of course, we can change this into
(2) x'+y'=1, x'y'=0 where x',y' are nonnegative continuous variables.
However, it has a nonlinear term (x'y'=0) which can't be linearized.
I am hoping anyone can tell me that either
any linearization or approximation method for (1) with continuous
variabes but without any nonlinear term,
or
any approximation method for x'y'=0 expressed in continuous
variables.
Any help would be appreciated.
Best, Seon
This can be expressed as:
x= 1
y= 1
In general z=x*y with x,y binary can be expressed:
z <= x
z <= y
z >= x+y-1
0<=z<=1
x,y binary
See http://groups.google.com/group/sci.op-research/browse_thread/thread/c45387ea26c8bf6c
about setting up schedule for golfers for an example.
----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
erwin.ka...@gmail.com, http://www.gams.com/~erwin
http://amsterdamoptimization.com
----------------------------------------------------------------
What I wanted is expressing or approximating
x+y=1, where x and y are binary variables,
with continuous variables without nonlinear terms..
On Jun 9, 4:51 pm, erwin <erwin.kalvela...@gmail.com> wrote:
> (1) is already linear. May be you mean:
> x*y=1
> x,y binary
>
> This can be expressed as:
>
> x= 1
> y= 1
>
> In general z=x*y with x,y binary can be expressed:
>
> z <= x
> z <= y
> z >= x+y-1
> 0<=z<=1
> x,y binary
>
> Seehttp://groups.google.com/group/sci.op-research/browse_thread/thread/c...
> about setting up schedule for golfers for an example.
>
> ----------------------------------------------------------------
> Erwin Kalvelagen
> Amsterdam Optimization Modeling Group
> erwin.kalvela...@gmail.com,http://www.gams.com/~erwinhttp://amsterdamoptimization.com
> ----------------------------------------------------------------
> On Jun 9, 7:35 pm, Kim.Seo...@gmail.com wrote:
>
>
>
> > I am working on approximation problem on a product of two binary
> > variables.
> > Here is the equation:
>
> > (1) x+y=1 where x, y are binary variables.
>
> > Of course, we can change this into
>
> > (2) x'+y'=1, x'y'=0 where x',y' are nonnegative continuous variables.
>
> > However, it has a nonlinear term (x'y'=0) which can't be linearized.
>
> > I am hoping anyone can tell me that either
>
> > any linearization or approximation method for (1) with continuous
> > variabes but without any nonlinear term,
>
> > or
>
> > any approximation method for x'y'=0 expressed in continuous
> > variables.
>
> > Any help would be appreciated.
>
> > Best, Seon- Hide quoted text -
>
> - Show quoted text -
x=1
y=1
x,y continuous
----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
erwin.kalvela...@gmail.com, http://www.gams.com/~erwin
http://amsterdamoptimization.com
----------------------------------------------------------------
> > - Show quoted text -- Hide quoted text -
x+y=1
x,y binary
while removing the binary variables.
Erwin
On Jun 9, 8:21 pm, erwin <erwin.kalvela...@gmail.com> wrote:
> How does this violate what you want?
>
> x=1
> y=1
> x,y continuous
>
> ----------------------------------------------------------------
> Erwin Kalvelagen
> Amsterdam Optimization Modeling Group
x,y=0,1 OR x,y=1,0
ie
x=0 OR 1
y=1-x
I think if you can do this linearly without integer variables
then we no longer need MIP solvers.
Erwin
----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
erwin.kalvela...@gmail.com, http://www.gams.com/~erwin
http://amsterdamoptimization.com
----------------------------------------------------------------
Thanks for your try on this.
It is likely that it is impossible to linearize it.
I am working on approximating it linearly.
The feasible points to your constraints are (0,1) and (1,0). The best
continuous linear approximation you can find is the convex hull of the
feasible points. In this case, x >= 0, y >= 0, x + y = 1. Anything else
will involve nonlinearities or imposing the binary constraints.
>
> Best, Seon
>
--
Matthew Saltzman
Clemson University Math Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs
Can't be done. A system of linear constraints (any mix of equalities
and inequalities) using continuous variables will define a convex
feasible region. If (x,y) = (1,0) and (x,y) = (0,1) are both in that
region, then any point (x,y) = (a,1-a) with 0 <= a <= 1 will be as well.
As Erwin suggests, if you could do this, you would wipe out the market
for MIP solvers. You might also get pretty close to a proof that P = NP.
/Paul