False positive on second-order cone feasibility problem
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 -
-
I'm reactivating this thread since I have a new, closely related issue. The original problem occurred in a model that could get very large due to the constraints the cutting plane algorithm added and the update to Gurobi 12.0.1 mostly resolved it.
Now I'm trying to solve similar problems with a local gradient method. As a result, the problems remain small, but the quadratic constraint is still used for regularization. Again, I'm observing constraint violations, but now they exclusively occur in the SOC constraint. Below, I provided the code that manually checks if the SOC from the .mps file holds.
I'm happy to share the corresponding .mps files and have thoroughly checked that I copied the SOC from the .mps file correctly. I'm using Gurobi 12.0.1 and v1.7.0 of the Gurobi Julia package.
using JuMP, Gurobi # load model from file mod = read_from_file("test.mps") set_optimizer(mod, Gurobi.Optimizer) # set high accuracy and solve set_optimizer_attribute(mod, "Method", 2) set_optimizer_attribute(mod, "NumericFocus", 3) set_optimizer_attribute(mod, "BarConvTol", 1e-10) set_optimizer_attribute(mod, "BarQCPConvTol", 1e-10) set_optimizer_attribute(mod, "FeasibilityTol", 1e-9) optimize!(mod) # check quadratic constraint conv = value(JuMP.variable_by_name(mod, "capaConv[none,_2040,_FR,_onshore]")) stIn = value(JuMP.variable_by_name(mod, "capaStIn[2040,_2040,_FR,_lithiumBattery,_1]")) stSize = value(JuMP.variable_by_name(mod, "capaStSize[2040,_2040,_FR,_lithiumBattery,_1]")) # quadratic constraint in .mps file # capaConv[none,_2040,_FR,_onshore]² + capaStSize[2040,_2040,_FR,_lithiumBattery,_1]² + capaStIn[2040,_2040,_FR,_lithiumBattery,_1]² - 988.64513652647 capaConv[none,_2040,_FR,_onshore] - 1494.108967790764 capaStSize[2040,_2040,_FR,_lithiumBattery,_1] - 298.823417245908 capaStIn[2040,_2040,_FR,_lithiumBattery,_1] <= - 824769.0620761865 # check constraint from results (lhs is -386520.97356201836) lhs = conv^2 + stSize^2 + stIn^2 - 988.64513652647 * conv - 1494.108967790764 * stSize - 298.823417245908 * stIn println(lhs <= -824769.0620761865)
0 -
Please sign in to leave a comment.
Comments
3 comments