False positive on second-order cone feasibility problem
Answered
I'm developing an iterative cutting plane algorithm, and the top problem, which is implementing the cuts, is a feasibility problem with a second-order cone constraint. The second-order cone constraint restricts the solution space to an area around the current best. The performance of the entire algorithm critically depends on the solving time for the top problem, and the solving time is heavily dependent on the Gurobi parameters. However, I realized that Gurobi frequently reports that a feasible solution has been found, although this is false. Often, even variable bounds are violated; for instance, a positively defined variable has a negative value in the results.
My default parameter setup is below. In a minimal reproducible example, Gurobi first reports numerical troubles. If I subsequently increase the Numeric Focus to 1, the algorithm "successfully" terminates with a false positive.
set_optimizer_attribute(model, "NumericFocus", 0)
set_optimizer_attribute(model, "GURO_PAR_BARDENSETHRESH", 10000)
set_optimizer_attribute(model, "BarQCPConvTol", 1e-6)
set_optimizer_attribute(model, "FeasibilityTol", 1e-6)
set_optimizer_attribute(model, "Threads", 10)
set_optimizer_attribute(model, "Method", 2)
set_optimizer_attribute(model, "Crossover", 0)
Some background on the other parameter settings:
- Using a really high value for "GURO_PAR_BARDENSETHRESH" was counterintuitive for me because the algorithm adds a lot of dense constraints during iteration, but it greatly improves the performance by a factor of >30. In the minimal example, not setting the parameter solves the issues, but I could not test it further since the large impact on computation time makes changing this parameter impractical.
- Reducing the number of threads sometimes solves the problem, also in the minimal example, but it is unreliable and obviously comes at the expense of computation time.
- I've also experimented with less precise feasibility and convergence tolerance, which aggravates the problem slightly. However, this is not the case in the minimal example.
I'm working with Julia and JuMP and happy to provide the .mps file and code for a minimal reproducible example. I get the error on 10.0.3 and 12.0.0. Also, I think the coefficient matrix of my problem looks decent.
Coefficient statistics:
Matrix range [4e-03, 1e+04]
QMatrix range [4e-01, 4e-01]
QLMatrix range [8e-03, 1e+01]
Objective range [0e+00, 0e+00]
Bounds range [3e+02, 3e+02]
RHS range [1e-02, 1e+02]
QRHS range [2e+03, 2e+03]
-
-
Gurobi Staff
Thanks, Leonard, for posting your observations here! I created a support ticket so we can investigate the model files.
0 -
-
-
For the public record, Gurobi version 12.0.1 solved the issue Leonard faced with this model and relates to "Fixed bug in implicitly handling lower bounds in cone constraints that can lead to sub-optimal termination for infeasible SOCPs" from our release notes on 12.0.1.
1 -
Please sign in to leave a comment.
Comments
2 comments