How work with greater tolerance?

Answered

Renan Fernando Franco da Silva

• September 04, 2021 00:09
• Edited

Hi,

I'm solving the Bin Packing Problem using the Gilmore and Gomory formulation, which is based on column generation. And I have some cases for this problem where the root relaxation value is equal to the integer solution value.

My problem is that if I stop generating columns when there are no negative cost variables with absolute values less than or equal to 1e-5, the root value will usually be 1e-5 greater than the correct value. And if I choose to work with this gap, my Branch and Pricing Algorithm runtime increases dramatically.

But if I decrease the minimum value to 1e-6, then the Gurobi returns dual values ​​that produce columns that are already in the model, and this leads to an infinite loop.

I would like to know if there is any way to work with greater tolerance. I tried to multiply the constraints and the objective function by 1e3 or 1e-3, in every way I can think of, but it didn't work. I also tried changing the ScaleFrag, ObjectiveFlag, NumericFocus parameters, but that didn't solve the problem either.

Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (linux64)

Thread count: 4 physical cores, 4 logical processors, using up to 1 threads

Optimize a model with 350 rows, 2159 columns and 8035 nonzeros

Coefficient statistics:

Matrix range [1e+00, 5e+00]

Objective range [1e+00, 1e+00]

Bounds range [0e+00, 0e+00]

RHS range [1e+00, 5e+00]

Iteration Objective Primal Inf. Dual Inf. Time

0-6.2727655e+244.023499e+316.272766e-06 0s

2381.3200001e+020.000000e+000.000000e+00 0s

Solved in 238 iterations and 0.02 seconds

Optimal objective 1.320000113e+02

Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (linux64)

Thread count: 4 physical cores, 4 logical processors, using up to 1 threads

Optimize a model with 350 rows, 2164 columns and 8053 nonzeros

Coefficient statistics:

Matrix range [1e+00, 5e+00]

Objective range [1e+00, 1e+00]

Bounds range [0e+00, 0e+00]

RHS range [1e+00, 5e+00]

Iteration Objective Primal Inf. Dual Inf. Time

0-2.6621603e+251.977023e+322.662160e-05 0s

1481.3200001e+020.000000e+000.000000e+00 0s

Solved in 148 iterations and 0.01 seconds

Optimal objective 1.320000106e+02

0

• 

  Jaromił Najman

  Gurobi Staff

  • September 06, 2021 11:45

  Hi,

  You can set the feasibility tolerances via the FeasibilityTol and IntFeasTol parameters. If you would like to make Gurobi focus more on true integer values, you should try experimenting with the IntegralityFocus parameter.

  Best regards,
  Jaromił

  2
• 

  Renan Fernando Franco da Silva

  • September 06, 2021 12:39

  

  

  

  Hi, 
  
  I changed the FeasibilityTol and OptimalityTol parameters, and it really worked. Thank you very much.

  1

Please sign in to leave a comment.