Advanced simplex routines#

This section describes a set of advanced basis routines. These routinesallow you to compute solutions to various linear systems involving thesimplex basis matrix. Note that these should only be used by advancedusers. We provide no technical support for these routines. Additionally,be aware that these routines are not supported by Gurobi Remote Services,such as Compute Server and Instant Cloud.

Before describing the routines, we should first describe theGRBsvecdata structure that is used to input or return sparse vectors:

typedefstructSVector{intlen;int*ind;double*val;}GRBsvec;

Thelen field gives the number of non-zero values in the vector. Theind andval fields give the index and value for each non-zero,respectively. Indices are zero-based. To give an example, the sparsevector[0,2.0,0,1.0] would be represented aslen=2,ind=[1,3], andval=[2.0,1.0].

The user is responsible for allocating and freeing theind andval fields. The length of the result vector for these routines isnot known in advance, so the user must allocate these arrays to hold thelongest possible result (whose length is noted in the documentation foreach routine).

intGRBFSolve(GRBmodel*model,GRBsvec*b,GRBsvec*x)#

Computes the solution to the linear system\(Bx=b\), where\(B\)is the current simplex basis matrix,\(b\) is an input vector, and\(x\) is the result vector.

Return value:

A non-zero return value indicates that a problem occurred while computing the desired vector.Refer to theError Codes tablefor a list of possible return values. Details on the error can be obtainedby callingGRBgeterrormsg.

Arguments:

• model – The model. Note that the model must have a current optimalbasis, as computed byGRBoptimize.

• b – The sparse right-hand side vector. It should contain one entryfor each non-zero value in the input.

• x – The sparse result vector. The user is responsible for allocatingtheind andval fields to be large enough to hold as many as onenon-zero entry per constraint in the model.

intGRBBSolve(GRBmodel*model,GRBsvec*b,GRBsvec*x)#

Computes the solution to the linear system\(B^Tx=b\), where\(B^T\) is the transpose of the current simplex basis matrix,\(b\) is an input vector, and\(x\) is the result vector.

Return value:

A non-zero return value indicates that a problem occurred while computing the desired vector.Refer to theError Codes tablefor a list of possible return values. Details on the error can be obtainedby callingGRBgeterrormsg.

Arguments:

• model – The model. Note that the model must have a current optimalbasis, as computed byGRBoptimize.

• b – The sparse right-hand side vector. It should contain one entryfor each non-zero value in the input.

• x – The sparse result vector. The user is responsible for allocatingtheind andval fields to be large enough to hold as many as onenon-zero entry per constraint in the model.

intGRBBinvColj(GRBmodel*model,intj,GRBsvec*x)#

Computes the solution to the linear system\(Bx=A_j\), where\(B\) is the current simplex basis matrix and\(A_j\) is thecolumn of the constraint matrix\(A\) associated with variable\(j\).

Return value:

A non-zero return value indicates that a problem occurred while computing the desired vector.Refer to theError Codes tablefor a list of possible return values. Details on the error can be obtainedby callingGRBgeterrormsg.

Arguments:

• model – The model. Note that the model must have a current optimalbasis, as computed byGRBoptimize.

• j – Indicates the index of the column of\(A\) to use as theright-hand side for the linear solve. The indexj must be between 0andcols-1, wherecols is the number of columns in the model.

• x – The sparse result vector. The user is responsible for allocatingtheind andval fields to be large enough to hold as many as onenon-zero entry per constraint in the model.

intGRBBinvRowi(GRBmodel*model,inti,GRBsvec*x)#

Computes a singletableau row. More precisely, this routine returnsrow\(i\) from the matrix\(B^{-1} A\), where\(B^{-1}\) isthe inverse of the basis matrix and\(A\) is the constraint matrix.Note that the tableau will contain columns corresponding to thevariables in the model, and also columns corresponding to artificial andslack variables associated with constraints.

Return value:

A non-zero return value indicates that a problem occurred while computing the desired vector.Refer to theError Codes tablefor a list of possible return values. Details on the error can be obtainedby callingGRBgeterrormsg.

Arguments:

• model – The model. Note that the model must have a current optimalbasis, as computed byGRBoptimize.

• i – The index of the desired tableau row.

• x – The result vector. The result will contain one entry for eachnon-zero value. Note that the result may contain values for slackvariables; the slack on rowi will have indexcols+i, wherecols is the number of columns in the model. The user is responsiblefor allocating theind andval fields to be large enough to holdthe largest possible result. For this routine, the result could have oneentry for each variable in the model, plus one entry for eachconstraint.

intGRBgetBasisHead(GRBmodel*model,int*bhead)#

Returns the indices of the variables that make up the current basismatrix.

Return value:

A non-zero return value indicates that a problem occurred while extracting the basis. Refer to theError Codes tablefor a list of possible return values. Details on the error can be obtainedby callingGRBgeterrormsg.

Arguments:

• model – The model. Note that the model must have a current optimalbasis, as computed byGRBoptimize.

• bhead – The constraint matrix columns that make up the current basis.The result contains one entry per constraint in\(A\). Ifbhead[i]=j, then columni in the basis matrix\(B\) iscolumnj from the constraint matrix\(A\). Note that the basismay contain slack or artificial variables. Ifbhead[i] is greaterthan or equal tocols (the number of columns in\(A\)), then thecorresponding basis column is the artificial or slack variable from rowbhead[i]-cols

.