Constraint Logic Programming and Integer Programming approaches and their collaboration in solving an assignment scheduling problem

✍ Scribed by Ken Darby-Dowman; James Little; Gautam Mitra; Marco Zaffalon

• Publisher: Springer US
• Year: 1997
• Tongue: English
• Weight: 977 KB
• Volume: 1
• Category: Article
• ISSN: 1383-7133
• DOI: 10.1007/bf00137871

✦ Synopsis

Generalised Assignment Problems (GAP), traditionally solved by Integer Programming techniques, are addressed in the light of current Constraint Programming methods. A scheduling application from manufacturing, based on a modified GAP, is used to examine the performance of each technique under a variety of problem characteristics. Experimental evidence showed that, for a set of assignment problems, Constraint Logic Programming (CLP) performed consistently better than Integer Programming (IP). Analysis of the CLP and IP processes identified ways in which the search was effective. The insight gained from the analysis led to an Integer Programming approach with significantly improved performance. Finally, the issue of collaboration between the two contrasting approaches is examined with respect to ways in which the solvers can be combined in an effective manner.