Symmetry Breaking in Mixed Integer Programming Models
Speaker
Abstract
| Production planning on multiple parallel machines is an interesting problem, both from a theoretical and practical point of view. The parallel machine lotsizing problem consists of finding the optimal timing and level of production and the best allocation of products to machines. In this paper we look at how to incorporate parallel machines in a Mixed Integer Programming model when using commercial optimization software. More specifically, we look at the issue of symmetry. When multiple identical machines are available, many alternative optimal solutions can be created by renumbering the machines. These alternative solutions lead to difficulties in the branch-and-bound algorithm. We propose new constraints to break this symmetry. We tested our approach on the parallel machine lotsizing problem with setup costs and times, using a network reformulation for this problem. Computational tests indicate that several of the proposed symmetry breaking constraints substantially improve the solution time, except when used for solving the very easy problems. The results highlight the importance of creative modeling in solving Mixed Integer Programming problems, specifically the potential added value of symmetry breaking constraints. We will also discuss some other examples of symmetry breaking related to clustering problems. |
| Let us know |
| Remember that this is a lunch meeting. For ordering the right amount of sandwiches, coffee, tea and milk, please let us know before Wednesday, May 7th whether you will be present. We hope to welcome all of you. |
| Contact information: |
| Wilco van den Heuvel |
