The integration of an interior-point cutting plane method within a branch-and-price algorithm (Q1881560)

The paper presents a modification of the branch-and-price method for solving integer programming problems which makes use of the interior point method. In contrast to classical column generation the new columns are obtained via cutting planes generated based on the analytic center of the relaxed master problem (ACCPM). The approach is theoretically and practically illustrated on the example of the capacitated location problem and the bin-packing problem. A main difficulty within the ACCPM approach is the update of the analytic center after adding cuts (adding constraints) and after branching (deleting constraints). These updates are performed by using a primal- respectively dual interior point method. The paper gives implementational details of the overall algorithm. A numerical comparison of the new approach with the performance of the Cplex-MIP package and Kelly's cutting plane branch-and-price approach shows the potential of this interior point branch-and-price method.