UFL::simulate_root

In this section, we will simulate the root node of a branch and cut tree. First we will solve the initial LP relaxation to get an initial lower bound. Depending on the solver implementation, the call si->initialSolve() typically calls the primal simplex method.

  si->initialSolve();  
  double current_lb = si->getObjValue();
  double current_ub = si->getInfinity();

Then, we repeatedly

• find an upper bound using the heuristic in find_upperbound(),
• find and add new cuts using the separation routine in generate_cuts(),
• find and add new cuts using CGL in generate_cuts_CGL(),
• and resolve the LP.

Depending on the solver implementation, the call si->resolve() typically calls the dual simplex method. At each iteration, we measure the new upper bound, lower bound and gap. We stop when either no new cuts have been found, there is less than 1% improvement in the bound or we have exceeded 100 iterations.

  while((newcuts || improvement > 0.01) && iterations <= 100){
    //find an upper bound using a simple rounding heuristic
    new_ub = find_upperbound();
    if(new_ub < current_ub) 
      current_ub = new_ub;
    gap = 100 * (current_ub - current_lb) / current_ub;

    //generate new logical cuts
    newcuts = generate_cuts();
    newcuts += generate_cuts_CGL();
    
    //resolve to produce a new lower bound
    si->resolve();
    new_lb = si->getObjValue();
    improvement = (new_lb - current_lb) / new_lb;
    current_lb = new_lb;
    iterations++;
  }
  gap = 100 * (current_ub - current_lb)/current_ub;
  return gap;

The next two sections expand on the heuristic find_upperbound() and the separation routines generate_cuts() and generate_cuts_CGL().