Try to propagate bounds in equalities

[vtjeng]

This results in an error message, even though we could reason that -2 <= z <= 6.

@variable(m, -1 <= x <= 1)
@variable(m, 3 <= y <= 5)
@variable(m, z)
@constraint(m, x+y == z)
u = @switch(
    (z <= 0) => 0,
    (z >= 0) => 1,
)

[rdeits]

Yeah, this is probably doable, but it can get arbitrarily complicated if, for example, x doesn't have bounds but has its own equality constraint on some variable a which has an equality constraint on variable b and so on...

The solution to this (and #27 ) is to actually solve a linear program for each variable to compute the "real" bounds on that variable within the model. But it only really makes sense to do that at the end of constructing the model. That will require re-thinking the way this package works.

[rdeits]

More specifically, this really can only work if we don't choose a big-M when you call @switch() but instead wait until just before you call solve() and work out all of the bounds once then. That probably requires JuMP to allow us to add callbacks or special constraint types (fortunately, I think this is coming in the newest JuMP version)

[vtjeng]

If I know that the dependencies in my graph constitute a dag and I'm specifying my constraints in order, would it be possible to calculate (weak) bounds on x, a and b (and so on?) I'm happy to take a stab at writing the relevant code.

[rdeits]

Sure! I would suggest writing a function like tighten_bounds!(v::Variable) that goes through each constraint containing that variable and tries to use it to derive tighter bounds for the variable (and then calls setupperbound() and setlowerbound()). You could then decide to call that in your code (it'll be computationally inefficient if your constraints aren't a DAG, but should work anyway).

[vtjeng]

Here's a rough sketch of two possible approaches (with some design decisions in each); I'd appreciate feedback.

• Use tighten_bounds!(v::Variable) as described.

  • The default behavior for tighten_bounds!(v::Variable) is to tighten bounds for variables that v depends on if and only if the variables do not already have bounds. This works well in the case where you specify constraints sequentially. (You can also pass a flag to attempt to tigthen the bounds on any variable that v depends on.
  • Bounds tightening only inspects the tree of tree dependencies to depth 1. For example, in the following code chunk, z actually can only take on value 0, but the naive tightening approach doesn't use information on the correlation between x and y and decides that the best bounds it can provide are -2<=z<=2.

  @variable(m, -1<=x<=1)
  @variable(m, y)
  @variable(m, z)
  @constraint(m, x == -y)`
  @constraint(m, z == x+y)

• Have bounds immediately calculated when specifying equalities, by writing wrapper functions for equality constraints (e.g. @constraint(m, z==x+y)), that do the appropriate interval arithmetic. This is a lot less general (but meets my immediate needs)