Improved sorting-based procedure for integer programming

Dantchev, Stefan

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.
• Public URL: https://durham-repository.worktribe.com/output/1563608