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

[Mark Williams]

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".
>>
>> Initially, I thought I could use "user_is_feasible", "user_shall_we_branch" and "user_select_candidates". But it looks like this kind of branching (where each child constrains a different variable) is not supported.
> 
> You will need to do something nonlinear.
> The condition allows (1, 0) and (0, 1), but not (0.5, 0.5).

Yes. I was hoping to do it by branching. eg for n==2, I should be able to produce two sub-problems, one with V0 constrained to be zero, and one with V1 constrained to be zero.

In principle it looks no different than any other form of branching. But it looks like SYMPHONY doesnt allow for it.

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

> The trick is to pick the smallest M's that will work.
> 
> 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.

Mark Williams