MIP start causes gurobi to fail

[Miles Lubin]

When I run the following Julia code:

using Gurobi

m = Gurobi.Model(Gurobi.Env(),"model")
Gurobi.read_model(m, "instance.mps")
Gurobi.set_dblattrarray!(m, "Start", 1, Gurobi.num_vars(m), [1.0e101,1.0e101,1.0e101,1.0e101,1.0e101,0.5,1.36922e-9])
Gurobi.optimize(m)

Gurobi 7.0.2 fails to solve the instance and reports:

Read MPS format model from file instance.mps

Reading time = 0.00 seconds

: 40 rows, 7 columns, 84 nonzeros

Optimize a model with 40 rows, 7 columns and 84 nonzeros

Variable types: 6 continuous, 1 integer (0 binary)

Coefficient statistics:

  Matrix range     [1e-04, 2e+01]

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

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

  RHS range        [1e-04, 3e+01]

Presolve removed 14 rows and 2 columns

Presolve time: 0.00s

Presolved: 26 rows, 5 columns, 62 nonzeros

Loaded MIP start with objective -18.0013

Variable types: 4 continuous, 1 integer (0 binary)

Presolve removed 5 rows and 31 columns

Presolve: All rows and columns removed

Extra 3 simplex iterations after uncrush

Root relaxation: unbounded, 3 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work

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

     0     0  postponed    0       -18.00128          -      -     -    0s

Explored 0 nodes (3 simplex iterations) in 0.00 seconds

Thread count was 2 (of 2 available processors)

Solution count 1: -18.0013 

Model is infeasible or unbounded

Best objective -1.800127892554e+01, best bound -, gap -

When I comment out the line calling set_dblattrarray!, then Gurobi is able to solve the instance and reports:

Read MPS format model from file instance.mps

Reading time = 0.00 seconds

: 40 rows, 7 columns, 84 nonzeros

Optimize a model with 40 rows, 7 columns and 84 nonzeros

Variable types: 6 continuous, 1 integer (0 binary)

Coefficient statistics:

  Matrix range     [1e-04, 2e+01]

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

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

  RHS range        [1e-04, 3e+01]

Presolve removed 14 rows and 2 columns

Presolve time: 0.00s

Presolved: 26 rows, 5 columns, 62 nonzeros

Variable types: 4 continuous, 1 integer (0 binary)

Presolved: 5 rows, 31 columns, 67 nonzeros

Presolve removed 5 rows and 31 columns

Root relaxation: objective -1.808424e+01, 10 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work

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

     0     0  -18.08424    0    1          -  -18.08424      -     -    0s

H    0     0                      -4.4060058  -18.08424   310%     -    0s

H    0     0                     -15.1382952  -18.08424  19.5%     -    0s

     0     0  -18.06591    0    1  -15.13830  -18.06591  19.3%     -    0s

     0     0  -18.03859    0    1  -15.13830  -18.03859  19.2%     -    0s

H    0     0                     -18.0012788  -18.03859  0.21%     -    0s

*    0     0               0     -18.0012788  -18.00128  0.00%     -    0s

Cutting planes:

  Gomory: 1

  MIR: 1

Explored 1 nodes (16 simplex iterations) in 0.00 seconds

Thread count was 2 (of 2 available processors)

Solution count 4: -18.0013 -18.0013 -15.1383 -4.40601 

Pool objective bound -18.0013

Optimal solution found (tolerance 1.00e-04)

Best objective -1.800127879528e+01, best bound -1.800127879528e+01, gap 0.0000%

What could be happening here?

[Oscar Dowson]

Miles,

This is likely due to the large coefficients (1e101).

Also addressed in https://groups.google.com/forum/#!topic/gurobi/M_Bzc6RWMhU and https://github.com/JuliaOpt/Gurobi.jl/issues/94

A more interesting example is

using Gurobi

m = Gurobi.Model(Gurobi.Env(),"model")
Gurobi.read_model(m, "instance.mps")


Gurobi.optimize(m)

# get solution and use as MIP start
Gurobi.set_dblattrarray!(m, "Start", 1, Gurobi.num_vars(m), Gurobi.get_dblattrarray(m, "X", 1, Gurobi.num_vars(m)))

Gurobi.optimize(m)


The last solve has a log of

Optimize a model with 40 rows, 7 columns and 84 nonzeros
Variable types: 6 continuous, 1 integer (0 binary)
Coefficient statistics:
  Matrix range     [1e-04, 2e+01]
  Objective range  [1e+00, 1e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e-04, 3e+01]
