A MIPstart for unconstrained quadratic integer program  Rejected, but no feasible solution found
Awaiting user inputI 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 highquality 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 multiobjectives
OBJ0: Priority=1 Weight=1 AbsTol=1e06 RelTol=0
0 x[4] + p
OBJ1: Priority=0 Weight=1 AbsTol=1e06 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

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
Please sign in to leave a comment.
Comments
1 comment