A MIPstart for unconstrained quadratic integer program - Rejected, but no feasible solution found
Awaiting user input
I am minimising a convex quadratic function over the integer lattice. I also have a secondary linear objective in cases when the convex quadratic function has multiple minimisers over the integer lattice.
A good guess is to minimise the convex quadratic over R^n, (which is solving a system of linear equations) and then rounding off the solution. Typically, this provides a high-quality initial solution.
However, for a particular instance, and certain chosen values of parameters, my start solution is rejected by the solver with the message "User MIP start did not produce a new incumbent solution".
I am running hundreds of such instances, and typically setting Model.MIPFocus = 2 and Model.DualReductions=0 runs the fastest. So I use these parameters.
For this particular instance, in fact, if I set MIPFocus=1, my initial point is accepted and the problem is solved in about 5 seconds. When I set MIPFocus=2, my initial point is rejected and for over 10 minutes no feasible solution is found either.
Can I do something to always force accepting my initial point?
I am pasting the instance as an LP file below.
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize multi-objectives
OBJ0: Priority=1 Weight=1 AbsTol=1e-06 RelTol=0
0 x[4] + p
OBJ1: Priority=0 Weight=1 AbsTol=1e-06 RelTol=0
3 x[0] + x[1] - x[2] + 5 x[3] + x[5] - x[6] + 4 x[7] - 2 x[8] + 3 x[9]
Subject To
pCons: - 48 x[0] - 45 x[1] - 56 x[2] - 41 x[3] - 58 x[4] - 63 x[5]
- 79 x[6] - 62 x[7] - 52 x[8] - 40 x[9] + p + [ - 4 x[0] ^2
+ 3 x[0] * x[1] - 3 x[0] * x[2] + 2 x[0] * x[3] + 3 x[0] * x[4]
- x[0] * x[5] - x[0] * x[6] - x[0] * x[8] - 5 x[0] * x[9] - 4 x[1] ^2
- x[1] * x[2] - 3 x[1] * x[3] + x[1] * x[4] + 2 x[1] * x[5]
- x[1] * x[6] - x[1] * x[7] + 2 x[1] * x[8] + 2 x[1] * x[9] - 4 x[2] ^2
- x[2] * x[3] + 3 x[2] * x[4] - 2 x[2] * x[5] - 3 x[2] * x[6]
- 2 x[2] * x[7] + x[2] * x[8] - 6 x[2] * x[9] - 5 x[3] ^2
+ 2 x[3] * x[4] - x[3] * x[5] - 2 x[3] * x[6] - 2 x[3] * x[7]
+ 2 x[3] * x[8] - 2 x[3] * x[9] - 3 x[4] ^2 + x[4] * x[5] + x[4] * x[6]
+ x[4] * x[7] + x[4] * x[8] + 3 x[4] * x[9] - 4.5 x[5] ^2
- 2 x[5] * x[7] - 2 x[5] * x[9] - 3 x[6] ^2 - x[6] * x[8]
- 4 x[6] * x[9] - 4 x[7] ^2 + x[7] * x[8] - x[7] * x[9] - 3.5 x[8] ^2
- 4.5 x[9] ^2 ] >= 0
Bounds
x[0] free
x[1] free
x[2] free
x[3] free
x[4] free
x[5] free
x[6] free
x[7] free
x[8] free
x[9] free
p free
Generals
x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] x[9]
End
You can see the absence of constraints above, making every integer solution actually feasible.
The MST file with the MIPStart values are below.
# MIP start
x[0] -29
x[1] -18
x[2] -11
x[3] -14
x[4] -39
x[5] -9
x[6] -5
x[7] -5
x[8] -20
x[9] 10
My parameters are below:
MIPGap 0.01
MIPFocus 2
DualReductions 0
-
Official comment
-
Gurobi Staff
This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi Sriram,
What version of Gurobi are you using? I have not been able to reproduce your issue and see the MIP start accepted with both v10 and v11, using your parameters.
There are some tips regarding investigation by fixing variables in this article:
What does "User MIP start did not produce a new incumbent solution" mean?- Riley
0 -
Post is closed for comments.
Comments
2 comments