El Instituto de Ingeniería Matemática y Computacional (IMC) invita al seminario que se dictará la próxima semana.
Jasper van Doornmalen, Instituto de Ingeniería Matemática y Computacional, Pontificia Universidad Católica de Chile.
Miércoles 20 de noviembre de 2024, 13:40 hrs. (Presencial en auditorio Edificio San Agustín; link Zoom disponible escribiendo a Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.)
ABSTRACT
Optimization problems are often solved using constraint programming or mixed-integer programming techniques, using enumeration or branch-and-bound techniques. It is well known that if the problem formulation is very symmetric, there may exist many symmetrically equivalent solutions to the problem. Without handling the symmetries, traditional solving methods have to check many symmetric parts of the solution space, which comes at a high computational cost. Handling symmetries in optimization problems is thus essential for devising efficient solution methods.
The presentation will introduce and review common methods for solving mathematical programs, the concepts of symmetries in mathematical programs, and how symmetries can be handled. Then, the main results of Jasper's dissertation are presented, along with computational results. In particular, the presentation focuses on a general framework for symmetry handling that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other in the literature, the framework allows to apply different symmetry handling methods simultaneously and thus outperform their individual effects. Moreover, most existing symmetry handling methods only apply to binary variables. Our framework allows to easily generalize these methods to general variable types. Numerical experiments confirm that our novel framework is superior to the state-of-the-art methods implemented in the solver SCIP.
