A Class of Hard Small 0-1 Programs

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 are 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.