Improved sorting-based procedure for integer programming

Dantchev, Stefan

doi:10.1007/s101070100245

Improved sorting-based procedure for integer programming

Dantchev, Stefan

Authors

Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor

Abstract

Recently, Cornuéjols 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 larger instances than was possible before using this technique.

Citation

Dantchev, S. (2002). Improved sorting-based procedure for integer programming. Mathematical Programming, 92(2), 297-300. https://doi.org/10.1007/s101070100245

Journal Article Type	Article
Publication Date	2002-04
Deposit Date	Mar 6, 2008
Journal	Mathematical Programming
Print ISSN	0025-5610
Electronic ISSN	1436-4646
Publisher	Springer
Peer Reviewed	Peer Reviewed
Volume	92
Issue	2
Pages	297-300
DOI	https://doi.org/10.1007/s101070100245
Keywords	Multiple subset-sum problem, Complete enumeration.