NETWORK RELAXATIONS AND LOWER BOUNDS FOR MULTIPLE CHOICE PROBLEMS.

Fred Glover, John M. Mulvey

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)385-393
Number of pages9
JournalINFOR Journal
Volume20
Issue number4
DOIs
StatePublished - Jan 1 1982

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'NETWORK RELAXATIONS AND LOWER BOUNDS FOR MULTIPLE CHOICE PROBLEMS.'. Together they form a unique fingerprint.

  • Cite this