Problem with very large matrix variables --- OverFlow error when setting objective?
Answered
Hi,
I currently have a model in which I optimize for the L2 norm (i.e. sum of all squared values) of an expression involving my optimization variable (a very large matrix X). Here is a snippet in gurobipy:
import gurobipy as gp
# N_1 (int). This is very large (around 30,000)
# E_vector (N_1^2 1D np.array)
# Create a new model model = gp.Model('optimization') # Define the optimization variable with a 0 lower bound: X = model.addMVar(shape=(N_1, N_1), name='X', lb=0)
# Define the optimization objective (L2 norm of a matrix difference):
X_vector = X.reshape(-1, order='C') delta = X_vector - E_vector
norm = delta @ delta
model.setObjective(norm, gp.GRB.MINIMIZE)
Here, I obtain an OverFlow Error that I can't really debug. The relevant traceback portion:
model.setObjective(norm, gp.GRB.MINIMIZE)
File "src/gurobipy/model.pxi", line 1474, in gurobipy.Model.setObjective
File "src/gurobipy/model.pxi", line 4373, in gurobipy.Model.setMObjective
OverflowError: value too large to convert to int
I don't understand what is the integer conversion that gurobi is attempting, and whether I can go around it. I checked related posts but was unable to find a proper solution. Any help would be appreciated. My machine has around 1.5T of RAM available and plenty of cores, in case some GUROBI hyperparameter choice could lead to efficient parallelization or better RAM usage (through monitoring memory usage, I noticed that I am not using more than 50% of the RAM I have available even though I did not set any memory limit in GUROBI).
-----------------------------------------------------------------------
There are also many constraints (expressed in matrix form). Since the error happens before their declaration, I don't think they matter, but I am writing them up because 1) maybe they do if the problem could be executed iteratively and 2) they can probably pose further space constraints that would be great to take into account:
- The rows and the columns of the optimization matrix must sum to given numbers
- An aggregated version of the matrix (C.T @ X @ C) must equal to a given matrix F
# P_0, P_1 (N_1 1D np.array)
# F (N_2 x N_2 2D np.array)
# C (N_1 x N_2 2D np.array)
#Define aggregate constraint (pre-compute to optimize):
X_aux = C.T @ X
X_agg = X_aux @ C
model.addConstr(X_agg == F)
#Define the marginal sums constraints:
model.addConstr(X.sum(axis=1) == P_0)
model.addConstr(X.sum(axis=0) == P_1)
Again, any help on the configuration of hyper parameters needed to solve a large problem of these sorts would be appreciated. Runtime isn't an issue for now.
Thanks!
-
Hi Gabriel,
Which version of Gurobi are you using? The line numbers in the error message will point to different parts of the source code for different versions.
- Riley
0 -
Hi Riley Clement, I am using gurobipy 11.0.1
0 -
Thanks Gabriel, I'll look into it and see what I find.
0 -
Hi Gabriel,
I'm not able to reproduce your problem due to limitations of my machine - it has 0.5TB of RAM and that is not enough to run your example code.
Looking at the source code I think I can see why there is an error.
I suspect that Gurobi will be not be able to solve this model even if we get around this error but here are some things for you to try:
i) instead of defining a Python variable called norm, define a Gurobi variable:
norm = model.addVar()
model.addConstr(norm == delta @ delta)
model.setObjective(norm, gp.GRB.MINIMIZE)ii) use the norm() function:
norm = model.addVar() model.addConstr(norm == gp.norm(delta, 2))
model.setObjective(norm*norm, gp.GRB.MINIMIZE)- Riley
0 -
Thanks a lot Riley Clement,
I think this helped on that specific line. Could I ask why these options avoid the error?When dealing with large MVars I also received other errors related to int conversion that do not seem obvious to me, and I wonder: is it a standard practice to just write these operations as constraints on auxiliary variables rather than python variables?
For example the following error has occurred too (E_vector is a large 1D array, and K is a Gurobi MLinExpr). I am currently looking into rewriting the lines by defining a new variable M_vector = model.addMVar(N_1). Would that be better (and why)?
Traceback (most recent call last):
File "optimize_test.py", line 87, in <module>
M_vector = E_vector * K
File "src/gurobipy/mlinexpr.pxi", line 1765, in gurobipy.MLinExpr.__rmul__
File "src/gurobipy/mlinexpr.pxi", line 1588, in gurobipy.MLinExpr.__mul__
File "src/gurobipy/mlinexpr.pxi", line 1691, in gurobipy.MLinExpr._mul_compact_ndarray
File "src/gurobipy/mlinexpr.pxi", line 1438, in gurobipy.MLinExpr.__imul__
File "src/gurobipy/mlinexpr.pxi", line 1506, in gurobipy.MLinExpr._imul_compact_ndarray
ValueError: Buffer dtype mismatch, expected 'int' but got 'long'0 -
Hi Gabriel,
The issue you encountered was due to the size of an MVar, arising from your norm expression, being assigned to a C int, which has a maximum value of 2147483647. The following will also fail for example:
m = gp.Model()
m.addMVar(shape=2147483647+1)The workarounds I gave you were to specifically target the problem I could see in the source code. I think you are going to keep running up against this assumption here that a model is only going to be so big in practice. It is very unlikely an LP with this many variables as yours can be solved in practice, and to complicate things you have a QP (or perhaps a MIQP). Our dev team is very confident a model like this cannot be solved, no matter what the machine specs are. I think you would need to try and identify if you can decompose your problem into smaller ones, or use techniques such as column generation, to make it solveable.
0
Please sign in to leave a comment.
Comments
6 comments