Variable Fixing for Max-Cut

Reduced cost fixing is an essential tool implemented in many mixed-integer programming solvers based on linear programming. During the branch-and-bound algorithm, the Lagrange multipliers of bound constraints are used to fix variables to certain values and thus, to reduce the problem size. However, it is challenging to adapt this idea for semidefinite programming, respectively for the well-known Max-Cut problem, since bound constraints are typically not included explicitly but are only enforced implicitly. In this talk, we discuss how variable fixing can be used for the Max-Cut problem and how the Lagrange multipliers can be computed numerically. We present promising results showing that the number of branch-and-bound nodes for Max-Cut can be drastically reduced by using variable fixing.