[Coin-symphony] How to enforce "at least one variable is zero"

[Michael Hennebry]

On Thu, 3 Jan 2008, Mark Williams wrote:

> On 1/3/2008 2:36 PM, Michael Hennebry wrote:
> > On Thu, 3 Jan 2008, Mark Williams wrote:
> >
> >> I need a constraint of the form "at least one of these (real valued, >=0) variables is zero".


> >> I realize I can do this by creating a parallel set of boolean variables, constraining the sum of those variables to be one, and then adding constraints of the form Vi <= M - M*bi (for suitably large M). But this approach appears to run into severe difficulties (very high runtimes for relatively small problems).
> >
> > Not quite:
> > Vi <= Mi*bi
> > SUM (1-bi) >= 1
> >  i
>
> Im not sure what your point is. I see three differences:
>
> 1) Your bi's are the complement of my bi's.
> 2) You have a separate M for each V
> 3) Your constraint on the bi's is SUM(1-bi) >= 1, while mine is SUM(1-bi)==1
>
> 1) doesnt seem relevant

I just found them easier to think about.

> 2) turns out to be irrelevant for me - the Vi's all have the same range
>
> So are you saying that 3) is a significant difference?

I missed your equality.  I *think* that the difference is unimportant.
Perhaps someone else could chime in.

> > The trick is to pick the smallest M's that will work.

This is what I thought would be important.
I suspected that you were using a single large M.

> > If you work at it, you only need ceil(lg(n)) binaries,
> > where n is the number of variables.
> > I don't know that that would be an improvement.
> >
>
> I hadnt thought of that (except for the n==2 case). Its worth a try, thanks.

Another strategy is to try to branch on
sums of binaries selected on the fly.
Start with the smallest and keep going until you reach one-half.

-- 
Michael   hennebry at web.cs.ndsu.NoDak.edu
"I AM DEATH, NOT TAXES.  *I* TURN UP ONLY ONCE."  --  Death