GUROBI Appendix A

From TomWiki

Jump to: navigation, search

Notice.png

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

Contents

The Matlab Interface Routines - Main Routines

gurobi

Purpose

GUROBI solves mixed-integer linear (MILP) problems of the form


\begin{array}{ccccccl}
\min\limits_{x} & f(x) = c^T x  \\
s/t & x_{L} & \leq  & x    & \leq  & x_{U} \\
& b_{L} & \leq  & Ax   & \leq  & b_{U} \\
&       &       & x_i \mathrm{\ \ integer} &  & i \in I \\
\end{array}

where c, x, x_{L}, x_{U} \in \mathbb{R}^{n}, A\in
\mathbb{R}^{m\times n} and b_{L},b_{U}\in \mathbb{R}^{m}. The variables x \in I, the index subset of 1,...,n, are restricted to be integers.

Calling Syntax

[x, slack, v, rc, f k, ninf, sinf, Inform, basis, lpiter, glnodes, iis, sa] = ... gurobi(c, A, x L, x U, b L, b U, grbControl, 
PriLev, IntVars, SC, SI, ... sos1, sos2, logfile, savefile, iisRequest, iisFile, saRequest, basis, xIP)

Description of Inputs

The following inputs are used:

InputDescription
cLinear objective function cost coefficients, vector n × 1.
ALinear constraint matrix for linear constraints, dense or sparse matrix m × n.
x_LLower bounds on x.
x_UUpper bounds on x.
b_LLower bounds on the linear constraints.
The following parameters are optional:
b_UUpper bounds on the linear constraints. If empty, then inf is assumed.
grbControlStructure, where the fields are set to the GUROBI parameters that the user wants to specify (not case-sensitive). For example:

grbControl.LPMETHOD = 0 %Primal instead of Dual simplex grbControl.IterationLimit = 20 % Limit the simplex iterations

PriLev Printing level in the GUROBI interface.

= 0 Silent

= 1 Warnings and Errors

= 2 Summary information

= 3 More detailed information

> 10 Pause statements, and maximal printing

IntVarsDefines which variables are integers, of general type I or binary B Variable indices should be in the range [1, ..., n]. IntVars is a logical vector ==> x(find(IntVars > 0)) are integers IntVars is a vector of indices ==> x(IntVars) are integers (if [], then no integers of type I or B are defined) GURONI checks which variables has x L=0 and x U=1, i.e. binary.
SCA vector with indices for the integer variables of type Semi-continuous (SC), i.e. that takes either the value 0 or a real value in the range [xL (i), xU (i)], assuming for some j, that i = SC (j), where i is an variable number in the range [1, ..., n].
SIA vector with indices for the integer variables of type Semi-integer (SI), i.e. that takes either the value 0 or an integer value in the range [xL (i), xU (i)], assuming for some j, that i = SI e(j), where i is an variable number in the range [1, ..., n].
sos1A structure defining the Special Ordered Sets of Type One (sos1). Assume there are k sets of type sos1, then sos1(k).var is a vector of indices for variables of type sos1 in set k. sos1(k).row is the row number for the reference row identifying the ordering information for the sos1 set, i.e. A(sos1(k).row,sos1(k).var) identifies this information. As ordering information, also the objective function coefficients c could be used. Then as row number,

0 is instead given in sos1(k).row.

sos2A structure defining the Special Ordered Sets of Type Two (sos2). Specified in the same way as sos1 sets; see sos1 input variable description.
logfileName of file to write the GUROBI log information to. If empty, no log is written.
savefileName of file to write GUROBI problem just prior to calling the GUROBI solver. The file extension will control the type of file generated (mps, lp or rlp).
iisRequestIIS request. Set this to 1 if IIS information is needed for infeasible models.
iisFileName of file to write IIS information to. No file is written if this input parameter is empty or if no such information is available. The file name must have the extension .ilp
saRequestStructure telling whether and how you want GUROBI to perform a sensitivity analysis (SA).

You can complete an SA on the objective function, right hand side vector, lower and upper bounds. The saRequest structure contains four sub structures:

.obj, .rhs, .xl, .xu

