MIP start not leading to a better feasible solution

[Harsha Veeramachaneni]

I have a MILP (will all binary variables) problem for which setting all variables to zero is feasible. I can produce a better feasible solution with some variables set to 1. When I set the MIP start to this setting of variables, I receive a "MIP start did not produce a new incumbent solution" and the all-zero solution is returned.

However when I fix the variables to the starting values with addConstr, the solution that is found is better. That is, when I constrain the variables to equal the MIP start I find a better solution (with a lower objective value) than when I initialize with the MIP start. This is odd because, I would expect that, if the MIP start that I provided is feasible and has a better objective value than the all-zero assignment, Gurobi should at least return my MIP start as the most optimal solution found.

What could I be doing wrong?

[Michael Winkler]

Could you please provide your model, your MIP start and also the fixed model (where you added the fixings via constraints). Thank you!

Best, Michel

P.S. What is your Gurobi version?

[Harsha Veeramachaneni]

gurobi_cl --version

Gurobi Optimizer version 7.0.2 build v7.0.2rc1 (mac64)

Copyright (c) 2017, Gurobi Optimization, Inc.

My MIP model is rather large and I am using the python API to set it up. Is there a way I can put it into a format to send to you.

[Michael Winkler]

In python you can use model.write('yourmodel.mps') to write out your model. If you have bzip2 or 7zip installed you could use model.write('yourmodel.mps.bz2') or model.write('yourmodel.mps.7z') accordingly to write it in compressed format. If it's still too large let me know.

Best, Michael

[Harsha Veeramachaneni]

The behavior of the model leads me to think that Gurobi thinks that the MIP start is infeasible. I think this because when I run the following commands after I setup the model and MIP start

model.update()
obj = model.getObjective()
print("Init objective = %f"%obj.getValue())

I get the following error.

  File "linexpr.pxi", line 325, in gurobipy.LinExpr.getValue (../../src/python/gurobipy.c:30901)
  File "var.pxi", line 76, in gurobipy.Var.__getattr__ (../../src/python/gurobipy.c:14162)
  File "var.pxi", line 142, in gurobipy.Var.getAttr (../../src/python/gurobipy.c:14973)
  gurobipy.GurobiError: Unable to retrieve attribute 'x'

[Harsha Veeramachaneni]

The model is too large to attach to the post, apparently. Can I email them to you?

[Michael Winkler]

I got your models, do you have a MIP start file (mst file) for us as well? The mst file has per line of pair of a variable name and its value (separated by some space), see https://www.gurobi.com/documentation/7.0/refman/mst_format.html.

Note that you cannot ask for an objective value if the model does not have a solution. After starting the solving process an installed MIP start will be processed and accepted or declined. So you can only ask for an objective value if the model has an accepted solution.

Best, Michael

[Harsha Veeramachaneni]

Interesting. Since the objective is just a LinExpr I assumed that I can evaluate it for a given start value.

Is there an easy way to find out the objective value for a given MIP start and (if it is infeasible) all the violated constraints? The reason I am asking is that we would like to provide an intelligent MIP start to aid the solver, but as we code it up would like to see if we are unwittingly passing a start value that actually has a worse objective and perhaps violates some constraints.

[Harsha Veeramachaneni]

For some reason I cant post another file to this thread. The mst file is small, however. Here are its contents

# MIP start

x[J3,71] 1

x[J5,0] 1

x[J25,55] 1

x[J32,79] 1

x[J65,39] 1

x[J67,10] 1

x[J82,44] 1

x[J90,24] 1

x[J94,88] 1

y[J3,79] 1

y[J5,10] 1

y[J25,71] 1

y[J32,88] 1

y[J65,44] 1

y[J67,24] 1

y[J82,55] 1

y[J90,39] 1

A[J3,R1,71] 1

A[J3,R1,72] 1

A[J3,R1,73] 1

A[J3,R1,74] 1

A[J3,R1,75] 1

A[J3,R1,76] 1

A[J3,R1,77] 1

A[J3,R1,78] 1

A[J5,R1,0] 1

A[J5,R1,1] 1

A[J5,R1,2] 1

A[J5,R1,3] 1

A[J5,R1,4] 1

A[J5,R1,5] 1

A[J5,R1,6] 1

A[J5,R1,7] 1

A[J5,R1,8] 1

A[J5,R1,9] 1

A[J5,R2,0] 1

A[J5,R2,1] 1

A[J5,R2,2] 1

A[J5,R2,3] 1

A[J5,R2,4] 1

A[J5,R2,5] 1

A[J5,R2,6] 1

A[J5,R2,7] 1

