Warm start of non-convex optimization problem
AnsweredI am using Gurobi to solve a quadratic problem with bilinear equality constrains in MATLAB. I want to provide a feaible initial guess x0 for the non-convex optimization, but I couldn't find a way to do that. How can i input a warm start to Gurobi? I checked online document and can only find warm start for MIP and LP problems
-
-
Gurobi Staff
Hi Boli,
A non-convex QCP or a non-convex MIQCP are, both, solved as a MIP. Therefore, you can follow the same approaches as used for a MIP to set an initial solution. You can pass an initial solution either by using the Start variable attribute or by loading a MIP start (.mst) or a solution (.sol) file.
Best regards,
Maliheh
0 -
-
I put "model.start = x0;"
before
"result = gurobi(model, params);"
But it seems not working (slow and converged to the suboptimal), because x0 is feasible and pretty close to the optimal. By providing the same start point x0, the IPOPT can find the optimal very fast.
0 -
-
-
Hi Boli,
That is interesting.
Can you share the Gurobi log?Cheers,
David0 -
-
Gurobi 10.0.1 (win64, Matlab) logging started Fri Jul 21 00:28:52 2023
Set parameter OptimalityTol to value 1e-09
Set parameter LogFile to value "output.log"
Set parameter NonConvex to value 2
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 3 rows, 501 columns and 504 nonzeros
Model fingerprint: 0x31126b0f
Model has 125250 quadratic objective terms
Model has 499 quadratic constraints
Coefficient statistics:
Matrix range [1e+00, 1e+00]
QMatrix range [1e+00, 1e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [1e+04, 1e+04]
QObjective range [1e+04, 2e+04]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Presolve removed 1 rows and 0 columns
Continuous model is non-convex -- solving as a MIP
User MIP start did not produce a new incumbent solution
Presolve time: 0.02s
Presolved: 1999 rows, 501 columns, 4496 nonzeros
Presolved model has 125250 quadratic objective terms
Presolved model has 499 bilinear constraint(s)
Variable types: 501 continuous, 0 integer (0 binary)
Root relaxation: objective -5.016200e+03, 1051 iterations, 0.12 seconds (0.14 work units)
Another try with MIP start
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -5016.2003 0 468 - -5016.2003 - - 1s
H 0 0 -5015.774454 -5016.2003 0.01% - 2s
Explored 1 nodes (1051 simplex iterations) in 2.74 seconds (0.81 work units)
Thread count was 8 (of 8 available processors)
Solution count 1: -5015.77
Optimal solution found (tolerance 1.00e-04)
Best objective -5.015774454255e+03, best bound -5.016200344800e+03, gap 0.0085%0 -
-
-
In the log we have the messages below implying that Gurobi processes the start solution.
User MIP start did not produce a new incumbent solution
...
Another try with MIP startPlease see the documentation of the Start attribute for the reasons behind this message:
If the Gurobi MIP solver log indicates that your MIP start didn't produce a new incumbent solution, note that there can be multiple explanations. One possibility is that your MIP start is infeasible. Another, more common possibility is that one of the Gurobi heuristics found a solution that is as good as the solution produced by the MIP start, so the MIP start solution was cut off.
In your model, since there is no incumbent before the search tree exploration, the reason behind the messages is the infeasibility of the initial solution according to Gurobi.
I understand that you believe the initial solution is feasible. To check this, you can fix the initial solution on the model via setting the LB and UB of the variables to the values of the initial solution. You can then call the optimize method. We expect for Gurobi to result in infeasibility. You can then call the method computeIIS() to find an IIS and potentially gain some insight into why Gurobi concludes the initial solution is infeasible.
Best regards,
Maliheh
1 -
-
Yes, you are right, I made mistake, although the initial guess x0 is pretty close to the optimal, the initial guess x0 is NOT fesible.
By setting the FestibilityTol and OptimalityTol to 1e-9, the Gurobi now can find the optimal, but much slower than the IPOPT.
I am wondering, can Gurobi accept infesible starting point as a warm start?
0 -
-
-
No, Gurobi does not accept infeasible solutions as warm-start. You can, however, provide partial solutions where the Start attribute is not defined for some variables and the Gurobi Optimizer will then try to fill in the missing values by solving a sub-MIP.
If you know which variables make the solution \(x_0\) infeasible, you can set their start values to nan, which instructs the Gurobi Optimizer to try to fill in values for these variables.
Best regards,
Maliheh
0 -
Please sign in to leave a comment.
Comments
7 comments