Advanced simplex routines#
This section describes a set of advanced basis routines. These routines allow you to compute solutions to various linear systems involving the simplex basis matrix. Note that these should only be used by advanced users. 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 the GRBsvec
data structure that is used to input or return sparse vectors:
typedef struct SVector {
int len;
int *ind;
double *val;
} GRBsvec;
The len
field gives the number of non-zero values in the vector. The
ind
and val
fields give the index and value for each non-zero,
respectively. Indices are zero-based. To give an example, the sparse
vector [0, 2.0, 0, 1.0]
would be represented as len=2
,
ind = [1, 3]
, and val = [2.0, 1.0]
.
The user is responsible for allocating and freeing the ind
and
val
fields. The length of the result vector for these routines is
not known in advance, so the user must allocate these arrays to hold the
longest possible result (whose length is noted in the documentation for
each routine).
-
int GRBFSolve(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 the Error Codes table for a list of possible return values. Details on the error can be obtained by calling
GRBgeterrormsg
.- Arguments:
model – The model. Note that the model must have a current optimal basis, as computed by
GRBoptimize
.b – The sparse right-hand side vector. It should contain one entry for each non-zero value in the input.
x – The sparse result vector. The user is responsible for allocating the
ind
andval
fields to be large enough to hold as many as one non-zero entry per constraint in the model.
-
int GRBBSolve(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 the Error Codes table for a list of possible return values. Details on the error can be obtained by calling
GRBgeterrormsg
.- Arguments:
model – The model. Note that the model must have a current optimal basis, as computed by
GRBoptimize
.b – The sparse right-hand side vector. It should contain one entry for each non-zero value in the input.
x – The sparse result vector. The user is responsible for allocating the
ind
andval
fields to be large enough to hold as many as one non-zero entry per constraint in the model.
-
int GRBBinvColj(GRBmodel *model, int j, GRBsvec *x)#
Computes the solution to the linear system \(Bx=A_j\), where \(B\) is the current simplex basis matrix and \(A_j\) is the column 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 the Error Codes table for a list of possible return values. Details on the error can be obtained by calling
GRBgeterrormsg
.- Arguments:
model – The model. Note that the model must have a current optimal basis, as computed by
GRBoptimize
.j – Indicates the index of the column of \(A\) to use as the right-hand side for the linear solve. The index
j
must be between 0 andcols-1
, wherecols
is the number of columns in the model.x – The sparse result vector. The user is responsible for allocating the
ind
andval
fields to be large enough to hold as many as one non-zero entry per constraint in the model.
-
int GRBBinvRowi(GRBmodel *model, int i, GRBsvec *x)#
Computes a single tableau row. More precisely, this routine returns row \(i\) from the matrix \(B^{-1} A\), where \(B^{-1}\) is the inverse of the basis matrix and \(A\) is the constraint matrix. Note that the tableau will contain columns corresponding to the variables in the model, and also columns corresponding to artificial and slack variables associated with constraints.
- Return value:
A non-zero return value indicates that a problem occurred while computing the desired vector. Refer to the Error Codes table for a list of possible return values. Details on the error can be obtained by calling
GRBgeterrormsg
.- Arguments:
model – The model. Note that the model must have a current optimal basis, as computed by
GRBoptimize
.i – The index of the desired tableau row.
x – The result vector. The result will contain one entry for each non-zero value. Note that the result may contain values for slack variables; the slack on row
i
will have indexcols+i
, wherecols
is the number of columns in the model. The user is responsible for allocating theind
andval
fields to be large enough to hold the largest possible result. For this routine, the result could have one entry for each variable in the model, plus one entry for each constraint.
-
int GRBgetBasisHead(GRBmodel *model, int *bhead)#
Returns the indices of the variables that make up the current basis matrix.
- Return value:
A non-zero return value indicates that a problem occurred while extracting the basis. Refer to the Error Codes table for a list of possible return values. Details on the error can be obtained by calling
GRBgeterrormsg
.- Arguments:
model – The model. Note that the model must have a current optimal basis, as computed by
GRBoptimize
.bhead – The constraint matrix columns that make up the current basis. The result contains one entry per constraint in \(A\). If
bhead[i]=j
, then columni
in the basis matrix \(B\) is columnj
from the constraint matrix \(A\). Note that the basis may contain slack or artificial variables. Ifbhead[i]
is greater than or equal tocols
(the number of columns in \(A\)), then the corresponding basis column is the artificial or slack variable from rowbhead[i]-cols
.