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 and val 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 and val 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 and cols-1, where cols is the number of columns in the model.

  • x – The sparse result vector. The user is responsible for allocating the ind and val 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 index cols+i, where cols is the number of columns in the model. The user is responsible for allocating the ind and val 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 column i in the basis matrix \(B\) is column j from the constraint matrix \(A\). Note that the basis may contain slack or artificial variables. If bhead[i] is greater than or equal to cols (the number of columns in \(A\)), then the corresponding basis column is the artificial or slack variable from row bhead[i]-cols

.