GUROBI Features

From TomWiki

Jump to: navigation, search

Notice.png

This page is part of the GUROBI Manual. See GUROBI.

The active components in GUROBI are continuously expanding with additional support included with each release. As of the current version the solver suite included:

  • Primal simplex (LP)
  • Dual simplex (LP)
  • Mixed-integer linear programming (parallel) (MILP)

Contents

Linear Programming

The linear programming capabilities included with GUROBI can be summarized as follows:

  • Algorithms: Primal and Dual Simplex
  • Sensitivity analysis
  • Warm start with an advanced basis
  • Infeasibility analysis
  • Presolve modifications and analysis

Algorithms:

The default linear programming solver in GUROBI is the dual simplex algorithm. In general, the dual algorithm is suitable for most problems. However, it is recommended to try the primal simplex solver as well since it has proven beneficial for certain problem types.

grbControl.LPMETHOD = 0; % Primal simplex
grbControl.LPMETHOD = 1; % Dual simplex

Sensitivity analysis:

TOMLAB /GUROBI also implements sensitivity analysis (post-optimality analysis) for linear programming problems. This makes it possible to further analyze the solution returned from the algorithm. The solver will return information about how much the variable bounds, linear constraint bounds and objective coefficients can be adjusted while still maintaining the same optimal basis. The results will be a range and hence give detailed information about the sensitivity for each input.

Warm start:

The warm start (advanced basis initialization) is most suitable for models where the presolve algorithm does not generate a great problem size reduction since the presolve will be turned off (not available) when using a basis. In general it is best to try both with and without warm start for recursive runs.

Infeasibility analysis:

GUROBI has a built-in infeasibility finder. When activated the solver will produce an Irreducibly Inconsistent Set of constraints (IIS). The IIS will consist of a set of variable bounds and linear constraints which are infeasible together, but will become feasible if one or more member of the set is removed. This feature is available for both LP and MIP problems.

Presolve modifications and analysis:

The GUROBI presolve algorithm generally results in a number of problem reductions. This makes it easier for the solver algorithm to solve the final problem since a smaller version is normally more manageable. For models with few or no reductions, the presolve algorithm could be turned off for further speed-ups in the overall solution process.

In case the presolve algorithm detects infeasibility with limited information as to the source, IIS can be activated and used instead (or the problem rerun with the presolve).

Mixed-Integer Programming

GUROBI is the first solver suite to offer unlimited memory-shared core/cpu usage without additional costs for the parallelism. By default the solver will utilize as many cores/cpus as it sees fit for the particular problem and also produce deterministic results (i.e. solution path will be identical).

GUROBI uses a branch and cut algorithm to solve binary and integer programming problems. This involves (among other things) to solve a series of LP problems, apply problem cuts and implement heuristics in the search tree. In general this will be very computationally intensive and require significant RAM memory (and possible harddrive space) to complete the solution process.

The solver supports most standard variable types (apart from binary and integer): Semi-continuous (0 or in real interval), semi-integer (0 or in integer interval), special ordered sets of type 1 and 2.

It is also possible to supply a (partial) starting point for the MIP problem. The not known elements should be set as NaN in the start vector. The solver will then automatically repair the vector and if successful use the information to further improve the solution process.

Personal tools