A note on reducing the number of variables in Integer Programming problems

被引：6

作者：

Zhu, N

Broughan, K

机构：

[1] Department of Mathematics, University of Waikato, Hamilton

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 1997年 / 8卷 / 03期

关键词：

integer programming; knapsack problem; dominated columns; integer variables;

D O I：

10.1023/A:1008675522511

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

A necessary and sufficient condition for identification of dominated columns, which correspond to one type of redundant integer variables, in the matrix of a general Integer Programming problem, is derived. The given condition extends our recent work on eliminating dominated integer variables in Knapsack problems, and revises a recently published procedure for reducing the number of variables in general Integer Programming problems given in the literature. A report on computational experiments for one class of large scale Knapsack problems, illustrating the function of this approach, is included.

引用

页码：263 / 272

页数：10

共 8 条

[1]

Babayev D. A., 1994, Computational Optimization and Applications, V3, P99, DOI 10.1007/BF01300969

[2]

BROUHAN K, 1993, IMA J MATH APPL BUSI, V5, P115

[3] A NOTE ON DOMINANCE RELATION IN UNBOUNDED KNAPSACK-PROBLEMS [J].

DUDZINSKI, K .

OPERATIONS RESEARCH LETTERS, 1991, 10 (07) :417-419

[4]

Martello S., 1990, Knapsack problems: Algorithms and computer implementations

[5]

Nemhauser G. L., 1988, Integer and Combinatorial Optimization

[6]

PISINGER D, 9433 DIKU

[7]

WILLIAMS HP, 1992, J OPNS RES SOC, V5, P387

[8]

ZHU N, 1995, 31 ANN C OR SOC NZ W

← 1 →