Deaclaration of 3D variables with C++
Answered
I am using Gurobi with C++. I have a linear program involving decision variables with two indices x[][] and others with 3 indices w[][][] and f[][][]
There is no problem when declaring variables like this
GRBVar x[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
x[i][j] = model.addVar(0.0, 1.0, c[i][j], GRB_CONTINUOUS);
}
}
GRBVar f[n][n][n];
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
for (v = 0; v < n; v++) {
if(i!=j && j!=v && i!=v)
f[i][j][v] = model.addVar(0.0, 1.0, 0.0, GRB_CONTINUOUS);
}
}
}
GRBVar w[n][n][n];
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
for (v = 0; v < n; v++) {
w[i][j][v] = model.addVar(0.0, 1.0, 0.0, GRB_CONTINUOUS);
}
}
}
But when running, there is an error of stack overflow! Is there any mean to overcome this issue?
The cost matrix c[][] has two dimensions each one of 40. With less than 40, Gurobi runs successfully, but beyond 40, I have this issue of stack overflow.
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
Hi Ali,
Your arrays are too large to fit on the stack. By using sizeof, we see that each GRBVar element requires 8 bytes of memory. With \( n=39 \), your three GRBVar arrays require \(8(n^2 + 2n^3)\) = 961,272 bytes, or ~0.92 megabytes (one 2D array and two 3D arrays). With \( n = 40\), these arrays require 1,036,800 bytes, or ~0.99 megabytes. This suggests that your stack size is 1 megabyte, and your code has a few other stack allocations that, combined with these array allocations, exceed 1 megabyte.
Instead, you could allocate these arrays on the heap. E.g., for a three-dimensional array:
GRBVar ***x = new GRBVar**[n];
for (int i = 0; i < n; i++) {
x[i] = new GRBVar*[n];
for (int j = 0; j < n; j++) {
x[i][j] = new GRBVar[n];
}
}Be sure to free this memory once it's no longer needed.
Thanks,
Eli
1 -
It works.
Many thanks Eli.
0 -
Dear Eli,
How we can define variable types (Binary,..) in your suggested codes for the 3D variable?
Thanks.
0 -
Those loops just allocate space for the variable objects. You can use GRBModel::addVars() or GRBModel::addVar() to add the variables to your model (and simultaneously specify the variable type). E.g.,
x[i][j][k] = model.addVar(0.0, 1.0, 0.0, GRB_BINARY);
0 -
Hi Eli,
I am dealing with the same problem and I used your recommendation and defined all of the 2 and 3-dimensional variables as pointers. Now I want to call a 3D variable inside of a lazy constraint callback.
I'm not an expert in c++ and I don't know how should I do that.
Using the above example, is it correct to define my lazy constraint in this form or I am missing something here:
class LazyCut : public GRBCallback
{
public:
GRBVar ***x;
LazyCut (GRBVar*** xx) {
x= xx;
}
protected:
void callback() {
// whatever inside of the lazy constraint callback
}
};0 -
That looks correct. You should also make it easy to access the length of \( \texttt{x} \) within the callback:
class LazyCut : public GRBCallback
{
public:
GRBVar*** x;
int n;
LazyCut(GRBVar*** xx, int xn) {
x = xx;
n = xn;
}
protected:
void callback() {
// whatever inside of the lazy constraint callback
}
};The tsp_c++.cpp example is a good resource for using lazy constraints in the C++ API.
0 -
Hi Eli,
I want to define a two dimensional array in which the first dimension representing the vertices in a graph and the second dimension representing the edges in the graph. This means that the second dimension should be a pair type of edges.
To be clear, I want to define such variable where "E" represents the set of edges E={<u, v>, ...}
GRBVar y[num_vertices(g)][E]
Do you think it is better to define a three dimensional variable as you suggested above?
Or is there another way to be more efficient?
Thanks in advance.
0 -
I think the difference is a matter of style. I would use whichever approach is easier for you to understand and work with when building the model.
0 -
Thanks Eli for your reply!
As most of the graphs I'm using are sparse, I would like to define a two dimensional array in which the first dimension represents the vertices and the second dimension represents the edges. Something like the follwing
GRBVar y[num_vertices(g)][E] where E={<u, v>, ...}.
This helps me to be very efficient in time, but I don't know how to define such variable in gurobi in c++.
0 -
Can you use the same approach described above?
GRBVar **x = new GRBVar*[num_vertices];
for (int i = 0; i < num_vertices; i++) {
x[i] = new GRBVar[num_edges];
for (int j = 0; j < num_edges; j++) {
x[i][j] = model.addVar(...);
}
}0 -
Thanks Eli.
I could use it but in a different way.
I needed to define a map assigning a distinct integer number to each edge as I need to access the source and target of each edge through my constraints.
But I don't know without defining such a map whether we can define GRBVar **x in which the second dimension has such property. I mean something like the following:
GRBVar **x = new GRBVar*[num_vertices]; for (int i = 0; i < num_vertices; i++) { x[i] = new GRBVar[edges]; for (<u, v>: edges) { x[i][<u, v>] = model.addVar(...); } }
Again thanks Eli
0 -
I needed to define a map assigning a distinct integer number to each edge as I need to access the source and target of each edge through my constraints.
This sounds like a standard array or vector, where each distinct integer index "maps" to an edge. Is there a reason you don't want to index the second dimension of the 2D GRBVar array with the same indices used in the array/vector? If you define \(\texttt{edges}\) as a vector of pairs, you can iterate over the indices of the vector and still tell which nodes comprise each edge. E.g.:
std::vector<std::pair <int,int>> edges = {
{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 5}, {4, 5}
};
// Create x[i][j] for each node i and edge j
GRBVar **x = new GRBVar*[num_vertices];
for (int i = 0; i < num_vertices; i++) {
x[i] = model.addVars(edges.size());
}
// Iterate over indices of edges vector
for (int j = 0; j < edges.size(); j++) {
cout << "edges[" << j << "] = (" << edges[j].first << "," << edges[j].second << ")\n";
}If your constraints require you to iterate over the edges incident to a node, you would be better off constructing an adjacency list for each node. That is, for each node, you store the indices of edges that are incident to that node. This would work well with the above edge-index approach, especially if your edges are undirected.
If you really want to index the second dimension of the GRBVar array using the actual edge objects, you can't use a standard C++ array. You could instead define a \(\texttt{map}\) (or \(\texttt{unordered_map}\), if the edge data structure is hashable) using the edges as keys and the GRBVar objects as values:
std::map<std::pair<int,int>, GRBVar> *x = new std::map<std::pair<int,int>, GRBVar>[num_vertices];
for (int i = 0; i < num_vertices; i++) {
for (auto & e : edges) {
x[i][e] = model.addVar(...);
}
}With this approach, you may run into issues if the edges are undirected. For example, say you have an undirected edge \(\texttt{\{1,2\}}\) (or equivalently, \(\texttt{\{2,1\}}\)). If you use the pair \(\texttt{\{1,2\}}\) to index variables corresponding to that edge, you cannot later access those variables using \(\texttt{\{2,1\}}\) as an index.
0 -
Very helpful! Thanks a lot!
My graph is directed and I was looking for something like this as you gave above
map<edge, GRBVar> *x = new map<edge, GRBVar>[num_vertices]; for (int i = 0; i < num_vertices; i++) { for (auto & e : edges) { x[i][e] = model.addVar(...); } }Thanks again Eli!
1
Post is closed for comments.
Comments
14 comments