Hispanopedia Wiki
HiGHS es un software de código abierto para resolver modelos de programación lineal (LP), programación entera mixta (MIP) y programación cuadrática convexa (QP). [1]
Escrito en C++ y publicado bajo una licencia MIT , HiGHS proporciona interfaces de programación para C , Python , Julia , Rust , JavaScript , Fortran y C# . No tiene dependencias externas. Hay disponible un práctico contenedor para Python a través del paquete PyPI de highspy .
Aunque generalmente son de un solo subproceso, algunos componentes de resolución pueden utilizar arquitecturas de múltiples núcleos. HiGHS está diseñado para resolver modelos a gran escala y aprovecha la escasez de problemas . Su rendimiento en relación con el software comercial y de código abierto se revisa periódicamente utilizando puntos de referencia estándar de la industria . [2]
El término HiGHS también puede referirse tanto al proyecto subyacente como al pequeño equipo que lidera el desarrollo del software.
Historia
HiGHS se basa en solucionadores escritos por estudiantes de doctorado del Grupo de Investigación Operativa y Optimización [3] de la Facultad de Matemáticas de la Universidad de Edimburgo . Sus orígenes se remontan a finales de 2016, cuando Ivet Galabova combinó su presolución de LP con el procedimiento de choque simplex de Julian Hall y el solucionador simplex dual de Huangfu Qi para resolver una clase de problemas de LP industriales más rápido que los mejores solucionadores de código abierto en ese momento. Desde entonces, se han desarrollado una API de C++ y otras interfaces de lenguaje, y se han agregado utilidades de modelado y otras categorías de solucionadores.
A principios de 2022, los proyectos de modelado de sistemas de energía abiertos GenX y PyPSA aprobaron una solicitud de financiación para el solucionador HiGHS en un esfuerzo por reducir la dependencia de su comunidad de bibliotecas propietarias. [4] Esa apelación resultó enFinanciación por valor de 76 000 dólares canadienses de Invenia Labs, Cambridge, Reino Unido, en julio de 2022. [5]
Solucionadores
Simplex
HiGHS tiene implementaciones del método simplex revisado primal y dual para resolver problemas de programación lineal, basado en técnicas descritas por Hall y McKinnon (2005), [6] y Huangfu y Hall (2015, 2018). [7] [8] Estas incluyen la explotación de la hiperesparcimiento al resolver sistemas lineales en las implementaciones simplex y, para el solucionador simplex dual, la explotación de subprocesos múltiples. El rendimiento del solucionador simplex en relación con el software comercial y de código abierto se informa regularmente utilizando puntos de referencia estándar de la industria. [9]
Punto interior
HiGHS tiene una implementación del método de punto interior para resolver problemas de PL, basada en técnicas descritas por Schork y Gondzio (2020). [10] Se destaca por resolver el sistema de Newton de manera iterativa mediante un método de gradiente conjugado preacondicionado , en lugar de hacerlo directamente, a través de una descomposición LDL* . El desempeño del solucionador de punto interior en relación con el software comercial y de código abierto se informa regularmente utilizando puntos de referencia estándar de la industria. [11]
Programación entera mixta
HiGHS cuenta con un solucionador de ramificación y corte para problemas MIP. Su desempeño en relación con el software comercial y de código abierto se informa periódicamente utilizando puntos de referencia estándar de la industria. [12]
Programación cuadrática
HiGHS tiene un solucionador de conjuntos activo para problemas de programación cuadrática convexa (QP).
Aplicaciones que utilizan HiGHS
HiGHS se puede utilizar como una biblioteca de resolución independiente en aplicaciones a medida, pero los entornos de computación numérica, los paquetes de programación de optimización y los proyectos de análisis numérico específicos del dominio también están comenzando a incorporar el software en sus sistemas.
Soporte de cálculo numérico
Como potente software de código abierto en desarrollo activo, HiGHS está siendo adoptado cada vez más por proyectos de software de aplicación que brindan soporte para análisis numérico . La biblioteca científica SciPy , por ejemplo, utiliza HiGHS como su solucionador LP [13] desde la versión 1.6.0 [14] y el solucionador MIP HiGHS para optimización discreta desde la versión 1.9.0. [15] Además de ofrecer una interfaz para HiGHS, el lenguaje de modelado JuMP para Julia [16] también describe el uso específico de HiGHS en su documentación de usuario. [17] El solucionador MIP en la biblioteca NAG se basa en HiGHS, [18] y HiGHS es el solucionador LP y MIP predeterminado en MathWorks Optimization Toolbox. [19]
Modelos de sistemas energéticos abiertos
HiGHS ahora también es utilizado por algunas aplicaciones específicas del dominio, incluido un entorno de modelado de sistemas de energía abierto . La versión basada en la web del modelo multisectorial europeo PyPSA implementa el solucionador HiGHS de forma predeterminada a partir de febrero de 2022. [20] [21] El proyecto GridCal que desarrolla software de sistemas de energía orientado a la investigación agregó soporte opcional para HiGHS en febrero de 2022. [22]
Véase también
- Lista de software de optimización
- Optimización matemática
- Evaluación comparativa numérica
- Método simplex
Enlaces externos
- Repositorio de GitHub
- Documentación del software
Referencias
- ^ Hall, Julian (21 de septiembre de 2020). HiGHS: software de código abierto de alto rendimiento para optimización lineal (PDF) . Edimburgo, Reino Unido: Universidad de Edimburgo . Consultado el 27 de febrero de 2022 . Presentación.
- ^ "Puntos de referencia para software de optimización". Árbol de decisiones para software de optimización . Marzo de 2022. Consultado el 31 de marzo de 2022 .
- ^ "Optimización e Investigación Operativa: Facultad de Matemáticas". Marzo de 2022. Consultado el 31 de marzo de 2022 .
- ^ Parzen, Maximilian; Hall, Julian; Jenkins, Jesse; Brown, Tom (31 de marzo de 2022). Solucionadores de optimización: el eslabón perdido para un ecosistema de modelado de sistemas energéticos totalmente de código abierto (PDF) . doi :10.5281/zenodo.6409432 . Consultado el 3 de abril de 2022 .
Propuesta de financiación de ocho páginas que también ofrece una hoja de ruta relativamente detallada.
- ^ "Se recibió una donación de $76k de Invenia Labs para apoyar a HiGHS". Facultad de Matemáticas, Universidad de Edimburgo . Edimburgo, Escocia. 21 de julio de 2022. Consultado el 21 de julio de 2022 .
- ^ Hall, JAJ; McKinnon, KIM (1 de diciembre de 2005). "Hiperesparcimiento en el método Simplex revisado y cómo explotarlo" (PDF) . Optimización computacional y aplicaciones . 32 (3): 259– 283. doi :10.1007/s10589-005-4802-0. ISSN 1573-2894. S2CID 15967632 . Consultado el 1 de abril de 2022 . El PDF vinculado es una preimpresión preliminar.
- ^ Huangfu, Q; Hall, JAJ (abril de 2015). "Nuevas técnicas de actualización para el método simplex revisado" (PDF) . Optimización computacional y aplicaciones . 60 (3): 587– 608. doi :10.1007/s10589-014-9689-1. ISSN 0926-6003. S2CID 254416722 . Consultado el 31 de marzo de 2022 .
- ^ Huangfu, Q; Hall, JAJ (1 de marzo de 2018). "Paralelización del método simplex dual revisado" (PDF) . Mathematical Programming Computation . 10 (1): 119– 142. doi :10.1007/s12532-017-0130-5. ISSN 1867-2957. S2CID 4641325 . Consultado el 27 de febrero de 2022 .
- ^ "Benchmark of Simplex LP solvers". Árbol de decisiones para software de optimización . Marzo de 2022. Archivado desde el original el 11 de noviembre de 2021. Consultado el 31 de marzo de 2022 .
- ^ Schork, Lukas; Gondzio, Jacek (diciembre de 2020). "Implementación de un método de punto interior con preacondicionamiento de base" (PDF) . Mathematical Programming Computation . 12 (4): 603– 635. doi :10.1007/s12532-020-00181-8. hdl :20.500.11820/00a692a1-3372-41f6-8baf-f45396efcc0e. ISSN 1867-2949. S2CID 53444331 . Consultado el 31 de marzo de 2022 .
- ^ "Benchmark of Barrier LP solvers". Árbol de decisiones para software de optimización . Marzo de 2022. Consultado el 31 de marzo de 2022 .
- ^ "Las instancias de referencia MIPLIB2017". Árbol de decisiones para software de optimización . Marzo de 2022. Consultado el 31 de marzo de 2022 .
- ^ "SciPy — scipy.optimize.linprog". Optimización de SciPy . Marzo de 2022. Consultado el 1 de abril de 2022 .
- ^ "SciPy — Aspectos destacados de la versión 1.6.0". Optimización de SciPy . Marzo de 2022 . Consultado el 2 de abril de 2022 .
- ^ "SciPy — Aspectos destacados de la versión 1.9.0". Optimización de SciPy . Mayo de 2022 . Consultado el 5 de mayo de 2022 .
- ^ "JuMP". JuMP . Marzo de 2022 . Consultado el 1 de abril de 2022 .
- ^ "JuMP — Modelos". JuMP . Marzo de 2022 . Consultado el 1 de abril de 2022 .
- ^ "NAG Library Manual, Mark 29.3". Suite de modelado de optimización de NAG . Enero de 2024. Consultado el 25 de marzo de 2024 .
- ^ "Notas de la versión de Optimization Toolbox". Mathworks Optimization Toolbox . Marzo de 2024 . Consultado el 22 de marzo de 2024 .
- ^ Brown, Tom. «Servidor de optimización PyPSA-Eur-Sec» . Consultado el 22 de julio de 2022 . Una interfaz web para el modelo PyPsa‑Eur‑Sec.
- ^ "Commit de GitHub: Cambiar el solucionador de Gurobi a HiGHS". Proyecto de servidor PyPSA . 3 de febrero de 2022 . Consultado el 22 de julio de 2022 .
- ^ "Commit de GitHub: Se agregaron valores altos para Linux". Proyecto GridCal . 3 de febrero de 2022 . Consultado el 24 de julio de 2022 .
