Presolving

Presolving is a technique used in mathematical optimization, particularly in constraint programming and mixed-integer programming, to simplify a problem before a full-scale solution method is applied. The goal of presolving is to reduce the size and complexity of the problem by eliminating redundant constraints, variables, and by deducing new information about the problem's structure. This can lead to significant speedups in the overall solution time.

Common presolving techniques include fixing variables to specific values based on constraint implications, removing dominated or redundant constraints, aggregating constraints, and identifying infeasible or unbounded subproblems. For example, if a constraint dictates that a variable must be less than or equal to 5, and another constraint dictates that the same variable must be greater than or equal to 10, presolving can immediately identify that the problem is infeasible. Similarly, if a variable can only take on a single value due to the constraints, it can be fixed to that value and all related constraints can be simplified.

The effectiveness of presolving depends heavily on the specific structure of the optimization problem. For some problems, presolving can dramatically reduce the problem size, making it solvable in a fraction of the time. For others, the overhead of the presolving steps might outweigh the benefits. Most modern optimization solvers incorporate sophisticated presolving routines as a standard part of their process. The simplified problem resulting from presolving is then passed to the main solving algorithm, such as a branch-and-bound or simplex method.