Archive

Posts Tagged ‘bug’

Bug on Gurobi Optimization

July 16th, 2009 linfati.cl No comments

Today gurobi give me the confirmation of the bug ( and the fix is on the next release 1.1.2 )

Gurobi is a solver for LP and MIP and can be user from C, C++, Java, Python and they are Premiun Partner of Microsoft Solver Foundation. The Management Team are 3 ex-employees from (Ilog) Cplex. The Price of comercial license is from USD$ 6.500 (single user, single machine, single instance) to USD $36.000 (unlimited user, single machine, multi cpu) + 20% per year for maintenance.

The Problem:
Gurobi give me a incorrect, not optimal, not valid, not feasible solution as optimal

The model in format lp

Minimize
  x
Subject To
 c0: 75000 x - 75001 y - 75002 z = 0
Bounds
 1 <= x
Generals
 x y z
End

Or

\min \quad x
Subject To
7500 * x = 75001 * y + 75002 * z
x \geq 1, y \geq 0, z \geq 0
x,y,z \in \mathbb{Z}^{+}_{0}

The Output of gurobi is

Python 2.5.2 (r252:60911, Jul 31 2008, 17:28:52)
[GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2
Type "help", "copyright", "credits" or "license" for more information.

Gurobi Interactive Shell, Version 1.1.1
Copyright (c) 2009, Gurobi Optimization, Inc.
Type "help()" for help

gurobi> f1 = read('/datos/Universidad/PhD-Unibo/ilofail/fail1.lp' )
Read LP format model from file /datos/Universidad/PhD-Unibo/ilofail/fail1.lp
(null): 1 Rows, 3 Columns, 3 NonZeroes
gurobi> f1.optimize()
Optimize a model with 1 Rows, 3 Columns and 3 NonZeroes
Presolve time: 0.00s
Presolved: 1 Rows, 3 Columns, 3 Nonzeros
Objective GCD is 1

Root relaxation: objective 1.000000e+00, 0 iterations, 0.00 seconds

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

H    0     1                          2.0000     1.0000  50.0%     -    0s
     0     1     1.0000    0    1     2.0000     1.0000  50.0%     -    0s

Explored 1364 nodes (1363 simplex iterations) in 0.28 seconds
Thread count was 2 (of 2 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 2.0000000000e+00, best bound 2.0000000000e+00, gap 0.0000%

And… is easy check that for x=2 \quad \nexists \quad y,z \in \mathbb{Z}^{+}_{0} that satisface 7500 * x = 75001 * y + 75002 * z

The optimal solution is x = 37501 , y = 0, z = 37500

Thanks to
Edward Rothberg – Gurobi
For confirm the bug (and fix it in the next release)
Juan José Salazar – Universidad of La Laguna, Tenerife, Spain
For show an example of very very small mathematical model, but very hard to solve in cplex or another solver. See the slide

Categories: linfati.cl Tags: , , ,