Solving the Case Mix Problem Optimally by Using Branch-and-Price Algorithms

This paper describes a methodology for the case mix problem in the health care sector. Aiming at maximizing the overall financial contribution of the given resource capacity within a hospital, the case mix problem is formulated as an integer linear programming model to produce the optimal patient mix pattern together with its associated resource allocation scheme. In order to solve the huge integer program optimally, an efficient solution approach, branch-and-price, is proposed, developed and implemented in this research. When studied from the column generation perspective, the integer linear programming model can be formulated differently. According to different decomposition units, namely wards, surgeon groups and patient groups, three decomposition based reformulations are built respectively. Among them, the first two reformulations are suitable to be solved within the framework of branch-and-price, while this is not the case for the last one. Numerical experiments are carried out, and the computational results are presented and compared, which demonstrate that the branch-and-price approach outperforms the integer linear programming method significantly and that decomposition on wards performs much better than decomposition on surgeon groups both with respect to the solution quality and the computation speed