Why the model is infeasible after adding lazy constraint
Awaiting user input
I am coding with C++ to build a tsp model by using C API. The model became infeasible after I adding the first lazy constraint which is a subtour elimination constraint. But when I add this constraint as a normal constraint by using GRBaddconstr function, the model is not infeasible. I cannot figure out the reason.
GRBstartenv(env);
GRBmodel *model = NULL;
GRBnewmodel(env,&model,"scooter",0,NULL,NULL,NULL,NULL,NULL);
// add variables r_ij
for(inti=0;i<sysInfo.num_nodes-1;++i){
for(intj=i+1;j<sysInfo.num_nodes;++j){
GRBaddvar(model,0,NULL,NULL,sysInfo.travel_cost[i][j],0.0,1.0, GRB_BINARY,NULL);
GRBupdatemodel(model);
}
}
int N = sysInfo.num_nodes;
vector<pair<int,int>>edges;
for(inti=0;i<N-1;++i){
for(intj=i+1;j<N;++j){
edges.push_back(make_pair(i,j));
}
}
usrData.cind=newint[N-1];
usrData.cval=newdouble[N-1];
// add (1a) and (1b)
intidx;
intcnt;
intbeg_tmp;
for(inti=0;i<N;++i){
cnt=0;
for(intj=0;j<N;++j){
if(i<j){
idx=distance(edges.begin(),find(edges.begin(),edges.end(),make_pair(i,j)));
usrData.cind[cnt]=idx;
usrData.cval[cnt]=1.0;
cnt++;
}
if(i>j){
idx=distance(edges.begin(),find(edges.begin(),edges.end(),make_pair(j,i)));
usrData.cind[cnt]=idx;
usrData.cval[cnt]=1.0;
cnt++;
}
}
GRBaddconstr(model,N-1,usrData.cind,usrData.cval, GRB_EQUAL,2.0,NULL);
GRBupdatemodel(model);
}
delete []usrData.cind;
delete []usrData.cval;
callback_data mydata;
mydata.n=N;
mydata.temp_edges=edges;
GRBgetintattr(model,"NumVars",&mydata.num_vars);
// define a function pointer
int(*functionPtr)(GRBmodel*,void*,int,void*)=subtourelim;
callback_data*mydataPtr=&mydata;
interror=GRBsetcallbackfunc(model, functionPtr,mydataPtr);
cout<<"error = "<<error<<endl;
GRBsetintparam(GRBgetenv(model),"LazyConstraints",1);
// optimize model
GRBoptimize(model);
void findsubtour(int n, double* sol, int* tourlenP, int* tour) {
inti,node,len,start;
intbestind,bestlen;
int*seen=newint[n];
for(i=0;i<n;++i)
seen[i]=0;
start=0;
bestlen=n+1;
bestind=-1;
while(start<n){
for(node=0;node<n;++node){
if(seen[node]==0)
break;
}
if(node==n)
break;
for(len=0;len<n;++len){
tour[start+len]=node;
seen[node]=1;
for(i=0;i<n;i++){
if(sol[node*n+i]>0.5&&!seen[i]){
node=i;
break;
}
}
if(i==n){
len++;
if(len<bestlen){
bestlen=len;
bestind=start;
}
start+=len;
break;
}
}
}
for(i=0;i<bestlen;++i){
tour[i]=tour[bestind+i];
}
*tourlenP=bestlen;
delete []seen;
}
int subtourelim(GRBmodel *model, void *cbdata, int where, void *usrdata) {
structcallback_data*mydata=(structcallback_data*) usrdata;
int n =mydata->n;
vector<pair<int,int>> edges_list = mydata->temp_edges;
int num_vars =mydata->num_vars;
int error;
int len;
if(where == GRB_CB_MIPSOL){
cout << "where = " << where << endl;
double* allsol =newdouble[num_vars];
int* tour =newint[n];
error = GRBcbget(cbdata, where, GRB_CB_MIPSOL_SOL, allsol);
// cout << "error = " << error << endl;
// print allsol
// for (int i = 0; i < edges_list.size(); ++i) {
// if (allsol[i] > 0.5){
// cout << edges_list[i].first << "--" << edges_list[i].second << endl;
// }
// }
double* sol =newdouble[n*n];
intcnt=0;
intind=0;
for(int i =0; i < n;++i){
for(int j =0; j < n;++j){
if(i == j){
sol[cnt]=0.0;
}
if(i < j){
ind = distance(edges_list.begin(),find(edges_list.begin(), edges_list.end(), make_pair(i,j)));
sol[cnt]=allsol[ind];
}
if(i > j){
ind = distance(edges_list.begin(),find(edges_list.begin(), edges_list.end(), make_pair(j,i)));
sol[cnt]=allsol[ind];
}
cnt++;
}
}
// print sol
// for (int i = 0; i < n*n; ++i) {
// cout << i << "= " << sol[i] << endl;
// }
// exit(0);
findsubtour(n, sol,&len, tour);
cout<<"len = "<< len << endl;
// print tour
for(int i =0; i < len;++i){
int temp =tour[i];
cout << temp << endl;
}
// exit(0);
if(len < n){
int* ind =newint[len*(len-1)/2];
double* val =newdouble[len*(len-1)/2];
int nz =0;
for(int i =0; i < len;++i){
for(int j = i+1; j < len;++j){
if(tour[i]<tour[j]){
auto it =find(edges_list.begin(),edges_list.end(),make_pair(tour[i],tour[j]));
ind[nz++]= it -edges_list.begin();
}
if(tour[i]>tour[j]){
auto it =find(edges_list.begin(),edges_list.end(),make_pair(tour[j],tour[i]));
ind[nz++]= it -edges_list.begin();
}
}
}
for(int i =0; i < nz;++i){
val[i]=1.0;
}
// print ind
for(int i =0; i < len*(len-1)/2;++i){
cout << i << "= " << ind[i] << ", " << val[i] << endl;
}
cout << "nz = " << nz << endl;
//exit(0);
error=GRBcblazy(cbdata, nz,ind, val, GRB_LESS_EQUAL, len -1);
cout<<"add lazy constraint!"<< endl;
cout<<"error = "<< error << endl;
delete [] ind;
delete [] val;
}
delete [] sol;
delete [] tour;
delete [] allsol;
}
return error;
}
0
-
Hi Dong Han,
Could you already solve your issue?
If not, could you show the solver output of your two runs, the one where you add the subtour elimination constraint during a callback and the other one where you add the constraint a priori to the model?
Please also output the constraints you are adding in the callback.
Additionally, could you write out the model as LP file before calling optimize() and post it here?
If it is too large, could you try to find a smaller TSP instance (with fewer nodes) that shows the same issue?Best regards,
Mario0
Please sign in to leave a comment.
Comments
1 comment