I am trying to implement benders decomposition for a simple fixed charge transportation problem for the purpose of learning. I implemented the classic Benders decomposition successfully by adding benders cuts as cutting planes to the master problem (generate cut and add to master - solve again ) and it works well ! But, when I wanted to treat benders cuts as lazy and user cut constraints, and embed them within the branch and bound, it doesn't work. Infact, when I only used benders cuts as a lazyconstraint, the algorithm worked out very well, but when I used them as both usercut and lazyconstraint, the programm couldn't stop, it kept calling usercutCallback at at the root node (please see the image below) and wouldn't make branch. I really don't know what the problem is.
Please below find the some part of the codes:
The codes related to adding benders cuts iteratively to the master problem:
void Benders::Benders_body()
{
#pragma region create relaxed master ILP
model_master = new IloModel(env_master);
createMasterILP();//set up master problem
#pragma endregion create relaxed master ILP
// Create subproblem IloCplex algorithm and subproblem LP for Benders' cuts separation
cplex_sub = IloCplex(env_sub);
createSubproblemLP();
// Create subproblem IloCplex algorithm and subproblem LP for Benders' cuts separation
// Set up the cut callback to be used for separating Benders' cuts
cplex_master = IloCplex(env_master);
cplex_master.extract(*model_master);
cplex_master.setParam(IloCplex::Param::Preprocessing::Presolve, IloFalse);
cplex_master.setParam(IloCplex::Param::Threads, 1);
// ***********Turn on traditional search for use with control callbacks***********
cplex_master.setParam(IloCplex::Param::MIP::Strategy::Search,IloCplex::Traditional);
//cplex_master.setOut(env_master.getNullStream());
//add lazy constraints (to handle integer nodes) and user call back (to handle fractional ones) to the model
cplex_master.use(BendersLazyCallback(env_master, data, *this));
cplex_master.use(BendersUserCallback(env_master, data, *this));
//cplex_master.exportModel("Mater-mathmodel.lp");
if (cplex_master.solve())
{
IloAlgorithm::Status solStatus = cplex_master.getStatus();
cout << "Solution status: " << solStatus << endl;
if (solStatus == IloAlgorithm::Optimal) {
cout << "master Objective" << "\t" << cplex_master.getObjValue() << "\n";
}
}
model_master->end();
model_sub->end();
cplex_master.end();
cplex_sub.end();
}
The code of the Lazy constraints callback macro:
ILOLAZYCONSTRAINTCALLBACK2(BendersLazyCallback, InputData , data, Benders &, B)
{
//initilize Y_bar which is fixed now to be used in the subproblem
IloArray<IloNumArray> Y_bar(B.Get_env_master(),data.Get_nWarehouse());
for (int i = 0; i < data.Get_nWarehouse(); ++i) {
Y_bar[i] = IloNumArray(B.Get_env_master());
getValues(Y_bar[i], B.Get_Y()[i]);
}
IloExpr BenCut(B.Get_env_master());
//cout << "ADD Lazy constraint" << "\n";
IloBool sepStat =B.separate(Y_bar, BenCut);
if (sepStat) {
if (B.Get_CutType() == 1)//benders feasibility cut
add(BenCut <= 0).end();
else if (B.Get_CutType() == 2)//benders optimality cut
add(B.Get_MaxFlow() >= BenCut).end();
}
BenCut.end();
return;
}
The code of the User cut callback macro:
ILOUSERCUTCALLBACK2(BendersUserCallback, InputData, data, Benders &, B)
{
//This method indicates whether or not the callback was invoked after CPLEX stopped generating cuts and called the callback a final time.
if (!isAfterCutLoop())
return;
//initilize Y_bar which is fixed now to be used in the subproblem
IloArray<IloNumArray> Y_bar(B.Get_env_master(),data.Get_nWarehouse());
for (int i = 0; i < data.Get_nWarehouse(); ++i) {
Y_bar[i] = IloNumArray(B.Get_env_master());
getValues(Y_bar[i], B.Get_Y()[i]);
}
IloExpr BenCut(B.Get_env_master());
IloBool sepStat =B.separate(Y_bar, BenCut);
if (sepStat) {
if (B.Get_CutType() == 1)//benders feasibility cut
add(BenCut <= 0).end();
else if (B.Get_CutType() == 2)//benders optimality cut
add(B.Get_MaxFlow() >= BenCut).end();
}
BenCut.end();
return;
}
The code of the separate function
IloBool Benders::separate(const IloArray<IloNumArray> Y_bar, IloExpr & BenCut)
{
IloBool violatedCutFound = IloFalse;
//update the rhs of the BigM constraints given the new Y_fixed
float minM2;
int counter = 0;
rhs_bigM = IloNumArray(env_sub, data.Get_nWarehouse()*data.Get_nCustomers());
for (int i = 0; i < data.Get_nWarehouse(); i++)
for (int j = 0; j < data.Get_nCustomers(); j++)
{
minM2 = std::min(data.Get_Capacity(i), data.Get_Demand(j));
rhs_bigM[counter] = minM2*Y_bar[i][j];
counter += 1;
}
BigM_constraints.setUbs(rhs_bigM);
cplex_sub.extract(*model_sub);
cplex_sub.solve();
//to save extreme points or dual values
Warehouse_Ray= IloNumVarArray(env_sub);
Customer_Ray= IloNumVarArray(env_sub);
BigM_Ray= IloNumVarArray(env_sub);
warehouse_ray= IloNumArray(env_sub);
customer_ray= IloNumArray(env_sub);
bigM_ray= IloNumArray(env_sub);
if (cplex_sub.getStatus() == IloAlgorithm::Infeasible) //primal subproblem is infeasible
{
cut_type = 1;
violatedCutFound = IloTrue;
cplex_sub.getDuals(warehouse_ray, Capacities_constraints);
cplex_sub.getDuals(customer_ray, Demands_constraints);
cplex_sub.getDuals(bigM_ray, BigM_constraints);
}
else if (cplex_sub.getStatus() == IloAlgorithm::Optimal)//subproblem is optimal
{
cut_type = 2;
violatedCutFound = IloTrue;
cplex_sub.getDuals(warehouse_ray, Capacities_constraints);
cplex_sub.getDuals(customer_ray, Demands_constraints);
cplex_sub.getDuals(bigM_ray, BigM_constraints);
}
BenCut = Get_BenCut(env_master);
Warehouse_Ray.end();
Customer_Ray.end();
BigM_Ray.end();
warehouse_ray.end();
customer_ray.end();
bigM_ray.end();
return violatedCutFound;
}
I should note that I am using Cplex 12.9 and C++ technology concert;
I would be grateful if you could help me out !
Best regards,
