Using information on feasible solutions in Branch-and-Benders-Cut

進行中

Tjard Bätge

• 2024年04月23日 13:59

Dear all,

in my research I am solving a facility location type problem (MILP) via classical Benders Decomposition using the Gurobi Python API and user callbacks. My callback applies Benders cuts (lazy constraints) every time a new integer solution (MIPSOL) is found and in the root node (MIPNODE and NODCNT=0). This implementation works fine. 

However, I would like to speed up my algorithm and have encountered two difficulties that I think are connected:

1) I have a reasonably good construction heuristics. I would like to specify some values for the integer variables of my problem using the "Start" attribute of the variables. I want Gurobi to calculate the other variables' values. My Benders callback now calculates that the start solution is infeasible for the original problem and optimality cuts need to be applied. Now I know the high-quality solution that is feasible for the original problem that I want to use and start from. However, Gurobi keeps the objective of the start solution from before the cuts, which is infeasible for the original problem and should be cut off, as the best know primal bound. The algorithm then fails and convergences to some infeasible solution. Why is that? And how can I use my construction heuristic solution to "warm start" the BnBC? 

2) Every time a feasible integer solution to the primary problem is found that is better than the best known solution, my Benders callback is executed. If optimality cuts are applied, the solution is infeasible to the original problem and the objective is discarded. However, I might now have found a new primal bound to the problem. That is why, I want to use cbSetSolution (and cbUseSolution) to specify the values of this feasible solution, which I know is better than the best known solution, to update the primal bound of the search tree. However, Gurobi does not update the primal bound and it can sometimes take very long for Gurobi to find this solution "on its own". Why is that? And how can I force Gurobi to update the primal bound immediately when I find a new better feasible solution?

I would appreciate any help and am happy to elaborated further on my problems / questions. 

Thank you so much!

Tjard

関連するエンティティ

• Callbacks
• Bender's

0

• 

  Mario Ruthmair

  Gurobi Staff

  • 2024年05月06日 13:26

  Hi Tjard,

  I have an idea of what could be the reason for this behaviour, but let me first try to understand your Benders model and approach correctly. Please correct me on the following statements:

  • Your model contains binary or general integer variables in the constraints and continuous variables in the objective.
  • The integer and continuous variables are not related (correctly) in the beginning, this is what the Benders optimality cuts are fixing in the lazy constraint callbacks.
  • You provide solution values for all integer variables, and the solver computes the corresponding values for the continuous variables. However, those are incorrect since some Benders cuts are still missing.
  • You add the Benders cuts and would expect that the same integer solution from before with different values for the continuous variables is found by the solver or accepted if you provide it.
  • But what happens is that the integer part of the solution from before is considered as being infeasible and ignored from now on.

  Is this true?

  Best regards,
  Mario

  0
• 

  Tjard Bätge

  • 2024年05月06日 14:36

  

  

  Hi Mario,

  thank you for your quick response.

  All of your statements are correct. However, some notes:

  • First statement: The objective of the primary (master) problem contains both, binary / integer and continuous, variables. The continuous variables are the auxiliary variables that are being restricted by the optimality cuts during the solution process. 

  • Last statement: The integer part is "ignored from now on" implies that it is not found later on. However, a solution of identical value is often found again, but (much) later in the search. Additionally, the infeasibility results from the continuous variable of the before solution "being too good", not from the integer part being infeasible after applying the optimality cut.

  Best regards,

  Tjard

  0
• 

  Mario Ruthmair

  Gurobi Staff

  • 2024年05月07日 08:05

  Thanks, Tjard, for the additional information. There could be an issue with the solver. We are currently trying to reproduce it using a small example.

  0
• 

  Tjard Bätge

  • 2024年05月07日 09:09

  

  

  Thank you again for looking into this issue. Let me know if I can assist in any way. 

  0

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