Resumen: Introducimos la violación discreta de Min-Max (DMMV) como un problema de optimización general que busca una asignación de valores discretos a variables que minimiza la mayor violación de la restricción. Esta formulación matemática sin contexto es aplicable a una amplia gama de casos de uso que tienen requisitos de rendimiento en el peor de los casos. Después de definir el problema de DMMV matemáticamente, exploramos sus propiedades para establecer una comprensión fundamental. Para abordar los tamaños de instancia de DMMV de relevancia práctica, desarrollamos una heurística acelerada con GPU que aprovecha las propiedades matemáticas de DMMV para acelerar el proceso de solución. Demostramos la aplicabilidad versátil de nuestra heurística al resolver tres problemas de optimización como casos de uso: (1) Cuantización posterior al entrenamiento de modelos de lenguaje, (2) tomografía discreta y (3) diseño de filtro de respuesta de impulso finito (FIR). En cuantificación sin separación atípica, nuestra heurística logra una mejora del 14% en promedio sobre los métodos existentes. En la tomografía discreta, reduce el error de reconstrucción en un 16% bajo ruido uniforme y acelera los cálculos en un factor de 6 en la GPU. Para el diseño del filtro FIR, casi logra una reducción de la ondulación del 50% en comparación con el uso del solucionador de optimización de enteros comerciales, GUROBI. Nuestros resultados comparativos apuntan a los beneficios de estudiar DMMV como un problema de optimización sin contexto y las ventajas que nuestra heurística propuesta ofrece en tres problemas distintos. Nuestra heurística acelerada con GPU se realizará de código abierto para estimular aún más la investigación sobre DMMV y sus otras aplicaciones. El código está disponible en esta URL HTTPS
Publicado Originalme en export.arxiv.org El 19 de agosto de 2025.
Ver Fuente Original
