search

hdavid16 / DisjunctiveProgramming.jl

A JuMP extension for Generalized Disjunctive Programming
MIT License
27 stars 3 forks source link

Is it possible to save a Logical variable if I have a disjunction of merely two alternatives? #106

Open schlichtanders opened 6 months ago

schlichtanders commented 6 months ago

Hi there,

the documentation advises to create on logical variable per Disjunct. I am wondering, whether this can be simplified in the case of only two Disjuncts.

Maybe one can reduce the number of needed variables down from 2 to 1 because one Logical variable might represent two options.

hdavid16 commented 6 months ago

Hi @schlichtanders , when adding a disjunction, the Exactly 1 logical variable is selected constraint is added (unless exactly1 = false in the disjunction macro). If you have a disjunction with 2 options, you will have Select exactly 1 option (y1 or y2) which will be formulated to the algebraic constraint y1 + y2 = 1. During presolve, the solver will likely replace y2 with 1-y1, which is essentially what you are describing. That way when y1 = 1 the first disjunct is selected, and when y1 = 0 (meaning y2 = 1) the second disjunct is selected.

So presolve will likely take care of reducing the variables from 2 to 1.

pulsipher commented 6 months ago

@hdavid16 I think it may be worth keeping this feature request open to only use one logical variable when there are two disjuncts. For linear/quadratic problems that are compatible with solver like Gurobi I agree that a presolver will likely take care of the redundancy. However, for general MINLP solvers I don't think this will be the case for most solvers. Hence, for nonlinear problems, I think this would be a worthy feature addition.

hdavid16 commented 5 months ago

I don't think we should support it. This would complicate the syntax a bit. How would you define the second disjunct constraint? @constraint(m, x <= b, Disjunct(\neg Y))? We would have to support expressions inside the Disjunct tag. I don't know if it is worth taking such a shortcut.

pulsipher commented 5 months ago

I don't think we should support it. This would complicate the syntax a bit.... I don't know if it is worth taking such a shortcut.

I think this feature addition would be more than a convenient shortcut, but rather a way to construct better formulations.

How would you define the second disjunct constraint? @constraint(m, x <= b, Disjunct(\neg Y))? We would have to support expressions inside the Disjunct tag.

It would be a relatively simply feature addition to have Disjunct accept \neg Y and only that. Then we could add a flag to the data structure to know if the negation should be used on the indicator or not.

Alternatively, we could keep the user API the same and instead check when reformulating if there are only 2 disjuncts. If there are then we can reformulate using only one indicator variable instead of two. This could be an opt-in feature, to prevent any surprises.

hdavid16 commented 5 months ago

Yeah, this could be a behind the scenes feature because it will only work if the disjunction is not Nested and the exactly1 relation is enforced on the logical variables. So letting the user do this has some gotchas