On solving the progressive party problem as a mixed integer problem

On solving the progressive party problem as a mixed integer problem

0.00 Avg rating0 Votes
Article ID: iaor20042302
Country: United Kingdom
Volume: 30
Issue: 11
Start Page Number: 1713
End Page Number: 1726
Publication Date: Sep 2003
Journal: Computers and Operations Research
Authors:
Keywords: heuristics
Abstract:

The ‘Progressive Party Problem’ has long been considered a problem intractable for branch-and-bound mixed integer solvers. Quite impressive results have been reported with constraint programming systems for this problem. As a result the problem has become a standard example in texts on constraint programming. Fortunately, there has been progress in the mixed integer programming arena: we can solve now larger and more difficult problems than ever before. Improvements in algorithmic theory, solvers, modeling environments and computer hardware created a new situation, where reported cases of unsolvable instances of mixed integer programming models need to be re-examined possibly with another outcome. In this paper we will show that we can solve the ‘Progressive Party Problem’ formulated as a large MIP problem, using standard, off-the-shelf hardware and software. A simple myopic heuristic is also implemented and can solve the problem in a fraction of the time.

Reviews

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