• Gurobi Staff

Hi Erik,

Could you try converting $$\texttt{t+inst.distance(i,j)}$$ to an $$\texttt{integer}$$ as $$\texttt{int(t+inst.distance(i,j))}$$?

Best regards,
Jaromił

Hi Jaromil,

I tried casting it to integer but the key error stays the same (except it shows a 42 instead of the float 42.0 in the x variables)
:-/

Thanks

Erik

• Gurobi Staff

Hi Erik,

Could you print the length of x in each dimension to check which key seems to be invalid?

Best regards,
Jaromił

Hi Jaromil,

how do I print its length in each dimension? Does the Gurobi API have a method for this?

Best regards,

Erik

• Gurobi Staff

Hi Erik,

$$\texttt{len(x)}$$ will provide you the length of $$\texttt{x}$$ combined over all for loops. You could simplify your code to have only one cluster $$\texttt{k}$$. You can then divide by the number of $$\texttt{inst.nodes(k)-1}$$ twice as you loop over them in the $$\texttt{i}$$ and $$\texttt{j}$$ loop with $$\texttt{i != j}$$. This should provide you the length of the $$\texttt{t}$$ dimension.

If the above does not work, you could just loop over the $$\texttt{t}$$ dimension and print the output until an error occurs (it's not the most elegant way but should work for this case)

t = 0while True:       print(str(x[3,0,t]))    t+=1

This way you can see how long your $$\texttt{t}$$ dimension is and then try to determine why it is too short.

Best regards,
Jaromił

Hi Jaromil,

len(x) equals 3890 for T = 400 (maximum time).

When I try to retrieve the length of the t dimension with either of your suggested methods I get a KeyError with t = 0, ,because t needs to be >= inst.distance(i, j).

The distance function of the inst returns the euclidean distance between the nodes i and j:

def distance(selfij):
return round(((self._x[str(i)] - self._x[str(j)])**2 + (self._y[str(i)] - self._y[str(j)])**2)**0.50)

Thanks,

Erik

• Gurobi Staff

Hi Erik,

You are right. Could you try start the $$\texttt{while True}$$ loop with $$\texttt{t=3}$$ or $$\texttt{t=4}$$. This should work.

Best regards,
Jaromił

Hi Jaromil,

I already started the while True loop at t = 42 as that is the value of the rounded euclidean distance between node 0 and 3 (x_0 = -5, y_0 = -5; x_3 = 32, y_3 = 15).

No matter where I start it (t = 43, 44, ...) it always throws the same error with the respective t (KEyError (3, 0 , 4X)

Could this have to do with how I formed my clusters? The clusters including nodes (reference via nodes(k) in the model) has 2 lists 0,1,2 and 3,4,5 whereas the cluster nodes excluding the depot ("_cluster_nodes") consist of the lists 1,2,3 and 4,5.
It seems like the t within my x variables is not the issue or am I wrong about this?

Thank you very much for any help so far!

Cheers,
Erik

• Gurobi Staff

Hi Erik,

Your explanation sounds reasonable. You could try to reduce the size of this example while preserving the error, e.g., reduce the cluster sizes to only 2 and maybe reduce $$T$$. You could also $$\texttt{print(x)}$$ before the problematic loops which will provide you your whole set of $$x$$ variables with all keys and then check if $$\texttt{(3,0,42)}$$ is missing to find out which dimension is the true evil here. You can even just $$\texttt{print(x[i,j,t])}$$ within the loop to get more information.

Let me know if this helped.

Best regards,
Jaromił

Ok I have tried printing the whole set of x variables and it becomes pretty clear that t should'nt be the 'evil' dimension.

The output with a reduced T (once T = 100, later T = 50) always iterates until x(5, 4, 50) or x(5, 4, 100):

Output for T = 50:

{(4, 5, 37): <gurobi.Var *Awaiting Model Update*>, (4, 5, 38): <gurobi.Var *Awaiting Model Update*>, (4, 5, 39): <gurobi.Var *Awaiting Model Update*>, (4, 5, 40): <gurobi.Var *Awaiting Model Update*>, (4, 5, <gurobi.Var *Awaiting Model Update*>, (5, 4, 37): <gurobi.Var *Awaiting Model Update*>, (5, 4, 38): <gurobi.Var *Awaiting Model Update*>, (5, 4, 39): <gurobi.Var *Awaiting Model Update*>, (5, 4, 40): <gurobi.Var *Awaiting Model Update*>, (5, 4,
41): <gurobi.Var *Awaiting Model Update*>, (4, 5, 42): <gurobi.Var *Awaiting Model Update*>, (4, 5, 43): <gurobi.Var *Awaiting Model Update*>, (4, 5, 44): <gurobi.Var *Awaiting Model Update*>, (4, 5, 45): <gurobi.Var *Awaiting Model Update*>, (5, 4, 46): <gurobi.Var *Awaiting Model Update*>, (5, 4, 47): <gurobi.Var *Awaiting Model Update*>, (5, 4, 48): <gurobi.Var *Awaiting Model Update*>, (5, 4, 49): <gurobi.Var *Awaiting Model Update*>, (5, 4, 50):robi.Var *Awaiting Model Update*>, (4, 5, 46): <gurobi.Var *Awaiting Model Update*>, (4, 5, 47): <gurobi.Var *Awaiting Model Update*>, (4, 5, 48): <gurobi.Var *Awaiting Model Update*>, (4, 5, 49): <gurobi.Var *Awaiting Model Update*>, (4, 5, 50): <gurobi.Var *Awaiting Model Update*>, (5, 4, 37): <gurobi.Var *Awaiting Model Update*>, (5, 4, 38): <gurobi.Var *Awaiting Model Update*>, (5, 4, 39): <gurobi.Var *Awaiting Model Update*>, (5, 4, 40): <gurobi.Var *Awaiting Model Update*>, (5, 4, 41): <gurobi.Var *Awaiting Model Update*>, (5, 4, 42): <gurobi.Var *Awaiting Model Update*>, (5, 4, 43): <gurobi.Var *Awaiting Model Update*>, (5, 4, 44): <gurobi.Var *Awaiting Model Update*>, (5, 4, 45): <gurobi.Var *Awaiting Model Update*>, (5, 4, 46): <gurobi.Var *Awaiting Model Update*>, (5, 4, 47): <gurobi.Var *Awaiting Model Update*>, (5, 4, 48): <gurobi.Var *Awaiting Model Update*>, (5, 4, 49): <gurobi.Var *Awaiting Model Update*>, (5, 4, 50): <gurobi.Var *Awaiting Model Update*>}

It always shows a KeyError in which either i or j equals 0.
Could it be that my clusters_nodes_depot need to include a depot in every cluster?

I included the depot ("0") in both clusters and now the model actually runs but is infeasible.

The original model in C++ definitely is not. It runs smoothly and returns an ObjVal.

Any ideas?

Thanks,
Erik

• Gurobi Staff

Hi Erik,

Are you iterating over the same sets? In the C++ code you iterate over $$\texttt{orders}$$ while in the Python code you iterate over $$\texttt{clusters}$$. I can't find $$\texttt{orders}$$ in the JSON file. If you can compile the C++ code, you could print the actually added indices by calling

#include <iostream>......std::cout << "(" << i << "," << j << "," << t << ")" << std::endl;

If this doesn't help, could you provide a minimum working example, i.e., a short compileable C++ code just adding the variables and the corresponding Python code and JSON file?

Best regards,
Jaromił

Hi Jaromil,

sorry for the confusion. Same model, different use case. The clusters correspond to the orders set in the C++ Code. You could help me understand the following lines in the code:

public:
explicit mip(const instance &inst)
: _inst{ &inst }
{
_nodes.resize(inst.orders().size());

for (const auto o : inst.orders())
{
_nodes[o] = inst.items(o);

_nodes[o].push_back(inst.depot());
}
}

inst.depot() is simply a 0 (integer).
Does the code above add the 0 to all lists within the orders() set? (which is a list of lists exactly like the cluster_nodes in the .json file)
Or is the 0 only added to one of those orders/clusters?

Thank you,
Erik

• Gurobi Staff

Hi Erik,

As it is not possible to determine what data structures $$\texttt{nodes, items}$$, and $$\texttt{orders}$$ are, from you answers and the previous conversation I will assume that $$\texttt{nodes}$$ is a $$\texttt{vector}$$ of $$\texttt{lists}$$, $$\texttt{items}$$ is a $$\texttt{vector}$$ of $$\texttt{integer lists}$$ and $$\texttt{orders}$$ is a $$\texttt{set}$$ of $$\texttt{integers}$$.

First, $$\texttt{nodes}$$ has the size of the $$\texttt{orders}$$ set, e.g., 2.
Then, we iterate over each element in the $$\texttt{orders}$$ set, i.e., we iterate over 2 orders 0-1.
Each $$\texttt{nodes}$$ entry 0-1 is assigned a list in the $$\texttt{items}$$ vector. Let's assume each list in the items vector is of length 3 and has all 1 entries.
Last, the integer 0 is inserted at the end of each list in each $$\texttt{nodes}$$ entry.
All in all, you get the following

_nodes[0] = {1,1,1,0}_nodes[1] = {1,1,1,0}

where the {...} brackets denote lists.

Concluding, 0 is not added to all lists within the orders() set, but to each list in each node.

If you are working with Visual Studio, you can use the Debugger to track all of the data structures and see what they look like at each time of interest. If you are not using Visual Studio, you can always print your data structures using standard functions.

Best regards,
Jaromił

Hi Jaromil,

thank you for your explanation (I have 0 experience in C++). My clusters did indeed need a 0 denoting the depot in each of them. The sets in the Code suggested as much.

I am running the model right now and it seems to be correct now as it returns optimal values for small instances.

Thank you very much!

Cheers,
Erik

• Gurobi Staff

Hi Erik,

Great! I am happy that your code works now.

Best regards,
Jaromił

Hi Jaromil,

I actually have follow-up question, if you don't mind.
I am used to accessing the solution values of variables via the X variable, but how would I access/extract only the t in my x[i, j, t] and p[i, j, t] variables?

I can't find any information on how to access the indices of variables in a solution.

Thanks again,
Erik

• Gurobi Staff

Hi Erik,

I am not sure if I fully understand. Do you want to iterate over $$t$$ only? This may lead to some problems as you may have multiple $$i, j$$ for a single $$t$$, e.g., $$4,5,37$$ and $$5,4,37$$.

Maybe the getVarByName() might help you in this case, if you make sure to name your variables uniquely. Note that if a name is not unique, then getVarByName() chooses which variable to return arbitrarily. You could name your variables, e.g., $$\texttt{"x_i_j_t"}$$, where $$\texttt{i,j,t}$$ are integers.

Best regards,
Jaromił

Hi Jaromil,

are my variable names not unique:

for k in inst.clusters():
for i in inst.nodes(k):
for j in inst.nodes(k):
if i != j:
for t in range(0, T + 1):
if inst.distance(i, j) <= t:
x[i, j, t] = m.addVar(vtype=GRB.BINARY, name="x_%s_%s_%s" % (i, j, t))

makespan = m.addVar(vtype=GRB.CONTINUOUS, lb=0.0, ub=T, name="makespan")

for i in inst.nodes():
for j in inst.nodes():
if i != j:
for t in range(0, T + 1):
if inst.distance(i, j) <= t:
p[i, j, t] = m.addVar(vtype=GRB.BINARY, name="p_%s_%s_%s" % (i, j, t))

Here i, j, t are all integers.

Thank you for your suggestion with the getVarByName() method.

Kind regards,
Erik

• Gurobi Staff

Hi Erik,

I am not sure if this is a question, but I will just answer anyway. Yes, your variable names are unique.

Best regards,
Jaromił