Each one of these contain the field:

.index

.index contain indices to variables or constraints of which to return possible value ranges.

The .index array has to be sorted, ascending.

To get an SA of objective function on the four variables 120 to 123 (included) and variable

19, the saRequest structure would look like this:

saRequest.obj.index = [19 120 121 122 123];

The result is returned through the output parameter 'sa'.

basisVector with GUROBI starting basis. If re-solving a similar problem several times, this can be set to the 'basis' output argument of an earlier call to gurobi.m. The length of this vector must be equal to the sum of the number of rows (m) and columns (n).

The first m elements contain row basis information, with the following possible values for non-ranged rows:

0 associated slack/surplus/artificial variable nonbasic at value 0.0

1 associated slack/surplus/artificial variable basic

and for ranged rows (both upper and lower bounded)

0 associated slack/surplus/artificial variable nonbasic at its lower bound

1 associated slack/surplus/artificial variable basic

2 associated slack/surplus/artificial variable nonbasic at its upper bound

The last n elements, i.e. basis(m+1:m+n) contain column basis information:

0 variable at lower bound

1 variable is basic

2 variable at upper bound

3 variable free and nonbasic

xIPVector with MIP starting solution, if known. Missing values may be set to NaN. Length should be equal to number of columns in problem.

Description of Outputs

The following fields are used:

OutputDescription
xSolution vector x with decision variable values (n × 1 vector).
slackSlack variables (m × 1 vector).
vLagrangian multipliers (dual solution vector) (m × 1 vector).
rcReduced costs. Lagrangian multipliers for simple bounds on x.
f_kObjective function value at optimum.
ninfNumber of infeasibilities.
sinfSum of infeasibilities.
InformSee section A.3.
basisBasis status of constraints and variables, ((m + n) × 1 vector). See inputs for more information.
lpiterNumber of simplex iterations.
glnodesNumber of nodes visited.
iisStructure containing IIS information. For example, if lb = [1; 2; 3; 4], then the lower bounds for variables 1-4 are part of the IIS set.

If there were ranged constraints among the original constraints, the lb/ub outputs may contain indices higher than the original number of variables, since ranged constraints are transformed using slacks and those slack variables may become IIS set members. Fields:

iisStatus: Status flag. Possible values:

0 - IIS exist.

10015 - Model is feasible.

10016 - Model is a MIP.

lb: Variable whose lower bounds are in the IIS.

ub: Variable whose upper bounds are in the IIS.

constr: Constraints that are in the IIS.

saStructure with information about the requested SA, if requested. The fields:
objRanges for the variables in the objective function.
rhsRanges for the right hand side values.
xlRanges for the lower bound values.
xuRanges for the upper bound values.
These fields are structures themselves. All four structures have identical field names:
statusStatus of the SA operation. Possible values:

1 = Successful.

0 = SA not requested.

-1 = Error: begin is greater than end.

-2 = Error: The selected range (begin...end) stretches out of available variables or con- straints.

-3 = Error: No SA available.

lower The lower range.

upper The upper range.

Description

The interface routine gurobi calls GUROBI to solve LP, and MILP problems. The matrix A is transformed in to the GUROBI sparse matrix format.

Error checking is made on the lengths of the vectors and matrices.

gurobiTL

Purpose

GUROBI solves mixed-integer linear (MILP) problems of the form


\begin{array}{ccccccl}
\min\limits_{x} & f(x) = c^T x  \\
s/t & x_{L} & \leq  & x    & \leq  & x_{U} \\
& b_{L} & \leq  & Ax   & \leq  & b_{U} \\
&       &       & x_i \mathrm{\ \ integer} &  & i \in I \\
\end{array}

where c, x, x_{L}, x_{U} \in \mathbb{R}^{n}, A\in
\mathbb{R}^{m\times n} and b_{L},b_{U}\in \mathbb{R}^{m}. The variables x \in I, the index subset of 1,...,n, are restricted to be integers.

Calling Syntax

Prob = ProbCheck(Prob, 'gurobi'); 
Result = gurobiTL(Prob);  or
Result = tomRun('gurobi', Prob, 1);

