A class of hard small 0-1 programs

In this article, we consider a class of 0-1 programs that, although innocen t looking, is a challenge for existing solution methods. Solving even small instances from this class is extremely difficult for conventional branch-a nd-bound or branch-and-cut algorithms. We also experimented with basis redu ction algorithms and with dynamic programming without much success. The art icle then examines the performance of two other methods: a group relaxation for 0,1 programs, and a sorting-based procedure following an idea of Wolse y. Although the results with these two methods are somewhat better than wit h 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.