Research Reports from the Department of Operations
Document Type
Report
Publication Date
4-21-1989
Abstract
Recently, valid inequalities derived from polytopal structure of the constraints are playing an important role in solving difficult combinatorial problems. These inequalities strengthen the LP relaxation of the problems and improve the lower bounds substantially. It is expected that in an branch-and-cut type algorithm stronger lower bounds will reduce size of the search tree and will minimize computational effort. In this paper , we consider an Assignment Problem with a single Knapsack Constraint (APKC). We present efficient procedures to identify valid inequalities for the APKC from the LP optimal solution. These inequalities can be strengthened by including additional variables for the same right hand side value (this procedure is known as "extension" or "lifting" of a valid inequality to higher dimensions). We use the underlying matching problem and the properties of the knapsack polytope to develop efficient extension procedures for the derived valid inequalities.
Keywords
Operations research, Mathematical optimization, Linear programming, Inequalities (Mathematics)
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 669
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Dhamankar, Sunil and Solow, Daniel, "Valid Inequalities for Constrained Assignment Problems" (1989). Research Reports from the Department of Operations. 633.
https://commons.case.edu/wsom-ops-reports/633
