dual inception creates more variables as we dualize

[guilhermebodin]

Hey guy, a thought I had after the dualize(dualize(model)) == model commentary by @blegat on gitter. Consider the problem

#=
    primal
        min -4x_1 - 3x_2 -1
    s.t.
        2x_1 + x_2 - 3 <= 0  :y_3
        x_1 + 2x_2 - 3 <= 0  :y_4
        x_1 >= 1                   :y_1
        x_2 >= 0                   :y_2
    =#

Following the convention here http://www.juliaopt.org/MathOptInterface.jl/stable/apimanual/#Advanced-1 the dual will be

    dual
        max 3y_4 + 3y_3 + y_1 - 1
    s.a.
        y_1 + 2y_3 + y_4 == -4   :z_1
        y_2 + y_3 + 2y_4 == -3   :z_2   
        y_1 >= 0                        :z_3        
        y_2 >= 0                        :z_4
        y_3 <= 0                        :z_5
        y_4 <= 0                        :z_6

Now note that if we dualize the dual problem it will have 6 variables, if I did not make any mistakes it should be

    dual of the dual
        min 4z_3 + 3z_4 - 1
    s.a.
        2z_3 + z_4 + z_5 == -3.0  
       z_3 + 2z_4 + z_6 == -3.0
        z_1 + z_3 == 0       # I add this to the model, but it doesn't add much to the model
        z_2 + z_4 == 0       # I add this to the model, but it doesn't add much to the model
        z_3 >= 0                        
        z_4 >= 0                        
        z_5 <= 0                        
        z_6 <= 0
        z_1 in Reals        # I don't add this constraint
        z_2 in Reals        # I don't add this constraint

This kind of problem happens because I don't receive the model with the equality and slack variable, so I can't do this primal dual

primal (over x,s):

  min  c'x :          duals
    b - Ax == 0       (y)
    h - Gx == s in K  (z)
dual (over z,y):

  max  -b'y - h'z :      duals
    c + A'y + G'z == 0   (x)
                z in K*  (s)

So the question, it is important to make dualize(dualize(model)) == model to work?

[blegat]

This seems to be due to the fact that in MOI, the primal is kind of: all variables are free and the dual is: all constraint are equalities. This is related to https://github.com/JuliaOpt/MathOptInterface.jl/issues/710 where we plan to add a add_constrained_variables which adds non-free variables. MOIU.AbstractModel does not make any distinction on whether the variables were added with add_variable or add_constrained_variables. You can see in https://github.com/JuliaOpt/MathOptInterface.jl/pull/759 that I modified Utilities/copy.jl to select VectorOfVariables-in-S and SingleVariable-in-S that are considered as variable-constraint, hence the variables are not free. So instead of adding equality constraint for these variables, you should add constraints in S. By doing this, you should recover dualize(dualize(model)) == model.

[blegat]

You can take inspiration from here: https://github.com/JuliaOpt/MathOptInterface.jl/pull/802/files#diff-694aadc2fa89948c303188c206ad2f63L186-R309 to detect free and constrained variables.

[joaquimg]

does it still happen with compact mode?

[blegat]

This was fixed by https://github.com/jump-dev/Dualization.jl/pull/112 for conic problems at least. IIRC, this does not work for scalar sets with nonzero constants (or all scalar sets). Supporting for these sets would be complicated as we would need to do a work equivalent to what variables bridges do (e.g., substitutions etc...) My feeling is that we could drop support for these so that bridges do that part. We could have an option that is used by supports_... so that the support can be added for these scalar sets in case the performance is an issue.