3
$\begingroup$

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.

enter image description here

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,

$\endgroup$
2
$\begingroup$

First, I don't understand why you extract the master model, set parameters and add the callback repeatedly inside a loop. When using a callback, the plan is to solve the master problem once, adding cuts via the callback along the way, so extracting the model etc. would be done once.

Second, and more directly related to your issue, while I'm not a C/C++ user I believe that applying end() to the cut you just added has the effect of removing it from the model. Try removing the calls to end() after add(). I think ending BenCut is harmless (but probably unnecessary, since it has local scope), but I might be wrong about that. (This is incorrect. As noted in a comment, the Benders ATSP example supplied by IBM invokes .end() on added cuts within the callback.)

$\endgroup$
8
  • $\begingroup$ Thanks for your comments ! Regarding your first comment, according to my understanding, at each iteration of benders decomposition method, one benders cut should be added to the master problem and the process continues until the gap between lower bound and upper bound would be very negligible. That's why I use a loop. About extracting the master model, you are right. I can put it outside the loop. But, I am not sure whether I can define the callback outside the loop as at each iteration one cut may add to the model using the callback. $\endgroup$
    – Sam
    Mar 17 at 9:23
  • $\begingroup$ regarding your second comment, as far as I know, the end() will be used to free the memory. The same approach is used at the examples located at the Cplex directory. $\endgroup$
    – Sam
    Mar 17 at 9:24
  • $\begingroup$ I think I make a mistake by combining the framework of classical benders using cutting planes and modern benders using lazy constraints $\endgroup$
    – Sam
    Mar 17 at 19:21
  • $\begingroup$ Your last comment is correct. Classical Benders restarts the solution of the master problem from the root node after each new constraint is added. With callbacks, you do a single solve of the master and add cuts "on the fly". $\endgroup$
    – prubin
    Mar 18 at 15:08
  • $\begingroup$ Does switching to a single call to solve() rather than a loop fix your problem? $\endgroup$
    – prubin
    Mar 18 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.