Originally posted by: dlbur

Hello,

I'm attempting to use goals to implement a custom Branch-and-Cut algorithm for an MIP. I've used the ILOCPLEXGOAL3 macro to define a goal that solves a separation problem and adds global cuts. When I run my code, a cut is identified in the goal's execute function, but this same cut keeps occuring in all the subsequent iterations (producing an infinite loop). It seems that the cut isn't actually being incorporated into the B&C search. I verified this by exporting the formulation in the first line of the execute function. Here is my goal definition:

ILOCPLEXGOAL3(kPathsGoal, algorithm*, alg, IloIntVarArray, vars, ofstream&, summary_stream) {
    alg->rmp_inst->rmp_cplex.exportModel(filename);
 
   IloCplex::Goal goal = this;
   bool foundCut = false;
   int c;
 
    // solve k_psp for each commodity
    for (c = 0; c < alg->pars->ncommodities; c++) {
        IloExpr cut(getEnv()); //alg->rmp_inst->env
        if (alg->k_psp_inst->bc_iter(alg->opts, alg->pars, summary_stream, alg->rmp_inst, c, cut)) {
            foundCut = true;
        goal = AndGoal(GlobalCutGoal(cut <= 0), goal);
        cerr << cut << " <= 0" << endl;
        }
    }
    
    //If no cuts were found, start Benders feasibility cuts
    if(!foundCut)
      goal = AndGoal(BendersFeasGoal(getEnv(),alg,vars,summary_stream),goal);
   return goal;
}

You'll notice that if no cuts are found in the for loop, the Goal object is aggregated with a BendersFeasGoal object, which is another goal I define to identify Benders feasibility cuts. (I've omitted the definition of this goal, since the program never reaches this condition). Also, here's how I call the solve method:

rmp_cplex.solve(kPathsGoal(env, alg,x,summary_stream))

The argument x is an IloIntVarArray consisting of the binary variables in the MIP.

So, can anyone think of a reason why the cuts aren't being added?

Thanks.

I know this does not answer your question, but still: is there a reason you are using goals instead of callbacks? Usually callbacks are much easier to implement and maintain.

About the cut not being added: Can you please check by how much the cut is violated when you add it (what does getValue(cut) return)? Maybe the violation is so small that the cut is actually not violated and you keep adding a non-violated cut.

Originally posted by: dlbur

Thanks for the suggestion. Your observation was correct: I evaluated the cut, and it turns out the solution doesn't violate it. So, I suppose the problem is occuring in the separation procedure, rather than the goal implementation.

I decided to go with goals over callbacks after reading the "Goals and callbacks: a comparison" section in the CPLEX User's Manual. I got the impression that using goals would make it easier - or at least require less code - to collectively customize cuts, branching, and node selection strategies.

Originally posted by: dlbur

Okay, I went through my code and fixed the problem with the separation procedure. Now it is finding a cut that is violated by the incumbent solution. However, I'm seeing the same problem of the cut not being incorporated into the B&C tree. And, as before, I ran a few iterations and exported the formulation to verify that the cut is not added.

From what I've seen online, I take it that not many people use goals, but I'd like to stick with this approach if I can get it to work. Can you (or any other posters) think of what else could be wrong? Thanks.

How did you "export the formulation"? Did you just call IloCplex::exportModel()? That will never contain the cuts you added. In fact, in Concert-C++ there is no way to write out the model including any of the cuts that were added dynamically.

How do you see that the cut is not being incorporated into the B&C tree? Is the same cut violated again at a later point in time or how do you figure this out?

Originally posted by: dlbur

I was using IloCplex::exportModel(), and I belatedly realized that, as you point out, cuts won't show up in the file.

So, I've reexamined my code, and determined that I wasn't updating the solution I was feeding to the separation problem, so it kept producing the same cut. I've fixed that, and now it appears that new cuts are being added and different solutions are being obtained throughout the B&C tree. I'm still debugging, but I'm under the impression that the goals are doing what they're supposed to. Thanks.