Logic cuts for multilevel generalized assignment problems

Logic cuts for multilevel generalized assignment problems

0.00 Avg rating0 Votes
Article ID: iaor20043310
Country: Netherlands
Volume: 151
Issue: 1
Start Page Number: 238
End Page Number: 246
Publication Date: Nov 2003
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: branch and bound
Abstract:

In the multilevel generalized assignment problem (MGAP) agents can perform tasks at more than one efficiency level. Important manufacturing problems, such as lot sizing, can be easily formulated as MGAPs; however, the large number of variables in the related 0–1 integer program makes it hard to find optimal solutions to these problems, even when using powerful commercial optimization packages. The MGAP includes a set of knapsack constraints, one per agent, that can be useful for generating simple logical constraints or logic cuts. We exploit the fact that logic cuts can be generated in linear time and can be easily added to the model before solving it with classical branch and bound methodology. We generate all contiguous 1-cuts for every knapsack in large MGAPs and report the effect of adding these cuts in our experimental results.

Reviews

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