Lazy constrainst doesn't work
AnsweredI have a graph labeled on the edges, where multiple edges can have the same label, and my model tries to minimize the number of labels necessary to obtain a connected subgraph of the original one. In other words, I'm trying to obtain the minimum spanning subgraph. The solution returned by my model is a binary array that represents wich labels are in my subgraph. First I have a constraint that ensures each node from the original graph are in the subgraph. At the callbacks, I verify if the returned solution generates a connected subgraph, if it doesn't, I identify each component of the subgraph and add a cut between each one of them. My problem is that for a few instances of my dataset, the model is returning a solution that doesn't generate a connected subgraph. When I printed the lazy constraints added to the model, I noticed that some cuts added in the last callback where not being satisfied, it seems that the model is ignoring the lazy constraints and I can't figure out why.
The "Grafo" class is a representation of a graph using the union-find method to better calculate the number of components on the graph.
class mycallback: public GRBCallback {
public:
int numVars;
GRBVar* vars;
vector<GRBLinExpr*> restricoes;
Grafo* grafo;
~mycallback() {
for(inti=0; i<restricoes.size(); i++)
deleterestricoes[i];
}
mycallback(intnumVars, GRBVar*vars, Grafo*grafo) {
this->numVars = numVars;
this->vars = vars;
this->grafo = grafo;
}
protected:
voidcallback () {
Grafo* solution;
stringstream ss;
vector<int> compConexas;
vector<int*> labelsComp;
vector<int> tamanhoComp;
Edge* atual;
int numCompConexas;
if(where == GRB_CB_MIPSOL) {
double* z = getSolution(vars, numVars);
//Following the union-find method, grafo-roots is a vector containing the roots of the component where each node are inserted
solution = newGrafo(grafo->roots.size(), grafo->edges.size());
for(int i=0; i<grafo->edges.size(); i++) {
if(z[i] == 1)
solution->addLabel(grafo->edges, i);
}
numCompConexas = solution->numCompConexas; //Number of connected components on the graph with the edges labeled by the labels on solution
//Verify if the solution graph is connected
if(numCompConexas > 1) {
for(int i=0; i<solution->roots.size(); i++) {
if(!isOnTheArray(compConexas, solution->root(solution->roots[i]))) { //isOnTheArray verifies if a given integer is on a vector
compConexas.push_back(solution->root(solution->roots[i]));
labelsComp.push_back(newint[solution->edges.size()]);
for(int j=0; j<solution->edges.size(); j++)
labelsComp[compConexas.size()-1][j] = 0;
}
}
if(numCompConexas == 2) {
for(int i=0; i<grafo->edges.size(); i++) {
atual = grafo->edges[i]->next;
while(atual != nullptr) {
if(solution->root(atual->x) != solution->root(atual->y)) {
labelsComp[0][atual->label] = 1;
labelsComp[1][atual->label] = 1;
}
atual = atual->next;
}
}
} else {
for(int i=0; i<grafo->edges.size(); i++) {
atual = grafo->edges[i]->next;
while(atual != nullptr) {
if(solution->root(atual->x) != solution->root(atual->y)) {
for(int j=0; j<compConexas.size(); j++) {
if(compConexas[j] == solution->root(atual->x))
labelsComp[j][atual->label] = 1;
else if(compConexas[j] == solution->root(atual->y))
labelsComp[j][atual->label] = 1;
}
}
atual = atual->next;
}
}
}
for(int i=0; i<compConexas.size(); i++) {
ss.str("");
ss.clear();
ss<<"corte_novo-"<<compConexas[i];
restricoes.push_back(new GRBLinExpr);
*(restricoes.back()) = 0;
for(intj=0; j<solution->edges.size(); j++)
*(restricoes.back()) += vars[j] * labelsComp[i][j];
if(compConexas.size() == 2)
break;
}
//In every callback adds all the lazy constraints again
for(int i=0; i<restricoes.size(); i++)
addLazy(*(restricoes[i]) >= 1.0);
for(int i=0; i<labelsComp.size(); i++)
delete []labelsComp[i];
labelsComp.clear();
}
compConexas.clear();
delete solution;
delete[] z;
}
}
};
vector<int>* mip(Grafo* grafo, vector<int>* initialSolution, double* mipGap) {
Grafo* solucao; //graph
vector<int>* labelsSolucao; //labels in the solution
stringstream ss;
GRBEnv* env = 0;
GRBVar* z;
double* lb;
double* ub;
double* obj;
char* type;
string* variaveis;
vector<int>* labels;
int numLabels = grafo->edges.size(); //number of labels on the graph
env = new GRBEnv();
GRBModel model = GRBModel(*env);
model.set(GRB_StringAttr_ModelName, "MLST");
model.set(GRB_IntParam_OutputFlag, 0);
model.set(GRB_DoubleParam_TimeLimit, 36000);
model.set(GRB_IntParam_LazyConstraints, 1);
lb = new double[numLabels];
ub = new double[numLabels];
obj = new double[numLabels];
type = new char[numLabels];
variaveis = new string[numLabels];
for(int i=0; i<numLabels; i++) {
ss.str("");
ss.clear();
ss << "z" << i;
lb[i] = 0;
ub[i] = 1;
obj[i] = 1;
type[i] = GRB_BINARY;
variaveis[i] = ss.str();
}
z = model.addVars(lb, ub, obj, type, variaveis, numLabels);
for(int i=0; i<numLabels; i++)
z[i].set(GRB_DoubleAttr_Start, 0);
for(int i=0; i<initialSolution->size(); i++)
z[initialSolution->at(i)].set(GRB_DoubleAttr_Start, 1);
model.set(GRB_IntAttr_ModelSense, GRB_MINIMIZE);
int numCompConexas;
GRBLinExpr sum;
//Adds the restriction about each node being present in the solution graph
for(int i=0; i<grafo->roots.size(); i++) {
ss.str("");
ss.clear();
ss << "corte-" << i;
labels = grafo->getLabelsInVertice(i); //Returns the labels of all the edges that reach the node i
sum = 0;
for(int j=0; j<labels->size(); j++) {
sum += z[j] * labels->at(j);
}
model.addConstr(sum >= 1.0, ss.str());
delete labels;
}
mycallback cb = mycallback(numLabels, z, grafo);
model.setCallback(&cb);
model.optimize();
labelsSolucao = new vector<int>;
for(int i=0; i<numLabels; i++)
if(z[i].get(GRB_DoubleAttr_X) == 1)
labelsSolucao->push_back(i);
*mipGap = model.get(GRB_DoubleAttr_MIPGap);
delete []variaveis;
delete []lb;
delete []ub;
delete []obj;
delete []type;
delete env;
return labelsSolucao;
}
-
Official comment
-
Gurobi Staff
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?. -
-
-
The problem could be these conditional statements:
if (z[i] == 1)
if (z[i].get(GRB_DoubleAttr_X) == 1)Gurobi uses an integer feasibility tolerance (default 1e-5) to determine if a variable's value is integral. Thus, it's possible for binary variables to assume values like \( 0.999999 \neq 1 \). See the article Why does Gurobi sometimes return non-integral values for integer variables? for more information.
Can you try relaxing these statements? E.g.:
if (z[i] > 1 - 1e-5)
if (z[i].get(GRB_DoubleAttr_X) > 1 - 1e-5)1 -
-
Thanks Eli, it was these two conditionals. I fixed and it's working now. Thank you for the help.
0 -
Post is closed for comments.
Comments
3 comments