How work with greater tolerance?
AnsweredHi,
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 1e5, the root value will usually be 1e5 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 1e6, 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 1e3, 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
06.2727655e+244.023499e+316.272766e06 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
02.6621603e+251.977023e+322.662160e05 0s
1481.3200001e+020.000000e+000.000000e+00 0s
Solved in 148 iterations and 0.01 seconds
Optimal objective 1.320000106e+02

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 
Hi,
I changed the FeasibilityTol and OptimalityTol parameters, and it really worked. Thank you very much.1
Please sign in to leave a comment.
Comments
2 comments