Multiple user cut

Specific Domains Optimization (Mathematical)
1

Hi,
I am using a solver indipendent callback to add user cut withing a for loop, in a bilevel opt model. They are of the form:

function MyUsercutRelaxedSD(cb_data)
#Get var
...
for t in T
				SDrelcon = 
 				@build_constraint(LL_Primal[t]<=LL_Dual[t])
 				MOI.submit(MyMod, MOI.UserCut(cb_data), SDrelcon)
end
end#callback func

then calling as usual with

set_attribute(MyMod, MOI.UserCutCallback(), MyUsercutRelaxedSD)

Question is, am I actually adding all the t \in T different contraints to the call back? And if not, should i create a vector of cns with @build_constraint and how (?) before calling MOI.submit(.)?

Regards,
Fabrizio

2

Yes, assuming the solver supports multiple user cuts in a single call. If you didnt get an error and this callback made the solve faster then i guess it worked. You can also check the return of MOI.submit.

This sort of thing is hard/impossible to debug.

If you need more control, youll need to write a solver-specific callback for the particular solver that you are using.

3

Thanks for your reply @odow, I’am using Gurobi and it should be able to receive multiple cuts. I gave a try with COPT and it also not complaining. But the issue is that:

  • passing a single, aggregated, u cut that sum over t \in T Primal[t] and Dual[t] above, the result is correct, even if actually the cut is not beneficial, but this is another issue
  • using T disaggregate u cuts as explained above, the results is wrong in terms of OF, it is higher indicating i am actually cutting optimal solution(s)
  • but the Lower Level is separable in t, therefore this theoretically should not be the case, that brings me to think i am actually not inserting all T user Cuts separately, but maybe only the last one, the Tth.
  • I have tryes to get a return value from .submit call,

Resp=MOI.submit(MyMod, MOI.UserCut(cb_data), SDrelcon)
@printf(“resp=%s\n”,Resp)

but i get a laconic “nothing”

  • I have also tried to indexing a vector of user cuts and submit with

SDrelcon[t] = @build_constraint(LL_Primal[t]<=LL_Dual[t])
MOI.submit(MyMod, MOI.UserCut(cb_data), SDrelcon[t])

but i get an error, “SDrelcon not defined”. Does @build_constraint() support the costruction of a vector of cns(?)

any suggestion welcome, thanks again,
Fabrizio

4

Did you consider potential numerical issues? The results returned by a solver are typically subject to +/- epsilon precision. It might be that the epsilon-terms cancel out in the sum over all t, but this might not be the case if you create a cut for each t. In the latter case, you might cut more away than you want.
You could try to manually add epsilon-terms in the cut (in the direction you need), to avoid potential numerical issues if it applies to your problem.

5

Thanks for your reply @mike_k but i do add an \eps in the cut violation check, i don’t think its this is the problem. Besides for @odow, the error above was my mistake, in fact i initialize a vector

SDrelcon=Vector{ScalarConstraint}(undef,length(T))

and now this works fine:

SDrelcon[t] = @build_constraint(LL_Primal[t]<=LL_Dual[t])
MOI.submit(MyMod, MOI.UserCut(cb_data), SDrelcon[t])

and it works exactly as in the non indexed version, as you envisioned, so there should be some conceptual issue i am try to face

thanks for the moment,
Fabrizio

6

Take a read of https://www.gurobi.com/documentation/11.0/refman/c_cbcut.html. In particular:

Note that cuts should be added sparingly, since they increase the size of the relaxation model that is solved at each node and can significantly degrade node processing speed.

You should consider setting parameter PreCrush to value 1 when adding your own cuts. This setting shuts off a few presolve reductions that can sometimes prevent your cut from being applied to the presolved model (which would result in your cut being silently ignored).

User cuts are really hard to debug because there are a hint to the solver, they don’t change the solution, only the solution speed.

Your original code is how I would write the loop. The question is whether this improves the solution speed of Gurobi. That’s an open question. It may also be that Gurobi is just ignoring your cuts because it already found them (or something better).

but i get a laconic “nothing”

Yes, this is my fault. UserCut doesn’t report acceptance, only HeuristicSolution.

7

Thanks @odow for this added reccomandations, however i know/considered all, the Precrush is set to 1, i also switched off the DualReductions (which alone is able to speed up the complete dual increase in the problem, closing the MipGap much faster…but i don’t know why).
As for the size, the user cut added are cheap and sparse, the thing is that they are ineffective, so it must be a conceptual issue related to my problem. From the JuMP side, i can confirm that to the first question, the anwer is yes, the t .in T cuts are actually all added, there is no need to add a vector and then add one by one

Regards,
Fabrizio

2 Likes