Article ID: | iaor20003029 |
Country: | United States |
Volume: | 11 |
Issue: | 2 |
Start Page Number: | 205 |
End Page Number: | 210 |
Publication Date: | Mar 1999 |
Journal: | INFORMS Journal On Computing |
Authors: | Cornujols Grard, Dawande Milind |
Keywords: | programming: dynamic |
In this article, we consider a class of 0–1 programs that, although innocent looking, is a challenge for existing solution methods. Solving even small instances from this class is extremely difficult for conventional branch-and-bound or branch-and-cut algorithms. We also experimented with basis reduction algorithms and with dynamic programming without much success. The article then examines the performance of two other methods: a group relaxation for 0,1 programs, and a sorting-based procedure following an idea of Wolsey. Although the results with these two methods ares somewhat better than with the other four when it comes to checking feasibility, we offer this class of small 0,1 programs as a challenge to the research community.