Description of Inputs

Problem description structure. The following fields are used:

InputDescription
QP.c Linear objective function cost coefficients, vector n × 1.
ALinear constraint matrix for linear constraints, dense or sparse m × n matrix.
b_LLower bounds on the linear constraints.
b_UUpper bounds on the linear constraints.
x_LLower bounds on design parameters x. If empty assumed to be -I nf .
x_UUpper bounds on design parameters x. If empty assumed to be I nf .
PriLevOptPrinting level in gurobi.m file and the GUROBI C-interface.

= 0 Silent

= 1 Warnings and Errors

= 2 Summary information

= 3 More detailed information

> 10 Pause statements, and maximal printing (debug mode)

MIPStructure holding information about mixed integer optimization.
grbControlStructure, where the fields are set to the GUROBI parameters that the user wants to specify

(not case-sensitive). For example:

grbControl.LPMETHOD = 0 %Primal instead of Dual simplex grbControl.IterationLimit = 20 % Limit the simplex iterations

IntVarsDefines which variables are integers, of the general type I or binary B. Variable indices should be in the range [1,...,n]. If I ntV ars is a logical vector then all variables i where I ntV ars(i) > 0 are defined to be integers. If I ntV ars is determined to be a vector of indices then x(I ntV ars) are defined as integers. If the input is empty ([]), then no integers of type I or B are defined. The interface routine gurobi.m checks which of the integer variables have lower bound xL = 0 and upper bound xU = 1, i.e. are binary 0/1 variables.
SCA vector with indices for the integer variables of type Semi-continuous (SC), i.e. that takes either the value 0 or a real value in the range [xL (i), xU (i)], assuming for some j, that i = SC (j), where i is an variable number in the range [1, ..., n].
SIA vector with indices for the integer variables of type Semi-integer (SI), i.e. that takes either the value 0 or an integer value in the range [xL (i), xU (i)], assuming for some j, that i = SI (j), where i is an variable number in the range [1, ..., n].
sos1A structure defining the Special Ordered Sets of Type One (sos1). Assume there are k sets of type sos1, then sos1(k).var is a vector of indices for variables of type sos1 in set k. sos1(k).row is the row number for the reference row identifying the ordering information for the sos1 set, i.e. A(sos1(k).row,sos1(k).var) identifies this information. As ordering information, also the objective function coefficients c could be used. Then as row number, 0 is instead given in sos1(k).row.
sos2A structure defining the Special Ordered Sets of Type Two (sos2). Specified exactly as sos1 sets, see M I P.sos1 input variable description.
basisBasis for warm start of solution process. See Section A.1 for more information.
xIPVector with MIP starting solution, if known. NaN can be used to indicate missing values.

Length should be equal to number of columns in problem. Values of continuous variables are ignored.

GUROBIStructure with solver specific parameters for logging and saving problems. The following fields are used:
LogFileName of file to write the GUROBI log information to. If empty, no log is written.
SaveFileName of file to write GUROBI problem just prior to calling the GUROBI solver. The file extension will control the type of file generated (mps, lp or rlp).
iisRequestIIS request. Set this to 1 if IIS information is needed for infeasible models.
iisFileName of file to write IIS information to. No file is written if this input parameter is

empty or if no such information is available. The file name must have the extension .ilp

saStructure telling whether and how you want GUROBI to perform a sensitivity analysis (SA).

You can complete an SA on the objective function, right hand side vector, lower and upper bounds. The saRequest structure contains four sub structures:

.obj, .rhs, .xl, .xu

Each one of these contain the field:

.index

.index contain indices to variables or constraints of which to return possible value ranges. The .index array has to be sorted, ascending.

To get an SA of objective function on the four variables 120 to 123 (included) and variable

19, the saRequest structure would look like this:

saRequest.obj.index = [19 120 121 122 123];

The result is returned through the output parameter 'sa'.

Description of Outputs

Result structure. The following fields are used:

OutputDescription
IterNumber of iterations, or nodes visited.
ExitFlag0: Successful.

1: Time/Iterations limit exceeded.

2: Unbounded.

