New network relaxations and penalty calculations for 0-1 integer programs with multiple choice constraints are provided. The multiple choice problem, which may be viewed as a 0-1 problem with generalized upper bounding (GUB) restrictions, arises in a variety of applications involving scheduling, location and assignment. The new relaxations are designed to have special benefits for multiple choice problems with non-negative or non-positive coefficient matrices. The new penalties provide stronger bounds for both the previous (more general) and the new (more specialized) relaxations. In addition, the authors derive penalties for the multiple choice sets that exhibit a special additive property not available to LP relaxations.
All Science Journal Classification (ASJC) codes
- Signal Processing
- Information Systems
- Computer Science Applications