Why the model is infeasible after adding lazy constraint

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;

}

正式なコメント

Simranjit Kaur

Gurobi Staff

2026年11月13日 01:36

This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support.

Mario Ruthmair

2023年11月08日 12:08

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,
Mario

Why the model is infeasible after adding lazy constraint

コメント

お探しのものを見つけられませんでしたか？