How work with greater tolerance?
Answered
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
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
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
Post is closed for comments.
Comments
3 comments