Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms (Q1096544)

The problem (P) addressed here is a special set partitioning problem with two additional non-trivial constraints. A Lagrangean Relaxation \((LR_ u)\) is proposed to provide a lower bound to the optimal solution to this problem. This Lagrangean relaxation is accomplished by a subgradient optimization procedure which solves at each iteration a special 0-1 knapsack problem (KP-k). We give two procedures to solve (KP-k), namely an implicit enumeration algorithm and a column generation method. The approach is promising for it provides feasible integer solutions to the side constraints that will hopefully be optimal to most of the instances of the problem (P). Properties of the feasible solutions to (KP-k) are highlighted and it is shown that the linear programming relaxation to this problem has a worst case time bound of order \(O(n^ 3)\).