HiGHS 최적화 솔버

HiGHS optimization solver
HiGHS
안정된 릴리스
1.2.2
저장소github.com/ERGO-Code/HiGHS
기입처C++
유형최적화 솔버 스위트
면허증.MIT
웹 사이트ergo-code.github.io/HiGHS
HiGHS
본사에든버러
위치
  • 영국
감독.
줄리안 홀
주요 인물
  • 이베트 갈라보바
직원
3
웹 사이트www.dev.

HiGHS는 선형 프로그래밍(LP), 혼합 정수 프로그래밍(MIP) 및 볼록 2차 프로그래밍([1]QP) 모델을 해결하기 위한 오픈 소스 소프트웨어입니다.

C++로 작성되어 MIT 라이선스로 발행된 HiGHS는 C, Python, Julia, Rust, JavaScript, Fortran 및 C#에 프로그래밍 인터페이스를 제공합니다.외부 의존관계는 없습니다.Python에 대한 편리한 얇은 포장지는 Highspy PyPI 패키지를 통해 제공됩니다.

일반적으로 싱글 스레드이지만 일부 솔버 컴포넌트는 멀티 코어 아키텍처를 이용할 수 있습니다.HiGHS는 대규모 모델을 해결하고 문제 희소성을 활용하도록 설계되었습니다.상용 소프트웨어 및 기타 오픈 소스 소프트웨어에 대한 성능은 업계 표준 [2]벤치마크를 사용하여 정기적으로 검토됩니다.

HiGHS라는 용어는 기반이 되는 프로젝트와 소프트웨어 개발을 주도하는 소규모 팀을 모두 가리킬 수도 있습니다.

역사

HiGHS는 Edinburgh 대학 수학부의 Optimization and Operational Research Group의 박사과정 학생들이 작성한 해결사를 기반으로 합니다.그 기원은 2016년 말 Ivet Galabova가 LP 프리솔브와 Julian Hall의 심플렉스 크래시 프로시저 및 Huangfu Qi의 듀얼 심플렉스 솔버를 결합하여 당시 최고의 오픈 소스 솔버보다 빠르게 산업용 LP 문제를 해결한 것으로 거슬러 올라갈 수 있습니다.그 이후로, C++ API와 다른 언어 인터페이스가 개발되었고, 모델링 유틸리티와 다른 범주의 솔버가 추가되었다.

2020년 초에 GenX 및 PyPSa 개방형 에너지 시스템 모델링 프로젝트는 독점 [4]라이브러리에 대한 지역사회 의존도를 줄이기 위해 HiGHS 해결사를 위한 자금 지원 신청을 승인했습니다.그 호소로 2022년 [5]7월 영국 캠브리지의 Invenia Labs에서 미화 76,000달러를 지원하게 되었습니다.

해결사

심플렉스

HiGHS는 Hall과 McKinnon(2005년)[6] 및 Huangfu와 Hall(2015년,[7][8] 2018년)이 기술한 기법을 바탕으로 LP 문제 해결을 위한 primal 및 dual revisioned simplex method를 구현하고 있습니다.여기에는 심플렉스 구현에서 선형 시스템을 해결할 때 하이퍼스페어리티의 이용과 듀얼 심플렉스솔러의 경우 멀티스레딩의 이용 등이 포함됩니다.상용 및 기타 오픈 소스 소프트웨어에 대한 Simplex Solver의 성능은 업계 표준 [9]벤치마크를 사용하여 정기적으로 보고됩니다.

내부점

HiGHS는 쇼크와 곤지오(2020)[10]가 기술한 기술을 바탕으로 LP 문제를 해결하기 위한 내부 포인트 방식을 구현하고 있다.LDL* 분해를 통해 직접적이지 않고 사전 조정된 공역 구배법에 의해 뉴턴 시스템을 반복적으로 해결하는 것이 주목할 만하다.내부 포인트솔버의 퍼포먼스는 상용 소프트웨어 및 기타 오픈 소스 소프트웨어와 비교하여 업계 표준 [11]벤치마크를 사용하여 정기적으로 보고됩니다.

혼합 정수 프로그래밍

HiGHS에는 MIP 문제에 대한 분기 앤 컷솔버가 있습니다.상용 소프트웨어 및 기타 오픈 소스 소프트웨어에 대한 성능은 업계 [12]표준 벤치마크를 사용하여 정기적으로 보고됩니다.

이차 프로그래밍

HiGHS에는 볼록한 2차 프로그래밍(QP) 문제에 대한 액티브한 세트솔버가 있습니다

HiGHS를 사용하는 응용 프로그램

HiGHS는 맞춤형 애플리케이션에서 독립형 솔버 라이브러리로 사용할 수 있지만 수치 컴퓨팅 환경, 최적화 프로그래밍 패키지 및 도메인별 수치 분석 프로젝트에서도 소프트웨어를 시스템에 통합하기 시작하고 있습니다.

수치 컴퓨팅 지원

