THE GENERALIZED ASSIGNMENT PROBLEM - VALID INEQUALITIES AND FACETS

被引：27

作者：

GOTTLIEB, ES ^{[1
]}

RAO, MR ^{[1
]}

机构：

[1] NYU,STERN SCH BUSINESS,NEW YORK,NY 10003

来源：

MATHEMATICAL PROGRAMMING | 1990年 / 46卷 / 01期

关键词：

facets; Generalized assignment problem; integer polytope; knapsack problem; special ordered sets;

D O I：

10.1007/BF01585725

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Three classes of valid inequalities based upon multiple knapsack constraints are derived for the generalized assignment problem. General properties of the facet defining inequalities are discussed and, for a special case, the convex hull is completely characterized. In addition, we prove that a basic fractional solution to the linear programming relaxation can be eliminated by a facet defining inequality associated with an individual knapsack constraint. © 1990 North-Holland.

引用

页码：31 / 52

页数：22

共 33 条

[1]

[Anonymous], 2003, LINEAR PROGRAMMING

[2] INTEGER GENERALIZED TRANSPORTATION MODEL FOR OPTIMAL JOB ASSIGNMENT IN COMPUTER-NETWORKS [J].