GUROBI Appendix A

From TomWiki
Jump to navigationJump to search

Notice.png

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

The Matlab Interface Routines - Main Routines

gurobi

Purpose

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

where , and . The variables , the index subset of , 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:

Input Description
c Linear objective function cost coefficients, vector n × 1.
A Linear constraint matrix for linear constraints, dense or sparse matrix m × n.
x_L Lower bounds on x.
x_U Upper bounds on x.
b_L Lower bounds on the linear constraints.
The following parameters are optional:
b_U Upper bounds on the linear constraints. If empty, then inf is assumed.
grbControl Structure, 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

IntVars Defines 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.
SC A 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].
SI A 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].
sos1 A 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.

sos2 A structure defining the Special Ordered Sets of Type Two (sos2). Specified in the same way as sos1 sets; see sos1 input variable description.
logfile Name of file to write the GUROBI log information to. If empty, no log is written.
savefile Name 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).
iisRequest IIS request. Set this to 1 if IIS information is needed for infeasible models.
iisFile Name 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
saRequest Structure 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'.

basis Vector 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

xIP Vector 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:

Output Description
x Solution vector x with decision variable values (n × 1 vector).
slack Slack variables (m × 1 vector).
v Lagrangian multipliers (dual solution vector) (m × 1 vector).
rc Reduced costs. Lagrangian multipliers for simple bounds on x.
f_k Objective function value at optimum.
ninf Number of infeasibilities.
sinf Sum of infeasibilities.
Inform See section A.3.
basis Basis status of constraints and variables, ((m + n) × 1 vector). See inputs for more information.
lpiter Number of simplex iterations.
glnodes Number of nodes visited.
iis Structure 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.

sa Structure with information about the requested SA, if requested. The fields:
obj Ranges for the variables in the objective function.
rhs Ranges for the right hand side values.
xl Ranges for the lower bound values.
xu Ranges for the upper bound values.
These fields are structures themselves. All four structures have identical field names:
status Status 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

where , and . The variables , the index subset of , 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:

Input Description
QP.c Linear objective function cost coefficients, vector n × 1.
A Linear constraint matrix for linear constraints, dense or sparse m × n matrix.
b_L Lower bounds on the linear constraints.
b_U Upper bounds on the linear constraints.
x_L Lower bounds on design parameters x. If empty assumed to be -I nf .
x_U Upper bounds on design parameters x. If empty assumed to be I nf .
PriLevOpt Printing 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)

MIP Structure holding information about mixed integer optimization.
grbControl Structure, 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

IntVars Defines 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.
SC A 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].
SI A 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].
sos1 A 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.
sos2 A structure defining the Special Ordered Sets of Type Two (sos2). Specified exactly as sos1 sets, see M I P.sos1 input variable description.
basis Basis for warm start of solution process. See Section A.1 for more information.
xIP Vector 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.

GUROBI Structure with solver specific parameters for logging and saving problems. The following fields are used:
LogFile Name of file to write the GUROBI log information to. If empty, no log is written.
SaveFile Name 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).
iisRequest IIS request. Set this to 1 if IIS information is needed for infeasible models.
iisFile Name 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

sa Structure 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:

Output Description
Iter Number of iterations, or nodes visited.
ExitFlag 0: Successful.

1: Time/Iterations limit exceeded.

2: Unbounded.

4: Infeasible.

10: Input errors.

-1: Other errors.

ExitText See A.3.
Inform Result of GUROBI run. See section A.3 for details on the ExitText and possible Inform values.
x_0 Initial starting point not known, set as empty.
f_k Function value at optimum, f (xk ).
g_k Gradient value at optimum, c.
x_k Optimal solution vector xk .
v_k Lagrangian 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.
xState State 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.
SolverAlgorithm Solver algorithm used.
FuncEv Number of function evaluations. Set to Iter. GradEv Number of gradient evaluations. Set to Iter.
ConstrEv Number of constraint evaluations. Set to Iter. Prob Problem structure used.
MIP.ninf Number of infeasibilities.
MIP.sinf Sum of infeasibilities.
MIP.slack Slack variables (m × 1 vector).
MIP.lpiter Number of LP iterations.
MIP.glnodes Number of nodes visited.
MIP.basis Basis 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.sa Structure with information about the requested SA, if requested. The fields:
obj Ranges for the variables in the objective function.
rhs Ranges for the right hand side values.
xl Ranges for the lower bound values.
xu Ranges for the upper bound values.

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

status Status 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.
GUROBI.iis Structure 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:

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

Description of Outputs

The following fields are used:

Output Description
ExitText Text interpretation of GUROBI result.
ExitFlag TOMLAB standard exit flag.