these problem to and go back to 3 return Pseudocode In C++-like pseudocode, this could be written: // ILP branch and cut solution pseudocode, assuming objective is to be maximized ILP_solution branch_and_cut_ILP(IntegerLinearProgram initial_problem) { queue active_list; // L, above active_list.enqueue(initial_problem); // step 1 // step 2 ILP_solution optimal_solution; // this will hold x* above double best_objective = -std::numeric_limits<double>::infinity; // will hold v* above while (!active_list.empty()) { // step 3 above LinearProgram& curr_prob = active_list.dequeue(); // step 3.1 do { // steps 3.2-3.7 RelaxedLinearProgram& relaxed_prob = LP_relax(curr_prob); // step 3.2 LP_solution curr_relaxed_soln = LP_solve(relaxed_prob); // this is x above bool cutting_planes_found = false; if (!curr_relaxed_soln.is_feasible()) { // step 3.3 continue; // try another solution; continues at step 3 } double current_objective_value = curr_relaxed_soln.value(); // v above if (current_objective_value <= best_objective) { // step 3.4 continue; // try another solution; continues at step 3 } if (curr_relaxed_soln.is_integer()) { // step 3.5 best_objective = current_objective_value; optimal_solution = cast_as_ILP_solution(curr_relaxed_soln); continue; // continues at step 3 } // current relaxed solution isn't integral if (hunting_for_cutting_planes) { // step 3.6 violated_cutting_planes = search_for_violated_cutting_planes(curr_relaxed_soln); if (!violated_cutting_planes.empty()) { // step 3.6 cutting_planes_found = true; // will continue at step 3.2 for (auto&& cutting_plane : violated_cutting_planes) { active_list.enqueue(LP_relax(curr_prob, cutting_plane)); } continue; // continues at step 3.2 } } // step 3.7: either violated cutting planes not found, or we weren't looking for them auto&& branched_problems = branch_partition(curr_prob); for (auto&& branch : branched_problems) { active_list.enqueue(branch); } continue; // continues at step 3 } while (hunting_for_cutting_planes /* parameter of the algorithm; see 3.6 */ && cutting_planes_found); // end step 3.2 do-while loop } // end step 3 while loop return optimal_solution; // step 4 } In the above pseudocode, the functions LP_relax, LP_solve and branch_partition called as subroutines must be provided as applicable to the problem. For example, LP_solve could call the simplex algorithm. Branching strategies for branch_partition are discussed below. Branching strategies An important step in the branch and cut algorithm is the branching step. At this step, there are a variety of branching heuristics that can be used. The branching strategies described below all involve what is called branching on a variable. Branching on a variable involves choosing a variable, , with a fractional value, , in the optimal solution to the current LP relaxation and then adding the constraints and Most infeasible branching This branching strategy chooses the variable with the fractional part closest to 0.5. Pseudo cost