Gurobi 9.1 Performance Improvement and New Features.

Some really good performance improvements. Striking are the numbers for non-convex MIQCP models. 

Performance Improvements

With Gurobi 9.1, the Gurobi Optimizer registered notable performance improvements across multiple problem types including:

• Primal simplex: 17% faster overall, 37% faster on models that take at least 100 seconds.
• Dual simplex: 29% faster overall, 66% faster on models that take at least 100 seconds.
• Barrier: 15% faster overall, 34% faster on models that take at least 100 seconds.
• Mixed-integer linear programming (MILP): 5% faster overall, 9% faster on models that take at least 100 seconds.
• Convex mixed-integer quadratic programming (MIQP): 5% faster overall, 20% faster on models that take at least 100 seconds.
• Convex mixed-integer quadratically constrained programming (MIQCP): 13% faster overall, 57% faster on models that take at least 100 seconds.
• Non-convex mixed-integer quadratically constrained programming (non-convex MIQCP): 4x faster overall, 9x faster on models that take at least 100 seconds.
• Irreducible Infeasible Subset (IIS) computation: 2.6x faster overall, 5.7x faster on models that take at least 100 seconds.
• Better MIP feasible solutions: Heuristics are significantly better at finding high-quality solutions earlier.

New Features

The new features in the release include:

• NoRel Heuristic: This new heuristic finds high-quality solutions in situations where the linear programming (LP) relaxation of the mixed-integer programming (MIP) problem is too expensive to solve.
• Integrality Focus: This new feature allows users to be much stricter on integrality constraints, thus avoiding many undesirable results (including trickle flows) that can come from small integrality violations.
• Python Matrix API Enhancements: Gurobi’s Python interface – gurobipy – has been extended and improved to better support matrix-oriented modeling.
• Pip Install Support: Users can now utilize pip, a Python tool, to install Gurobi in their Python environment.

 

Gurobi v9.0.

Now including elevator music!


 Major new features:

• Non-convex quadratic solver
• Supports non-convexities both in objective and constraints
• Not quite sure if MIQCP is supported (I assume it is, but I think this was not mentioned explicitly)
• Cplex had already support for (some) non-convex quadratic models, so Gurobi is catching up here.
• Performance improvements
• MIP: 18% faster overall and 26% on difficult models (more than 100 seconds)
• MIQP: 24% faster
(these numbers are from the email I received -- not from the movie). Quite impressive numbers. Performance does not seem to plateau (yet). Of course we see this also for Cplex: it keeps improving. There is some healthy competition here.

References

1. What's New (for Gurobi), https://www.gurobi.com/products/gurobi-optimizer/whats-new-current-release/
2. 2019-11 - INFORMS Seattle - Whats new in CPLEX 12.10, https://ibm.ent.box.com/s/81yeflq972r6gmhckobl403pwwpuih4a

Gurobi Standalone version available

The Gurobi standalone solver is now available. More information is available on the website www.gurobi.com. There is reference material online to peruse. I have some experience with using Gurobi, and although I have not done any formal benchmarks, on my models it has shown to be very competitive with the other leading LP/MIP solvers and remarkably stable. Gurobi seems especially attractive when you have a machine with many cores/cpu’s available (and soon we all have cell-phones with 16 cores).

Interestingly the shell is based on Python. I am probably one of the very few ones who remember ABC, a small language developed at the CWI that was in many respects the origin of Python.

TSP in OML (MS Solver Foundation)

In theory it is easy to formulate a TSP when the all-different constraint is present. Let x[i] be the i^th city visited, an OML-like formulation could look like:

Model[

  Parameters[Integers,N=14],

  Parameters[Sets[Integers],city],

  Parameters[Reals,dist[city,city]],

  Decisions[Integers[0,N-1],x[city]],

  Constraints[

     Unequal[Foreach[{i,city},x[i]]]

  ],

  Goals[

    Minimize[Sum[{i,city},dist[x[i],x[i++1]]]]

  ]

]

This does not work completely. First, bounds can not contain a symbolic constant. Yuck: we need to write [0,13] as bounds:  Decisions[Integers[0,13],x[city]]. The objective has  a few more difficulties. There is no circular lead/lag operator in OML (like the -- or ++ operator in GAMS).  This can be solved by introducing a parameter next[city]. This can be calculated in Excel and imported in the OML model. Furthermore, we cannot use a variable as an index, so dist[x[i],x[next[i]]] is not a valid construct (some languages geared towards solving CSP problems allow this; it adds concise expressiveness to the language that may help the modeler). The error message indicates this is not related to OML per se but rather to solver support. Also it is not allowed to use something like FilteredSum[{j,city},j==x[i],...] (a condition in a FilteredSum cannot depend on a decision variable). The only thing I could think of was:

