2461. On the ordering of sets for asymmetrical representations for generic set partitioning problems
Invited abstract in session WD-17: Diversity in Solutions to CO problems, stream Combinatorial Optimization.
Wednesday, 14:30-16:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Lars Jäger
|
| Institute of production management, Leibniz University Hannover | |
| 2. | Matthieu Gruson
|
| Analytique, Opérations et Technologies de l'Information, Université du Québec à Montréal | |
| 3. | Raf Jans
|
| Department of Logistics and Operations Management , HEC Montreal |
Abstract
Set partitioning problems, also known as binary clustering problems, are of fundamental importance in operations research. A key problem in these groups is that of inherent symmetry, which can be defined as the property of solutions that can be trivially transformed into each other without altering the structure or objective function value. One solution to this problem is an asymmetrical representative formulation (ARF), first proposed by Campêlo et al. (2004). In this approach, a set of constraints is introduced to ensure that only one of the symmetric solutions is valid, thereby ensuring that the optimal solution remains in the solution space, but not multiple times. This approach has been shown to be effective in reducing the solution time and increasing quality of standard solvers. It has been observed that for some of these ARFs, the input order of the sets is important for the strength of the LP relaxation and solving time. Some authors have proposed simple problem-specific set-order policies.
First, the ARF is explained by example, and second, the importance of the set-ordering is demonstrated. A new approach is used to visualize large instances for different problems in the literature. Finally, we propose a universal heuristic as an alternative to the problem-specific policies that are currently in use. These heuristics are compared to an newly developed exact approach, in order to ensure high-quality solutions.
Keywords
- Programming, Integer
- Mathematical Programming
Status: accepted
Back to the list of papers