Dual bound not increasing - callbacks with binary variables

Answered

Caio Tomazella

March 21, 2025 13:57

• 
• 

I am currently having an issue with my B&C algorithm, in which I need to add cuts (with addLazy) to make a variable assume a certain value if two conditions happen

My case is, i got a continuous variable Z, that will have the minimum value of two linear expressions f or g. The first condition is given by a binary variable X, that is 1 if Z needs to have a value at all, and the second is Y, to decide for the minimum value.

My modeling is the following

Z >= f - M(1 - X + Y)

Z >= g - M(2 - X - Y)

This way, Z only has a positive value with  X = 1, and if Y = 1, it is equal to g (f otherwise)

The X variables are related to the other variables of the model, while Y is only used for this one. I only add these cuts when needed.

Currently, when I solve, I converge to a solution in which X are all integer quickly, but the solver keeps branching on nodes in which Y are continuous, and the dual bound gets stuck.

Any idea what I can do to solve this issue? My colleague did some preliminary tests with the same constraints but other solver and it converged to the global optimum (the same I'm finding with X).

0

• 

  Erik Halseth

  • Gurobi Staff

  March 30, 2025 14:31

  Hello Caio,

  Thank you for reaching out to the community forum. We appreciate your contribution.

  To respond to your comments around your observations during optimization, have you first considered reformulating your original equations for simplification?

  One such approach is in the following. Noting that your equations result in g when (X=1, Y=1) or otherwise, f, we can convert to a quadratic scenario in which:

  
  Z >= fXY

  Z >= gX(1-Y)

  We could do better than this if we introduce the constraint Y_1 + Y_2 = X (X =1 if Y_1 or Y_2 is 1) that results in:

  Z >= Y_1*f + Y_2*g

  Y_1 + Y_2 = X

  So that ultimately results in one quadratic constraint. Please also experiment with PreQLinearize on top of this new formulation when optimizing so that Gurobi has an opportunity to do a more efficient reformulation. Regarding PreQLinearize, please have a look at this.

  Please let us know your feedback.

   

  Warm thanks,

  Erik H.

  0

Please sign in to leave a comment.