LazyCut Callback with wrong or unstable results

ユーザーの入力を待っています。

John Feng

2025年10月29日 03:28 編集済み

• 
• 

Hi, I am using the C++ API to implement a callback to yield lazy cuts. This is an implementation of the Benders decomposition method. Initially, the master problem has no constraints. Like

max t

s.t. t ≤ a^k x + b^k, (lazy cuts)

I have some problems:

(1) In some instances, the solver outputs the wrong result, i.e., with the objective value being zero. This can be corrected by setting the Heuristics parameter off.

(2) If we set the domain of t to [0, GRB_INFINITY], the solver will always report that the problem is unbounded. It seems the solver skips the check of lazy constraints, or it never enters the callback function.

(3) The solver is unstable, as the objective values vary if we set on or off parameters such as Heuristics, Cuts, and I think the change exceeds reasonable tolerances.

(4) following (3), the objective values also have a gap with the true optimal values (obtained via solving a another model with Gurobi).

I don't know if some of the problems are expected behaviors of the solver (such as the above (2)) or if there are possible bugs (such as the above (1)).

関連

• Parameters
• Callbacks
• Bender's
• Lazy Constraints

1

• 

  Gwyneth Butera

  • Gurobi Staff

  2025年10月29日 19:53

  Hi John - Just to be sure, have you set the LazyContstraints parameter to 1? Thanks.

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年11月02日 08:23

  Hi John,

  Certainly 2) is completely expected.  For Benders Decomposition you would apply the lazy constraints when solutions are discovered.  If t is not bounded above then it is very easy for Gurobi to deduce the problem is unbounded and there will be no solutions to trigger the callback.  This is standard practice - see θ ≥ M in the formulation described here (here theta is bounded below because it is being minimized): https://jump.dev/JuMP.jl/stable/tutorials/algorithms/benders_decomposition/

  The other issues you describe will be issues in your implementation, not the solver.

  Here are some tips.

  * In the subproblem set InfUnbdInfo=1.  If your subproblem is in primal form you will need to construct your feasibility cuts with information from FarkasDual.  If your subproblem is in dual form you will need to construct your feasibility cuts with information from UnbdRay.

  * FarkasDual and UnbdRay may not be available if the subproblem terminates during barrier.  For this reason it is advisable to use either primal simplex, dual simplex, or both (with concurrent LP), to solve all subproblems, or at least until you no longer need feasibility cuts.

  * You can either build your subproblem by replacing the master variables with their values from the master solution, or you can keep them as variables and fix the values of the variables.  If you do the latter it can be tempting (when using the primal form of the subproblem) to fix the variables by their bounds and use RC in place of dual values - this will not likely work when the subproblem is infeasible. You should fix the values by constraints instead and query the dual values.

  * With respect to the undecomposed problem, if your objective coefficients for variables which would belong to the subproblem are all zero, then you may need to make modifications to the subproblem depending on whether it is in primal or dual form - but let's not worry about this unless this case holds.

  - Riley

   

   

  0

サインインしてコメントを残してください。