Presolve removed 14 rows and 2 columns
Presolve time: 0.00s
Presolved: 26 rows, 5 columns, 62 nonzeros

Loaded MIP start with objective -18.0013

Variable types: 4 continuous, 1 integer (0 binary)
Presolve removed 5 rows and 31 columns
Presolve: All rows and columns removed
Extra 3 simplex iterations after uncrush

Root relaxation: unbounded, 3 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0  postponed    0       -18.00128          -      -     -    0s

Explored 0 nodes (3 simplex iterations) in 0.01 seconds
Thread count was 8 (of 8 available processors)

Solution count 1: -18.0013

Model is infeasible or unbounded

Best objective -1.800127880161e+01, best bound -, gap -

Cheers,
Oscar

[Zonghao Gu]

Thanks for reporting the issue. With mip start solution, Gurobi is able to strengthen the variable bounds, then the root relaxation is slightly infeasible. The model has more constraints than variables, so it solves the dual formulation and concludes it is unbounded. The bug is that it doesn't change it to infeasible for the primal formulation. The fix will be in the future Gurobi release.

--

---
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+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Oscar Dowson]

It is a result of the presolve removing all rows and columns.

Here is an example in Python

from gurobipy import *

m = read("instance.mps")

# comment out to make fail
m.setParam("presolve", 0)

vars = m.getVars()
mipstart=[1.0e101,1.0e101,1.0e101,1.0e101,1.0e101,0.5,1.36922e-9]
for i in range(len(vars)):
    vars[i].start = mipstart[i]

m.optimize()

sol = m.getAttr("X")
for i in range(len(vars)):
    vars[i].start = sol[i]

m.optimize()

The first call to optimize with presolve

Optimize a model with 40 rows, 7 columns and 84 nonzeros
Variable types: 6 continuous, 1 integer (0 binary)
Coefficient statistics:
  Matrix range     [1e-04, 2e+01]
  Objective range  [1e+00, 1e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e-04, 3e+01]
Presolve removed 14 rows and 2 columns
Presolve time: 0.00s
Presolved: 26 rows, 5 columns, 62 nonzeros

Loaded MIP start with objective -18.0013

Variable types: 4 continuous, 1 integer (0 binary)
Presolve removed 5 rows and 31 columns
Presolve: All rows and columns removed
Extra 3 simplex iterations after uncrush

Root relaxation: unbounded, 3 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0  postponed    0       -18.00128          -      -     -    0s

Explored 0 nodes (3 simplex iterations) in 0.03 seconds
Thread count was 8 (of 8 available processors)

Solution count 1: -18.0013

Model is infeasible or unbounded
Best objective -1.800127892554e+01, best bound -, gap -

With presolve off

Changed value of parameter Presolve to 0
   Prev: -1  Min: -1  Max: 2  Default: -1

Optimize a model with 40 rows, 7 columns and 84 nonzeros
Variable types: 6 continuous, 1 integer (0 binary)
Coefficient statistics:
  Matrix range     [1e-04, 2e+01]
  Objective range  [1e+00, 1e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e-04, 3e+01]

Loaded MIP start with objective -18.0013

Variable types: 6 continuous, 1 integer (0 binary)

Root relaxation: objective -1.808424e+01, 16 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work

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

     0     0  -18.08424    0    1  -18.00128  -18.08424  0.46%     -    0s
     0     1  -18.08424    0    1  -18.00128  -18.08424  0.46%     -    0s

Explored 2 nodes (23 simplex iterations) in 0.02 seconds
Thread count was 8 (of 8 available processors)

Solution count 1: -18.0013

Pool objective bound -18.0013

Optimal solution found (tolerance 1.00e-04)

Best objective -1.800127891887e+01, best bound -1.800127891887e+01, gap 0.0000%

Oscar

On Sunday, 26 March 2017 02:14:28 UTC+13, Miles Lubin wrote:

[Miles Lubin]

Thanks, Gu. Do you mean that when the issue you mentioned is fixed, the instance will report infeasible when given the MIP start and optimal when not?

Best,

Miles

To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.

[Zonghao Gu]

Only Root relaxation becomes infeasible, the final MIP status is the same (optimal) and the solution (which is from the start) will have the same objective as that without mip start.

To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+unsubscribe@googlegroups.com.

[Zonghao Gu]

Note that after an optimal solution is found, reduced cost fixing and some reductions could make MIP infeasible and so the root relaxation.

[Miles Lubin]

Thanks for the clarification, Gu!

Oscar, the value 1e101 is the special value GRB_UNDEFINED. I don't think this is related to the issue you mentioned.