On the calculation of true and pseudo penalties in multiple choice integer programming

The general solution approach leading to the global optimum for multiple choice integer programming uses the branch-and-bound procedure designed for special ordered sets. Incorporated in such a solution procedure, the partitioning strategy based on a weighted mean method is the most often adopted to calculate the pseudo penalties on the partitioned subconstraints for branching and backtracking. Based on a reformulation and transformation technique, the authors show that the calculation of true penalties on these partitioned subconstraints can be performed efficiently.