What are dual reductions?

Reductions are the names given to the different techniques used to transform a model during presolve (see How does presolve work?).  Reductions which are solely based on reasoning applied to the feasible region are known as "primal reductions", while dual reductions consider the objective function.  Primal reductions do not remove feasible solutions from the solution space where as dual reductions may, provided at least one optimal solution is guaranteed to remain.

When should dual reductions be disabled?

Dual reductions are very powerful however there are cases where are turned off automatically:

• When adding lazy constraints via a callback it is possible that there are optimal solutions which violate the lazy constraints, and optimal solutions which respect the lazy constraints.  If dual reductions are applied it may remove all the optimal solutions which respect the lazy constraints, and consequently the true optimal cannot be obtained.  Gurobi will automatically disable dual reductions when LazyConstraints=1.
• When computing an IIS it is possible that dual reductions interfere with the ability to determine whether a model is infeasible or unbounded, and this is important to distinguish.  Gurobi will automatically disable dual reductions when computing an IIS if required.
• When using Solution Pools it is possible that dual reductions may remove additional solutions that a user wishes the solver to find.  For example, some users are interested in finding all optimal solutions. Gurobi will automatically disable dual reductions when PoolSearchMode=2 (to systematically enumerate all optimal solutions or all solutions within a certain gap).

Note that dual reductions can be manually disabled by setting DualReductions=0.  In very rare instances this may improve performance, but typically it will make the solver perform worse.

A toy example

Let's consider the presolve reductions that are performed on an extension (to include a variable "w") to the toy model defined in mip1.py

The feasible region is defined by the following:

x + 2y + 3z <= 4   (1)
x + y >= w         (2)
w,x,y,z binary

Using a primal reduction called probing it can be seen from (1) that y and z cannot both be 1. So the following inequality is valid for all feasible solutions:

y + z <= 1         (3)

This inequality, together with the binary bounds on the variables, implies (1). To see this multiply (3) by 2, and combine this together with the inequalities x <= 1 and z <= 1.  Constraint (1) can therefore be discarded (a primal reduction) and the transformed feasible region is now defined by:

x + y >= w
y + z <= 1
w,x,y,z binary

Now consider this transformed feasible region together with the objective function x + y + 2z.  Note this problem has two optimal solutions (w,x,y,z):= (0,1,0,1) and (w,x,y,z):= (1,1,0,1).

max x + y + 2z
s.t.
x + y >= w
y + z <= 1
w,x,y,z binary

As discussed above, any reduction which relies on the objective for logic is a dual reduction. The first such reduction is made by noting that w does not appear in the objective function and is only bounded below by any constraint, and it can therefore be fixed to 0.  Note that fixing w:=0 eliminates one of the optimal solutions.  The transformed problem is now:

max x + y + 2z
s.t.
x + y >= 0     (4)
y + z <= 1
x,y,z binary

Note that (4) is redundant, as it is implied by the bounds on x and y, and so it can be discarded (a primal reduction) to obtain the following transformed problem:

max x + y + 2z
s.t.
y + z <= 1
x,y,z binary

Observe that x has a positive objective coefficient and is no longer bounded by by any constraint, so we can fix x to its upper bound of 1.  This fixing is a dual reduction since it removes feasible solutions with x = 0.  This reduction is reflected in a new objective function:

max y + 2z + 1
s.t.
y + z <= 1
y,z binary

The next dual reduction is one that recognizes that there is only one constraint which can prevent y and z from taking their upper bound and since the objective coefficients are positive this constraint will be satisfied with equality.  Replacing the constraint with y + z = 1 is a dual reduction since it removes feasible solutions with y = z = 0.  Using this equality an aggregation (a primal reduction) can be made using the substitution y:= 1 - z. The transformed problem now becomes

max z + 2
s.t.
z binary

The last dual reduction is similar to the first; z is not bounded above by constraints and has a positive objective coefficient, and so it can be fixed to 1, to arrive at the final transformed problem, in which all variables and constraints have been removed:

max 3

If you add the w variable to mip1.py and solve with DualReductions=0 the log will indicate the presolved model has 2 rows, 4 columns, 5 nonzeros - exactly what we derived before applying dual reductions.  If DualReductions=1 (the default) then we see the following in the output "Presolve: All rows and columns removed".

Further reading

• How does presolve work?