4: Infeasible.

10: Input errors.

-1: Other errors.

ExitTextSee A.3.
InformResult of GUROBI run. See section A.3 for details on the ExitText and possible Inform values.
x_0Initial starting point not known, set as empty.
f_kFunction value at optimum, f (xk ).
g_kGradient value at optimum, c.
x_kOptimal solution vector xk .
v_kLagrangian multipliers (for bounds and dual solution vector). Set as vk = [rc; v], where rc is the n-vector of reduced costs and v holds the m dual variables.
xStateState of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3; bState State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3; Solver Solver used - GUROBI.
SolverAlgorithmSolver algorithm used.
FuncEvNumber of function evaluations. Set to Iter. GradEv Number of gradient evaluations. Set to Iter.
ConstrEvNumber of constraint evaluations. Set to Iter. Prob Problem structure used.
MIP.ninfNumber of infeasibilities.
MIP.sinfSum of infeasibilities.
MIP.slackSlack variables (m × 1 vector).
MIP.lpiterNumber of LP iterations.
MIP.glnodesNumber of nodes visited.
MIP.basisBasis status of constraints and variables ( (m + n) × 1 vector) in the GUROBI format, fields xState and bState has the same information in the TOMLAB format. See Section A.1 for more information.
GUROBI.saStructure with information about the requested SA, if requested. The fields:
objRanges for the variables in the objective function.
rhsRanges for the right hand side values.
xlRanges for the lower bound values.
xuRanges for the upper bound values.

These fields are structures themselves. All four structures have identical field names:

statusStatus of the SA operation. Possible values:

1 = Successful.

0 = SA not requested.

-1 = Error: begin is greater than end.

-2 = Error: The selected range (begin...end) stretches out of available variables or con- straints.

-3 = Error: No SA available.

lowerThe lower range.
upperThe upper range.
GUROBI.iisStructure containing IIS information. For example, if lb = [1; 2; 3; 4], then the lower bounds for variables 1-4 are part of the IIS set.

If there were ranged constraints among the original constraints, the lb/ub outputs may contain indices higher than the original number of variables, since ranged constraints are transformed using slacks and those slack variables may become IIS set members. Fields:

iisStatus: Status flag. Possible values:

0 - IIS exist.

10015 - Model is feasible.

10016 - Model is a MIP.

lb: Variable whose lower bounds are in the IIS. ub: Variable whose upper bounds are in the IIS. constr: Constraints that are in the IIS.

Description

The interface routine gurobi calls GUROBI to solve LP, and MILP problems. The matrix A is transformed in to the GUROBI sparse matrix format.

An empty objective coefficient c-vector is set to the zero-vector.

Examples

See mip prob

M-files Used

gurobi.m

grbStatus

Purpose

grbStatus analyzes the GUROBI output Inform code and returns the GUROBI solution status message in ExitText and the TOMLAB exit flag in ExitFlag.

Calling Syntax

[ExitText, ExitFlag] = grbStatus(Inform)

Description of Inputs

The following inputs are used:

InputDescription
InformResult of GUROBI run.
1Model is loaded, but no solution information is available
2Model was solved to optimality (subject to tolerances), and an optimal solution is available
3Model was proven to be infeasible
4Model was proven to be either infeasible or unbounded
5Model was proven to be unbounded
6Optimal objective for model was proven to be worse than the value specified in the CUTOFF parameter. No solution information is available
7Optimization terminated because the total number of simplex iterations performed exceeded the value specified in the ITERATIONLIMIT parameter
8Optimization terminated because the total number of branch-and-cut nodes explored exceeded the value specified in the NODELIMIT parameter
9Optimization terminated because the time expended exceeded the value specified in the TIMELIMIT parameter
10Optimization terminated because the number of solutions found reached the value specified in the SOLUTIONLIMIT parameter
11Optimization was terminated by the user
12Optimization was terminated due to unrecoverable numerical difficulties otherwise Unknown status

Description of Outputs

The following fields are used:

OutputDescription
ExitTextText interpretation of GUROBI result.
ExitFlagTOMLAB standard exit flag.
Personal tools