A[J5,R2,8] 1

A[J5,R2,9] 1

A[J25,R1,55] 1

A[J25,R1,56] 1

A[J25,R1,57] 1

A[J25,R1,58] 1

A[J25,R1,59] 1

A[J25,R1,60] 1

A[J25,R1,61] 1

A[J25,R1,62] 1

A[J25,R1,63] 1

A[J25,R1,64] 1

A[J25,R1,65] 1

A[J25,R1,66] 1

A[J25,R1,67] 1

A[J25,R1,68] 1

A[J25,R1,69] 1

A[J25,R1,70] 1

A[J25,R2,55] 1

A[J25,R2,56] 1

A[J25,R2,57] 1

A[J25,R2,58] 1

A[J25,R2,59] 1

A[J25,R2,60] 1

A[J25,R2,61] 1

A[J25,R2,62] 1

A[J25,R2,63] 1

A[J25,R2,64] 1

A[J25,R2,65] 1

A[J25,R2,66] 1

A[J25,R2,67] 1

A[J25,R2,68] 1

A[J25,R2,69] 1

A[J25,R2,70] 1

A[J32,R1,79] 1

A[J32,R1,80] 1

A[J32,R1,81] 1

A[J32,R1,82] 1

A[J32,R1,83] 1

A[J32,R1,84] 1

A[J32,R1,85] 1

A[J32,R1,86] 1

A[J32,R1,87] 1

A[J65,R1,39] 1

A[J65,R1,40] 1

A[J65,R1,41] 1

A[J65,R1,42] 1

A[J65,R1,43] 1

A[J65,R2,39] 1

A[J65,R2,40] 1

A[J65,R2,41] 1

A[J65,R2,42] 1

A[J65,R2,43] 1

A[J65,R3,39] 1

A[J65,R3,40] 1

A[J65,R3,41] 1

A[J65,R3,42] 1

A[J65,R3,43] 1

A[J67,R1,10] 1

A[J67,R1,11] 1

A[J67,R1,12] 1

A[J67,R1,13] 1

A[J67,R1,14] 1

A[J67,R1,15] 1

A[J67,R1,16] 1

A[J67,R1,17] 1

A[J67,R1,18] 1

A[J67,R1,19] 1

A[J67,R1,20] 1

A[J67,R1,21] 1

A[J67,R1,22] 1

A[J67,R1,23] 1

A[J67,R2,10] 1

A[J67,R2,11] 1

A[J67,R2,12] 1

A[J67,R2,13] 1

A[J67,R2,14] 1

A[J67,R2,15] 1

A[J67,R2,16] 1

A[J67,R2,17] 1

A[J67,R2,18] 1

A[J67,R2,19] 1

A[J67,R2,20] 1

A[J67,R2,21] 1

A[J67,R2,22] 1

A[J67,R2,23] 1

A[J67,R3,10] 1

A[J67,R3,11] 1

A[J67,R3,12] 1

A[J67,R3,13] 1

A[J67,R3,14] 1

A[J67,R3,15] 1

A[J67,R3,16] 1

A[J67,R3,17] 1

A[J67,R3,18] 1

A[J67,R3,19] 1

A[J67,R3,20] 1

A[J67,R3,21] 1

A[J67,R3,22] 1

A[J67,R3,23] 1

A[J82,R1,44] 1

A[J82,R1,45] 1

A[J82,R1,46] 1

A[J82,R1,47] 1

A[J82,R1,48] 1

A[J82,R1,49] 1

A[J82,R1,50] 1

A[J82,R1,51] 1

A[J82,R1,52] 1

A[J82,R1,53] 1

A[J82,R1,54] 1

A[J82,R2,44] 1

A[J82,R2,45] 1

A[J82,R2,46] 1

A[J82,R2,47] 1

A[J82,R2,48] 1

A[J82,R2,49] 1

A[J82,R2,50] 1

A[J82,R2,51] 1

A[J82,R2,52] 1

A[J82,R2,53] 1

A[J82,R2,54] 1

A[J82,R3,44] 1

A[J82,R3,45] 1

A[J82,R3,46] 1

A[J82,R3,47] 1

A[J82,R3,48] 1

A[J82,R3,49] 1

A[J82,R3,50] 1

A[J82,R3,51] 1

A[J82,R3,52] 1

A[J82,R3,53] 1

A[J82,R3,54] 1

A[J90,R1,24] 1

A[J90,R1,25] 1

A[J90,R1,26] 1

A[J90,R1,27] 1

A[J90,R1,28] 1

A[J90,R1,29] 1

A[J90,R1,30] 1

A[J90,R1,31] 1