Minimize[Sum[{i,city},{j,city},{k,city},AsInt[j==x[i]]*AsInt[k==x[next[i]]]*dist[j,k]]]

Note that I used integers as set elements. I started with using data-binding through tables, using set elements {'city0','city1',...,'city13'}. This made the model somewhat more complicated, as x[i] is an integer. So the CSP formulation uses the simpler set {0,1,...,13} allowing us to operate on indices. (Some consider this bad modeling: in GAMS arithmetic on sets is actually discouraged, and needs a function ord()to convert the element — always a string in GAMS — to an integer). Unfortunately I was not able to solve the small 14 city example with the CSP solver using this formulation. (Even after adding City[0]==0 as constraint). To check the input, I also tried a MIP formulation with Gurobi. That solved this small instance just fine.

In the MIP formulation we needed to formulate:

FilteredSum[{i,city},i != 'city0', x['city0',i]]==1

From what I can see this is not possible: a set element not being an integer can not be used in OML. As a workaround I created sets by binding to some dummy parameters:

Sum[{i0,city0},{i,city2},x[i0,i]]==1

where city0 is a set containing only a single element 'city0', and city2 is a set {'city1',...,'city13'}.  The constraint

FilteredSum[{i,city},{j,city},i != j,x[i,j]] <= N

did not work as i and j are not numeric. A workaround could be to have a parameter num[city] which can be calculated in Excel and then imported. Then the condition can read: num[i]!=num[j]. I just used dist[i,j]>0 as condition, as that also can be used to exclude the diagonal (the Excel spreadsheet makes sure all diagonal distances dist[i,i] are zero). A more general approach would be to be able to introduce sparse 2-d sets (like one could do in AMPL and GAMS), but OML has only one dimensional sets as far as I know.

This exercise was really meant to explore the expressiveness of OML. The little model actually shows some interesting issues with OML and some possible workarounds. I do not want to suggest this is a good way to solve TSP's. Obviously these approaches are not suited for large problems. A cutting plane algorithm often is quite effective for slightly larger problems (see this 42 city problem). The excel plugin does not allow us to to implement such an algorithm: an OML model can only contain a single model and has no looping facilities. For the real large problems, you need to look elsewhere, such as Concorde.

MS Solver Foundation /Gurobi (2)

The MIP capabilities of the standard editions have been significantly reduced. In the previous version this was 2k variables and equations and now only 500 variables and equations. This is looks like a Gurobi limit:

Error:
The solver(s) threw an exception while solving the model - Gurobi throttle exceeded.
Visit www.gurobi.com/html/products.html to purchase an unlock license (HostID: 8AA3C6D2).


The obj seems to be counted as an equation:

Model[

  // generate simple MIP model with 500 variables and 500 constraints
  Parameters[Integers,N=500],
  Decisions[Integers[0,1],Foreach[{i,N},x[i]]],
    
 Constraints[ Foreach[{i,N},x[i] <= 1]  ],
 
  Goals[
    Maximize[Sum[{i,N},x[i]]]
    //Maximize[obj->Sum[{i,N},x[i]]] use to prevent funny name for goal
  ]

]

does trigger the above message. From the Excel plug-in I don't see an option to use the MS MIP solver. I hope I am wrong, but I suspect there is a class of MIP models that could be solved with the previous version of the Standard Edition that can no longer be solved with the current 1.1 release.

The workaround seems obvious: purchase the enterprise edition or purchase Gurobi.

Note that the limit is on any variable, i.e. 1 integer variable + 500 continuous variables makes the model too large.


Update: If your problem is in between these limits this can help. There is a way to point the excel plugin back to the MS MIP solver through a configuration file. For more info please contact the MSF people at http://code.msdn.microsoft.com/solverfoundation. They are very helpful and responsive.

MS Solver Foundation / Gurobi

MS Solver Foundation 1.1 is out. It includes Gurobi! (it has even become the default MIP solver). See http://code.msdn.microsoft.com/solverfoundation.

Indeed we see when running a MIP from the Excel plugin:

Gurobi vs Cplex benchmarks

> What are your first impressions of Gurobi? How does it compare to CPLEX for MIP? Have you done any benchmark analysis?

Here are some benchmarks: http://plato.asu.edu/ftp/milpc.html

However I would always urge you to try out solvers on your particular models as they may behave very differently than the benchmark models. Drop me a note if you need me to run some models or need access to evaluation systems.

More solvers on the way

After Microsoft entering the Math Programming Software market, there also will be more solver competition at the high-end: http://www.gurobi.com/index.html. These guys were main developers of Cplex, so I would guess they aim towards a similarly positioned product. This is of course a very welcome development for us modelers.