Improved sorting-based procedure for integer programming

被引：4

作者：

Dantchev, S ^{[1
]}

机构：

[1] Univ Aarhus, Dept Comp Sci, Danish Natl Res Fdn, Basic Res Comp Sci Ctr, DK-8000 Aarhus C, Denmark

来源：

MATHEMATICAL PROGRAMMING | 2002年 / 92卷 / 02期

关键词：

multiple subset-sum problem; complete enumeration;

D O I：

10.1007/s101070100245

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Recently, Cornuejols and Dawande have considered a special class of 0-1 programs that turns out to be hard for existing IP solvers. One of them is a sorting-based algorithm, based on an idea of Wolsey. In this paper. we show how to improve both the running time and the space requirements of this algorithm. The drastic reduction of space needed allows us to solve much kuger instances than was possible before using this technique.

引用

页码：297 / 300

页数：4