On Solving The Progressive Party Problem as a MIP

Erwin Kalvelagen (erwingams.com)

Abstract: The `Progressive Party Problem' [smith1995] 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 MIP models need to 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.

Keywords: Mixed Integer Programming, Modeling

Category 1: Applications -- OR and Management Sciences (Other )

Citation: Report, GAMS Development Corp., June 2001.

Download: [Postscript][PDF]

Entry Submitted: 06/19/2001
Entry Accepted: 06/19/2001
Entry Last Modified: 06/19/2001

Modify/Update this entry