A[J90,R1,32] 1

A[J90,R1,33] 1

A[J90,R1,34] 1

A[J90,R1,35] 1

A[J90,R1,36] 1

A[J90,R1,37] 1

A[J90,R1,38] 1

A[J90,R2,24] 1

A[J90,R2,25] 1

A[J90,R2,26] 1

A[J90,R2,27] 1

A[J90,R2,28] 1

A[J90,R2,29] 1

A[J90,R2,30] 1

A[J90,R2,31] 1

A[J90,R2,32] 1

A[J90,R2,33] 1

A[J90,R2,34] 1

A[J90,R2,35] 1

A[J90,R2,36] 1

A[J90,R2,37] 1

A[J90,R2,38] 1

A[J94,R1,88] 1

A[J94,R1,89] 1

A[J94,R1,90] 1

A[J94,R1,91] 1

A[J94,R1,92] 1

A[J94,R1,93] 1

A[J94,R1,94] 1

A[J94,R1,95] 1

A[J94,R1,96] 1

A[J94,R1,97] 1

A[J94,R1,98] 1

A[J94,R1,99] 1

[Michael Winkler]

I tried solving the original instance and without a MIP start and at the root node, we find a feasible solution better than the zero solution. Here a part of my log:

     0     0 -18226.391    0 11791    0.00000 -18226.391      -     -  252s
H    0     0                    -3447.742970 -18226.391   429%     -  253s
 
Since you use only a partial MIP start, i.e., you do not assign a value to each of the binary(also integer) variables, Gurobi tries to "repair" your MIP start. Could it be that you interrupted the solving process where you installed the partial MIP start before a better (than the initial 0) solution was found? Do you have a log file of your run of the original model?

Again, you cannot evaluate the LinExpr because the partial MIP start is not yet applied and Gurobi does not have any feasible solution at hand. Also, currently it is not possible to get a list of all violated constraints for a given solution vector.

Note that since your MIP start is only a partial one, it might not be advantageous to add it. Instead if you have an idea what values certain variables will take in a good solution you can use variable hints, see https://www.gurobi.com/documentation/7.0/refman/varhintval.html.

Best, Michael

[Harsha Veeramachaneni]

Here is the log from the original model optimize call (without MIP start)

Changed value of parameter TimeLimit to 60.0

   Prev: 1e+100  Min: 0.0  Max: 1e+100  Default: 1e+100

Optimize a model with 51200 rows, 140000 columns and 1310000 nonzeros

Variable types: 0 continuous, 140000 integer (140000 binary)

Coefficient statistics:

  Matrix range     [1e+00, 2e+01]

  Objective range  [4e-03, 4e+01]

  Bounds range     [1e+00, 1e+00]

  RHS range        [1e+00, 2e+01]

Found heuristic solution: objective 0

Presolve removed 21277 rows and 3553 columns

Presolve time: 4.66s

Presolved: 29923 rows, 136447 columns, 470272 nonzeros

Variable types: 0 continuous, 136447 integer (136447 binary)

Root simplex log...

Iteration    Objective       Primal Inf.    Dual Inf.      Time

    7758   -2.5274950e+04   1.861331e+03   0.000000e+00      5s

   33427   -2.3782076e+04   2.038838e+03   0.000000e+00     10s

   39606   -2.3603225e+04   5.474040e+04   0.000000e+00     15s

   47459   -2.3434226e+04   2.811597e+04   0.000000e+00     20s

   53175   -2.3299348e+04   2.967102e+05   0.000000e+00     25s

   57478   -2.3178970e+04   4.066750e+04   0.000000e+00     30s

   61295   -2.3053191e+04   2.582856e+04   0.000000e+00     35s

   65358   -2.2966947e+04   5.153903e+04   0.000000e+00     40s

   69901   -2.2851799e+04   3.610020e+04   0.000000e+00     45s

Warning: Markowitz tolerance tightened to 0.03125

   73861   -2.2777284e+04   5.864664e+04   0.000000e+00     50s

   77921   -2.2677938e+04   1.019270e+05   0.000000e+00     55s

Root relaxation: time limit, 81684 iterations, 55.24 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work

 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0          -    0         0.00000          -      -     -   60s

Explored 0 nodes (81684 simplex iterations) in 60.17 seconds

Thread count was 8 (of 8 available processors)

Solution count 1: 0 

Time limit reached

Best objective 0.000000000000e+00, best bound -, gap -

And here is the log when I optimize with the MIP start

Changed value of parameter TimeLimit to 60.0

   Prev: 1e+100  Min: 0.0  Max: 1e+100  Default: 1e+100

