Linearization or Approximation on a product of two binary variables

[Kim.S...@gmail.com]

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

[erwin]

(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

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
----------------------------------------------------------------

[Kim.S...@gmail.com]

That's right, but I am not asking what you wrote here.

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 -

[erwin]

How does this violate what you want?

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 -

[erwin]

Sorry I read x*y=1. I don't know a quick answer to your

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

[erwin]

Note that this is essentially:

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
----------------------------------------------------------------

[Kim.S...@gmail.com]

On Jun 9, 5:50 pm, erwin <erwin.kalvela...@gmail.com> wrote:
> Note that this is essentially:
>
> 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

Thanks for your try on this.
It is likely that it is impossible to linearize it.
I am working on approximating it linearly.

[Matthew Saltzman]

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

[Paul Rubin]

Kim.S...@gmail.com wrote:
> That's right, but I am not asking what you wrote here.
>
> What I wanted is expressing or approximating
>
> x+y=1, where x and y are binary variables,
>
> with continuous variables without nonlinear terms..
>

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

[Kim.S...@gmail.com]

As always, you are the best. Thanks for your valuable info. Best, Seon