Getting the number of columns that enter the basis
OngoingHi everyone,
Is there currently a way to get the number of unique columns that have entered the basis when Gurobi solves a linear program by the simplex method? I looked through the list of attributes here (https://www.gurobi.com/documentation/current/refman/attributes.html), but I can't find this information.
Please let me know if I have missed it from the list, or if I need to code it manually to learn this information from Gurobi. Thanks!
-
-
Gurobi Staff
Hi,
You can use the variable attribute VBasis and the constraint attribute CBasis to extract the basis matrix given an LP optimal basic solution.
See the script below on how to extract the basis matrix. The code below assumes all constraints have unique names in the model and there is no redundant <= or >= constraints with +inf and -inf right-hand side values, respectively.
import gurobipy as gp
import numpy as np
import scipy.sparse as ss
BASIC = 0
SUPER_BASIC = -3
CBASIC = 0
def extract_basis(model) -> ss.csr_matrix:
"""Extract the basis matrix in sparse representation."""
model.optimize()
# Mapping constraint names to indices
constr_names_to_indices = {
c.ConstrName: i for i, c in enumerate(model.getConstrs())
}
m = model.NumConstrs
col_index = 0
# Initialize the lists to store the row and column indices of non-zero
# elements in the basis matrix
row_indices, col_indices, values= [], [], []
for v in model.getVars():
col = model.getCol(v)
# Find basic variables
if v.VBasis == BASIC:
for j in range(col.size()):
coeff, name = col.getCoeff(j), col.getConstr(j).ConstrName
row_index = constr_names_to_indices[name]
row_indices.append(row_index)
col_indices.append(col_index)
values.append(coeff)
col_index +=1
elif v.VBasis == SUPER_BASIC:
raise ValueError(f"Variable {v.varName} is superbasic!")
# Find constraints with slack variable in the basis
for c in model.getConstrs():
name = c.ConstrName
row_index = constr_names_to_indices[name]
if c.CBasis == CBASIC:
row_indices.append(row_index)
col_indices.append(col_index)
values.append(1)
col_index +=1
return ss.csr_matrix((values, (row_indices, col_indices)), shape=(m, m))Best regards,
Maliheh
0 -
-
Hi Maliheh,
Thanks for the code!! but what I am trying to do is to count the number of unique columns that ever enter the basis in the simplex method.
The code you posted seem to get the basis matrix at the end of the iteration, and it is not quite the same as what I need.
Thanks!
0 -
-
-
Thanks for the clarification. Yes, the code gives you only the optimal basis at the end.
It seems that you are looking for the entire history of the simplex algorithm. It is not possible to retrieve such information from Gurobi. Why do you need this information?
Best regards,
Maliheh
0 -
-
Hi Maliheh,
Thanks, I want this information primarily I am interested in knowing the number of distinct columns to enter the basis. A column can enter the basis multiple times based on the simplex method, so the number of iterations can potentially be higher than the number of columns that ever entered the basis.
I agree it sounds like looking for the entire history, but is it possible to just get the number of different columns that entered the basis (not necessarily the list of columns if that is not possible)?
For your information, I am mostly using R and Julia. I am mentioning this just in case the information I want can be obtained in the R or Julia API, but not in Python (I saw your sample code is in Python).
Thanks!!
0 -
Please sign in to leave a comment.
Comments
4 comments