When a Solver model includes integer, binary or alldifferent constraints, it is called an integer programming problem. Integer constraints make a model non-convex, and finding the optimal solution to an integer programming problem is equivalent to solving a global optimization problem. Such problems may require far more computing time than the same problem without the integer constraints. When the Simplex LP or GRG Nonlinear Solving methods are used, Solver uses a Branch & Bound method for the integer constraints. The Evolutionary Solving method uses its own methods for such problems.
The Branch & Bound Method
The Branch & Bound method begins by finding the optimal solution to the “relaxation” of the problem, ignoring the integer constraints. If it happens that in this solution, the decision variables with integer constraints already have integer values, then no further work is required. If one or more integer variables have non-integral solutions, the Branch & Bound method chooses one such variable and “branches,” creating two new subproblems where the value of that variable is more tightly constrained. For example, if integer variable A1 has the value 3.45 at the solution, then one subproblem will have the additional constraint A1 <= 3 and the other subproblem will add the constraint A1 >= 4. These subproblems are solved and the process is repeated, “branching” as needed on each of the integer decision variables, until a solution is found where all of the integer variables have integer values (to within a small tolerance).
Hence, the Branch & Bound method may solve many subproblems, each one a “regular” Solver problem. The number of subproblems may grow exponentially. The “bounding” part of the Branch & Bound method is designed to eliminate sets of subproblems that do not need to be explored because the resulting solutions cannot be better than the solutions already obtained.
Many other methods, such as preprocessing and probing, cut generation, node and branch variable selection, local search and heuristics, can be applied to integer programming problems to mitigate the exponential growth of the number of subproblems, but all these methods normally operate within the Branch & Bound framework.