현재 개발 중인 강력한 오픈 소스 소프트웨어인 HiGHS는 수치 분석을 지원하는 애플리케이션 소프트웨어 프로젝트에서 점점 더 많이 채택되고 있습니다.예를 들어 SciPy 과학 라이브러리는 릴리스 1.6.0부터 LP솔버로 HiGHS를 사용하고 릴리스 1.9.[15]0부터 개별 최적화를 위해 HiGHS MIP 솔버를 사용합니다.Julia를 위한 JuMP 모델링 언어는 HiGHS에 대한 인터페이스를 제공할 뿐만 아니라 사용자 [17]문서에서 HiGHS의 구체적인 사용 방법도 설명합니다.

오픈 에너지 시스템 모델

HiGHS는 현재 하나의 오픈 에너지 시스템 모델링 환경을 포함한 일부 도메인 고유의 애플리케이션에서도 사용되고 있습니다.PyPSa 유럽 멀티 섹터 모델의 웹 기반 버전은 2022년 [18][19]2월부터 기본적으로 HiGHS 솔버를 배포합니다.연구 지향 전력 시스템 소프트웨어를 개발하는 GridCal 프로젝트는 2022년 [20]2월에 HiGHS에 대한 선택적 지원을 추가했습니다.

「 」를 참조해 주세요.

외부 링크

레퍼런스

  1. ^ Hall, Julian (21 September 2020). HiGHS: High-performance open-source software for linear optimization (PDF). Edinburgh, United Kingdom: University of Edinburgh. Retrieved 27 February 2022. 프레젠테이션
  2. ^ "Benchmarks for optimization software". Decision tree for optimization software. March 2022. Retrieved 31 March 2022.
  3. ^ "Optimization and Operational Research: School of Mathematics". March 2022. Retrieved 31 March 2022.
  4. ^ Parzen, Maximilian; Hall, Julian; Jenkins, Jesse; Brown, Tom (31 March 2022). Optimization solvers: the missing link for a fully open-source energy system modelling ecosystem (PDF). doi:10.5281/zenodo.6409432. Retrieved 3 April 2022. 비교적 상세한 로드맵을 제공하는 8페이지에 걸친 자금 지원 제안서.open access
  5. ^ "A $76k donation from Invenia Labs has been received to support HiGHS". School of Mathematics, Edinburgh University. Edinburgh, Scotland. 21 July 2022. Retrieved 21 July 2022.
  6. ^ Hall, JAJ; McKinnon, KIM (1 December 2005). "Hyper-sparsity in the revised Simplex method and how to exploit it" (PDF). Computational Optimization and Applications. 32 (3): 259–283. doi:10.1007/s10589-005-4802-0. ISSN 1573-2894. S2CID 15967632. Retrieved 1 April 2022. Linked PDF는 초기 프리프린트입니다.
  7. ^ Huangfu, Q; Hall, JAJ (April 2015). "Novel update techniques for the revised simplex method" (PDF). Computational Optimization and Applications. 60 (3): 587–608. doi:10.1007/s10589-014-9689-1. ISSN 0926-6003. S2CID 254416722. Retrieved 31 March 2022.
  8. ^ Huangfu, Q; Hall, JAJ (1 March 2018). "Parallelizing the dual revised simplex method" (PDF). Mathematical Programming Computation. 10 (1): 119–142. doi:10.1007/s12532-017-0130-5. ISSN 1867-2957. S2CID 4641325. Retrieved 27 February 2022. open access
  9. ^ "Benchmark of Simplex LP solvers". Decision tree for optimization software. March 2022. Retrieved 31 March 2022.
  10. ^ Schork, Lukas; Gondzio, Jacek (December 2020). "Implementation of an interior point method with basis preconditioning" (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. Retrieved 31 March 2022.
  11. ^ "Benchmark of Barrier LP solvers". Decision tree for optimization software. March 2022. Retrieved 31 March 2022.
  12. ^ "The MIPLIB2017 Benchmark Instances". Decision tree for optimization software. March 2022. Retrieved 31 March 2022.
  13. ^ "SciPy — scipy.optimize.linprog". SciPy Optimization. March 2022. Retrieved 1 April 2022.
  14. ^ "SciPy — Release 1.6.0 Highlights". SciPy Optimization. March 2022. Retrieved 2 April 2022.
  15. ^ "SciPy — Release 1.9.0 Highlights". SciPy Optimization. May 2022. Retrieved 5 May 2022.
  16. ^ "JuMP". JuMP. March 2022. Retrieved 1 April 2022.
  17. ^ "JuMP — Models". JuMP. March 2022. Retrieved 1 April 2022.
  18. ^ Brown, Tom. "PyPSA-Eur-Sec optimization server". Retrieved 22 July 2022. PyPsa-Eur-Sec 모델에 대한 웹 인터페이스입니다.
  19. ^ "GitHub commit: Switch solver from Gurobi to HiGHS". PyPSA server project. 3 February 2022. Retrieved 22 July 2022.
  20. ^ "GitHub commit: Added Highs for linux". GridCal project. 3 February 2022. Retrieved 24 July 2022.