Optimize a model with 51200 rows, 140000 columns and 1310000 nonzeros

Variable types: 0 continuous, 140000 integer (140000 binary)

Coefficient statistics:

  Matrix range     [1e+00, 2e+01]

  Objective range  [4e-03, 4e+01]

  Bounds range     [1e+00, 1e+00]

  RHS range        [1e+00, 2e+01]

Found heuristic solution: objective 0

Presolve removed 21277 rows and 3553 columns

Presolve time: 4.73s

Presolved: 29923 rows, 136447 columns, 470272 nonzeros

MIP start did not produce a new incumbent solution

Variable types: 0 continuous, 136447 integer (136447 binary)

Explored 0 nodes (0 simplex iterations) in 60.09 seconds

Thread count was 8 (of 8 available processors)

Solution count 1: 0 

Pool objective bound -26846.9

Time limit reached

Best objective 0.000000000000e+00, best bound -2.684692534112e+04, gap -

And the log with MIP start and constraints

Changed value of parameter TimeLimit to 60.0

   Prev: 1e+100  Min: 0.0  Max: 1e+100  Default: 1e+100

Optimize a model with 51418 rows, 140000 columns and 1310218 nonzeros

Variable types: 0 continuous, 140000 integer (140000 binary)

Coefficient statistics:

  Matrix range     [1e+00, 2e+01]

  Objective range  [4e-03, 4e+01]

  Bounds range     [1e+00, 1e+00]

  RHS range        [1e+00, 2e+01]

Found heuristic solution: objective -901.656

Presolve removed 24298 rows and 34122 columns

Presolve time: 4.24s

Presolved: 27120 rows, 105878 columns, 391380 nonzeros

MIP start did not produce a new incumbent solution

Variable types: 0 continuous, 105878 integer (105878 binary)

Explored 0 nodes (0 simplex iterations) in 60.08 seconds

Thread count was 8 (of 8 available processors)

Solution count 1: -901.656 

Pool objective bound -24247

Time limit reached

Best objective -9.016560209196e+02, best bound -2.424704068669e+04, gap 2589.1675%

I also tried 

self.model.setParam("SubMIPNodes", 10000.0)

but that didn't help in finding a non-zero solution either.

[Michael Winkler]

Since you set a time limit the solving process is interrupted. In the first heuristic that produces the 0 solution your partial MIP start is not used to try to find a solution. In your fixed model on the other hand the first heuristic is capable of finding a better solution.

Also I ran you original model with the partial MIP start with a time limit, than it takes a lot of time to try to generate a solution but fails. As I wrote earlier I would suggest that you provide a full start vector if possible or use the variable hints for some variables if you know what values they will take in good solutions.

Best, Michael

P.S. Setting SubMIPNodes to 10000 does not change anything for you because you are still solving the hard root LP relaxation in your time limit. What seems to works good is to use METHOD=2 which uses the barrier solver instead of simplex for your root relaxation. (This gives me a solution with value -3447.742970 in 10s on my machine on your original model.) Still you should consider a (much) bigger time limit.

[Harsha Veeramachaneni]

Thanks for your help! I will try providing a full solution as the MIP start. Is there a simple way to set all values to zero, without having set them to zero separately? Also which function allows me to change the LP solver to the barrier method.

[Michael Winkler]

There is currently no possibility to set the start attribute for a bunch of variables to zero (or any other value). Maybe it helps if you first loop over all variables and set the start to zero and then afterwards set all non-zero start values for a subset of your variables.
To make Gurobi use the Barrier solver at the root, you need to set the parameter Method=2, e.g., model.Params.method = 2 (in python if your model is named "model", see also https://www.gurobi.com/documentation/7.0/examples/change_parameters.html).

Best, Michael

[Wang Minke]

Dear Michael,

I have a heuristic which provides an initial solution vector. In order to check the solution is feasible in my model, I set start vector to the value of these solutions. How can I let Gurobi to just return an incumbent or the closely feasible solution repaired from my initial? Thanks! Longing for your reply!

Best,

Minke

[Silke Horn]

Hi Minke,

Maybe the SolutionLimit parameter is what you need. <https://www.gurobi.com/documentation/8.1/refman/solutionlimit.html>
E.g. if you set SolutionLimit = 1, Gurobi will stop once it has found the first feasible solution.

- Silke

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Tobias Achterberg]

Moreover, you may also want to set NodeLimit=0. This way, Gurobi would also stop
pretty soon if your MIP start did not lead to a feasible solution.

Best regards,

Tobias

[Wang Minke]

Thanks for your help!

[Wang Minke]

Thanks for your help!