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

[Michael Hennebry]

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

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

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