Conference Agenda

This master thesis integrates the component bound branching rule, proposed by Vanderbeck et al., into the branch-price-and-cut solver GCG. This rule, similarly to Vanderbeck's generic branching scheme, exclusively operates within the Dantzig-Wolfe reformulated problem, where branching decisions generally have no corresponding actions in the original formulation. The current GCG framework requires modifications for such branching rules, especially within the pricing loop, as seen in Vanderbeck's method implementation. These rules also fail to utilize enhancements like dual value stabilization.

A significant contribution of this thesis is the enhancement of the GCG architecture to facilitate the seamless integration of new branching rules that operate solely on the reformulated problem. This allows these rules to benefit from current and future improvements in the branch-price-and-cut framework, including dual value stabilization, without necessitating alterations to the branching rule itself.

The thesis proposes an interface to manage constraints in the master problem that lack counterparts in the original formulation. These constraints require specific modifications to the pricing problems to ensure their validity in the master. The 'generic mastercut' interface, tightly integrated into the GCG solver, spans the pricing loop, column generation, and dual value stabilization. Enhancements to the existing branching rule interface complement this integration, enabling effective utilization of the generic mastercuts.

Finally, the component bound branching rule will be implemented using this new interface and evaluated on a set of benchmark instances. Its performance will be benchmarked against the existing Vanderbeck branching rule, offering a practical comparison of both approaches.

The existing literature on the relax-and-cut framework discusses its usage to generate lower-ranked cuts for mixed-integer optimization problems. Such lower-ranked cuts are essential to avoid numerical troubles of the solving process (e.g., a branch-and-cut algorithm) involving cuts such as the Gomory mixed-integer cuts. However, this literature focuses mainly on closing the root node gap in a branch-and-cut tree to solve these problems and does not dive deep into solving these problems to optimality faster. The relax-and-cut framework in the SCIP optimization solver addresses this gap in the literature by employing various novel techniques and implementations.

This talk will discuss the relax-and-cut framework in SCIP, an open-source optimization solver for solving mixed-integer optimization problems via a branch-cut-and-price implementation. Specifically, it will highlight how this framework can be used for dual and primal bound improvements while solving an optimization problem. Computational experiments on the MIPLIB 2017 benchmark dataset show an improved solving time and the number of nodes, especially for harder instances.