A class of hard small 0–1 programs

A class of hard small 0–1 programs

0.00 Avg rating0 Votes
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: ,
Keywords: programming: dynamic
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.