Integer Optimality Cut?

[WalterMadelim]

Why isn't there a module to add integer optimality cut? I wonder.

It's not difficult to implement, for example, my version is like

function add_I_cut(mst, sub; ITE) # add Integer Optimality Cut to the master
    Cd = lps.Cd
    x_check = mst.Xl
    xllen = sub.xllen
    x_check .= 0
    Gurobi.GRBsetdblattrarray(sub.o, "Obj", 1, xllen, x_check) # not a multiplier method
    b2len = sub.b2len
    BTv = fill(Cchar('B'), xllen + b2len)
    Gurobi.GRBsetcharattrarray(sub.o, "VType", 1, xllen + b2len, BTv) # solve integer subproblems always
    Gurobi.GRBsetcharattrarray(mst.o, "VType", 1+S, xllen, BTv) # always generate integer trial points
    θ_LB = Settings.getxdblattrelement(mst, S, "LB") # need to calculate this once at the beginning, before calling of this method
    Settings.opt_and_ter(mst)
    for ite = 1:ITE
        lb,θ_check = Settings.getmodeldblattr(mst, "ObjBound"),Settings.getxdblattrelement(mst,S,"X")
        Gurobi.GRBgetdblattrarray(mst.o, "X", 1+S, xllen, x_check)
        @. x_check = round(x_check)
        Gurobi.GRBsetdblattrarray(sub.o, "LB", 1, xllen, x_check)
        Gurobi.GRBsetdblattrarray(sub.o, "UB", 1, xllen, x_check)
        Settings.opt_ass_opt(sub)
        ObjVal = Settings.getmodeldblattr(sub, "ObjVal")
        vio = ObjVal - θ_check
        println("(I) ite = $ite, vio = $vio, lb = $lb")
        vio < 1e-4 && break
        DIFF = ObjVal - θ_LB
        for (i,e) = enumerate(x_check)
            Cd[i] = e < 0.5 ? DIFF : -DIFF
        end
        Cd[xllen+1] = 1.0
        Cn = ObjVal - DIFF * count(>(0.5), x_check)
        Gurobi.GRBaddconstr(mst.o,xllen+1,sub.Ci,Cd,Cchar('>'),Cn,C_NULL)
        Settings.opt_and_ter(mst)
    end
end;

where, the θ_LB is set by calling the following function beforehand

function give_theta_LB(mst, sub, lps, S; VType)
    xllen = sub.xllen
    b2len = sub.b2len
    BTv = fill(Cchar(VType), xllen + b2len)
    Gurobi.GRBsetcharattrarray(sub.o, "VType", 1, xllen + b2len, BTv)
    Flv = fill(0., xllen)
    Gurobi.GRBsetdblattrarray(sub.o, "Obj", 1, xllen, Flv)
    Gurobi.GRBsetdblattrarray(sub.o, "LB", 1, xllen, Flv)
    Flv .= 1; Gurobi.GRBsetdblattrarray(sub.o, "UB", 1, xllen, Flv)
    Settings.opt_ass_opt(sub)
    lb = Settings.getmodeldblattr(sub, "ObjBound")
    Settings.setxdblattrelement(mst, S, "LB", lb)
    Settings.setxdblattrelement(mst, S, "Obj", 1.0/S) # This will change for multi-scene
    Settings.opt_ass_opt(mst)
end;

[odow]

Do you have evidence this is useful? Any benchmarks on realistic instances with mixed integer state variables?

[WalterMadelim]

Short story: I think these are very weak cuts.

Long story:

First of all, Integer Optimality Cuts are valid only for pure-binary linking variable cases. And to generate such a cut, one has to generate pure-binary trial (linking) vector. However, in practice, we often would at first relax integer constraints of 1st-stage variables so we can generate integer-infeasible trial vectors.

Integer Optimality Cuts is not based on dual variables. It is only based on a one-shot primal-side exact evaluation. So there are exponentially many such cuts. And a bad thing one can see is that these are cuts with dense linear coefficients. It may at most cut off some nearby fractional parts. At other integer-feasible points, this cut is totally dominated.

---

Some of my other notes:

I tend to believe that mixed-integer linking variables are harder than pure-binary linking variables, if the recourse problem is MIP. (But I cannot prove.)

I think the Cutting Plane method (or, row generation) is the best numeric method so far. It's based on a sequence of LP solves, which is fast due to warm-start. Other methods like subgradient method, those have no memory, so they are step length based, which is hard to tune. And some stabilization method (bundle/level/proximal), they are less appealing to me since the hyperparameters in them are too hard to tune.

In terms of the value function approximation of Q(x), i.e. the θ-x cuts, there are three sorts of cuts:

1. Feasibility cuts: c'x >= Const
2. Pure θ cut: θ >= θ_LB
3. Optimality cuts: θ >= c'x + Const, where c is some nonzero vector.

I think only the last type of cuts are worth adding: they can both improve the lower bound and guide the trial vector x's generation (assume the feasible set of x is compact, which is true in real-world cases). Although the feasibility cuts seem plausible, adding them is simply prohibitive in practice---they do not contribute to lower bound ascending.

Edit:

And one more fact about the pure cutting plane method is that it can solve the concave maximization problem exactly, as long as it is initially bounded above. (I know how to prove it now.🥲)