Dual Simplex Stucks when Barrier solves the model in C++
AnsweredHello,
I have formulate the CVRPTW problem which is solved by the barrier algorithm but when the dual simplex method crossover comes to optimize the solution it stucks forever showing me logs... Any idea why is this happening?
P.S i am attaching the constraints of the problem and where the problem starts to arrise...
namespace PDPTW_Constraints
{
int customers = 101;
int vehicles = 25;
void no_return_back(GRBVar*** x, GRBModel& model)
{
for (int i = 0; i < customers; i++)
{
for (int k = 0; k < vehicles; k++)
{
x[i][i][k].set(GRB_DoubleAttr_UB, 0);
}
}
}
void visit_once_constr(GRBVar*** x,GRBModel& model)
{
for(int i =1; i < customers; i++)
{
GRBLinExpr expr = 0.0;
for (int k = 0; k< vehicles; k++)
{
for (int j =1; j < customers; j++)
{
expr += x[i][j][k];
}
}
model.addConstr(expr == 1);
}
}
void arrives_at_depot(GRBVar*** x, GRBModel& model)
{
for (int k = 0; k < vehicles; k++)
{
GRBLinExpr expr = 0.0;
for (int i = 1; i < customers; i++)
{
expr += x[i][0][k];
}
model.addConstr(expr == 1);
}
}
void departs_from_depot(GRBVar*** x, GRBModel& model)
{
for (int k = 0; k < vehicles; k++)
{
GRBLinExpr expr = 0.0;
for (int j = 1; j < customers; j++)
{
expr += x[0][j][k];
}
model.addConstr(expr == 1);
}
}
void arrives_depart_same(GRBVar*** x, GRBModel& model)
{
for (int h = 1; h < customers; h++)
{
for (int k = 0; k < vehicles; k++)
{
GRBLinExpr expr1 = 0.0;
GRBLinExpr expr2 = 0.0;
GRBLinExpr expr3 = 0.0;
for (int i = 1; i < customers; i++)
{
expr1 += x[i][h][k];
}
for (int j = 1; j < customers; j++)
{
expr2 += x[h][j][k];
}
expr3 = expr1 - expr2;
model.addConstr(expr3 == 0, "c4");
}
}
}
void pickup_delivery_same(GRBVar*** x, int_vec_2d z, GRBModel& model)
{
for (int i = 1; i<customers; i++)
{
for (int j = 1; j < customers; j++)
{
GRBLinExpr expr1 = 0.0;
GRBLinExpr expr2 = 0.0;
GRBLinExpr expr3 = 0.0;
for (int k = 0; k < vehicles; k++)
{
if (z[i][j] == 1)
{
for (int l = 1; l < customers; l++)
{
expr1 += x[l][i][k];
}
for (int p = 1; p < customers; p++)
{
expr2 += x[p][j][k];
}
}
}
expr3 = expr1 - expr2;
model.addConstr(expr3 == 0, "c5");
}
}
}
void capacity_hold(GRBVar* y, GRBModel& model)
{
for (int i = 1; i < customers; i++)
{
GRBLinExpr expr = 0.0;
expr += y[i];
model.addConstr(expr <= 200);
}
}
void capacity_next_node(GRBVar*** x, GRBVar* y, const float_vec q,GRBModel& model) // HERE COMES THE PROBLEM WHEN I ENABLE THIS CONSTRAINT
{
for (int i = 1; i < customers; i++)
{
for (int j = 1; j <customers; j++)
{
GRBQuadExpr expr = 0.0;
for (int k = 0; k < vehicles; k++)
{
expr += x[i][j][k] * (y[i] + q[i] - y[j]);
}
model.addQConstr(expr == 0);
}
}
}
void depart_arrival(GRBVar*** x, const matrix c_matrix, const vec_pair time_window,GRBVar* arrival,GRBVar* depart,const float_vec service_time,GRBModel& model) // HERE ALSO
{
for (int i = 1; i < customers-1; i++)
{
for (int j = i+1; j < customers; j++)
{
for (int k = 0; k < vehicles; k++)
{
model.addGenConstrIndicator(x[i][j][k], true, depart[i] + c_matrix[i][j] <= arrival[j]);
model.addGenConstrIndicator(x[i][j][k], true,arrival[j] <= depart[j]);
model.addGenConstrIndicator(x[i][j][k], true, depart[i] <= depart[j]);
}
}
}
}
void time_interv_hold(int_vec_2d z, GRBVar* arrival, GRBModel& model) // HERE ALSO
{
GRBLinExpr expr0 = arrival[0];
model.addConstr(expr0 <= 100);
for (int i = 1; i < customers-1; i++)
{
for (int j = i+1; j < customers; j++)
{
GRBLinExpr expr = arrival[i];
if (z[i][j] == 1)
{
model.addConstr(expr <= arrival[j]);
}
}
}
}
}
Best Regards,
-
Hi Giorgos,
I have formulate the CVRPTW problem which is solved by the barrier algorithm but when the dual simplex method crossover comes to optimize the solution it stucks forever showing me logs... Any idea why is this happening?
The Barrier method followed by crossover solves the root node relaxation in about ~140 seconds. After that the B&B phase of the algorithm begins. VRPs are known to be hard to solve, thus it is not surprising that the algorithm proceeds slowly. In your particular case, it looks like finding a feasible solution point is problematic. You might want to experiment with the NoRelHeurTime parameter (set it to ~1200 seconds to start with). Additionally, you might want to have a look at Most important parameters for MIPs.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment