최고의 오픈 소스 혼합 정수 최적화 솔버 [폐쇄

Question

나는 거대한 최적화 모델 (100k 이상)을 해결하기 위해 CPLEX를 사용하고 있습니다. 이제 오픈 소스 대안을 찾을 수 있는지, 혼합 정수 문제 (MILP)를 해결하고 CPLEX가 훌륭하게 작동하지만 매우 비싸다면 매우 비쌉니다. 대안을 찾거나 우리 자신의 임시 최적화 라이브러리를 작성하기 시작해야합니다 (고통 스러울 것입니다).

모든 제안/통찰력은 대단히 감사 할 것입니다

Answer 1

나는 개인적으로 발견했다 glpk lp_solve보다 낫습니다 (즉, 더 빠릅니다. 다양한 파일 형식을 지원하며 추가 장점은 라이브러리 인터페이스로 응용 프로그램과 원활하게 통합 할 수 있습니다.

Answer 2

또 다른 보증 동전 또는. 우리는 선형 최적화기 구성 요소 (CLP)가 매우 강했으며 혼합 정수 구성 요소 (CBC)는 일부 분석으로 상당히 잘 조정될 수 있음을 발견했습니다. 우리는 LP-Solve 및 GLPK와 비교합니다.

정말 힘든 문제의 경우 상업용 솔버가가는 길입니다.

Answer 3

Scip 솔버를 사용해보십시오. 성능이 우수한 300k 이상의 변수로 MILP 문제에 사용했습니다. MILP 성능은 GLPK보다 훨씬 낫습니다. Gurobi는 또한 MILP 문제에 대한 탁월한 성능을 가지고 있으며 (일반적으로 SCIP (2011 년 5 월)보다 우수하지만 학업 사용자가 아닌 경우 비용이 많이들 수 있습니다. 구로비는 멀티 코어를 사용하여 솔버 속도를 높입니다.

Answer 4

당신은 시도 했습니까? lp_solve? Java에 대한 다음 질문에는 다른 제안도있었습니다.

• Java 용 수학 최적화 라이브러리- 무료 또는 오픈 소스 권장 사항?
• Java 용 선형 프로그래밍 도구/라이브러리

Answer 5

내가 당신이라면, 나는 OSI (C ++) 또는 펄프 (Python)와 같은 멀티 솔버 인터페이스를 사용하여 코드를 한 번 작성하고 많은 솔버로 테스트 할 수 있도록 노력할 것입니다.

당신이 해결하려는 정수 프로그램이 거대하다면, 나는 코드가 더 깨끗해 보이고 시간의 99%가 솔버에 소비되기 때문에 c ++를 통해 Python을 추천합니다.

• https://projects.coin-or.org/osi
• http://code.google.com/p/pulp-or/

반대로, 문제가 작 으면, Python의 메모리에서 솔버로의 문제를 복사 할 시간은 더 이상 무시되지 않아야합니다.이 경우 컴파일 된 언어를 사용하여 눈에 띄는 성능 개선을 실험 할 수 있습니다. .

그러나 문제가 압도적으로 엄청나게되면 메모리 발자국은 대략 2로 나뉘어지기 때문에 컴파일 된 언어가 다시 이길 것입니다 (파이썬의 문제의 사본은 없음).

Answer 6

코인 프로젝트를 확인하는 것이 좋습니다.동전 또는

비선형 문제에 대한 iPopt와 혼합 정수 솔버를 포함하여 많은 좋은 솔버.

Answer 7

Scip 나쁘지 않아!

Answer 8

이것은 당신이 듣고 싶은 것이 아니지만, 한편으로는 상업용 솔버 Cplex와 Gurobi 사이에 빛과 오픈 소스 솔버 사이에 빛이 있습니다.

그럼에도 불구하고 운이 좋을 수 있고 모델은 GLPK, 코인 등으로 잘 작동하지만 일반적인 오픈 소스 솔루션은 상업용 솔버 뒤에 있습니다. 그것이 다르면, 아무도 구로비 라이센스에 대해 12.000 $를 지불하지 않고 CPLEX 라이센스에 대해서는 더 많은 것을 지불하지 않습니다.

지난 몇 년 동안 나는 오픈 소스 솔버에게는 어려운 많은 모델을 보았습니다. 나를 믿어...

크기의 문제가 아니라 숫자의 어려움입니다.

Answer 9

100k 변수는 큰 문제입니다. 많은 오픈 소스 라이브러리는 많은 변수와 잘 작동하지 않습니다. 내가 읽은 내용에서 lp_solve는 약 30k 변수에 대해서만 테스트되었습니다. 상용 시스템을 사용하는 것이 유일한 선택 일 수 있습니다.

Answer 10

NEOS 서버를 사용하여 DICOPT를 사용했습니다 (http://www.neos-server.org/neos/solvers/minco:dicopt/gams.html) 큰 (약 1K 변수 및 1K 제약 조건) 혼합 정수 비선형 프로그램을 해결하기 위해 우수합니다.

내 문제의 경우 DiCopt는 NEOS 서버 Baron/Knitro/Lindo/SBB 등에 나열된 다른 MINLP 솔버보다 훨씬 더 나았습니다.

NEO에 일자리를 제출하는 데는 특정 제약이 있으며 약간 번거 롭지 만 강력한 상업용 솔버에 대한 무료 액세스는 보충하는 것보다 더 많이 액세스 할 수 있습니다.

Answer 11

이미 훌륭한 답변에 다음을 추가하겠습니다.

다른 사람들이 지적했듯이 상업용 솔버는 무료 대안보다 훨씬 빠르고 능력이 있습니다. 많은 정수 변수의 큰 문제의 경우 1% 이상의 최적 차이를 수용 할 수 있다면 훨씬 빠른 해결 시간을 얻을 수 있습니다 (기본값은 약 0.01% 이하인 경향이 있습니다).

물론 1%가 수백만 달러로 변환되는 문제를 해결한다면 이것은 허용되지 않습니다. 따라서 최고 수준의 솔버 시장입니다. (구로비와 자유 솔버와의 일부 비교 여기)

다른 솔버를 시험해 볼 수 있으므로 솔버 독립 문제 파일 (예 : *.mps, *.lp 파일)을 생성하는 플랫폼을 사용하는 것이 가치가 있다는 데 동의합니다. 사용 중입니다 펄프 그리고 그것을 찾고, 무료 coin_cbc 솔버, 우수합니다. 많은 정수 변수의 문제에 대해서는 제한적이지만.

Answer 12

아무도 MIPCL을 언급하지 않았다는 것에 놀랐습니다.http://www.mipcl-cpp.appspot.com/index.html). 이 솔버는 LGPL 라이센스에 따라 오픈 소스라고 주장합니다 (출처 : http://www.mipcl-cpp.appspot.com/licence.html) 따라서, 비 관장 소스 애플리케이션에도 사용되기에 적합합니다. 그러나 실제로 오픈 소스가되기 위해 누락 된 것은 솔버 자체의 소스 코드입니다.

Hans Mittelmann 매우 최근 (2017 년 9 월 10 일) 혼합 정수 선형 프로그래밍 벤치 마크 : http://plato.asu.edu/ftp/milpc.html (개요 페이지를보고 관심이있을 수도 있습니다. http://plato.asu.edu/bench.html 또는 그의 대화의 슬라이드 : http://plato.asu.edu/talks/informs2017.pdf).

혼합 정수에서 12 개의 스레드와 2 시간의 시간 제한이있는 MIPCL이 79 인스턴스를 해결할 수있는 혼합 된 선형 프로그래밍 벤치 마크에서. 상용 솔버 만 CPLEX, GUROBI 및 XPRESS만이 주어진 제약 조건 (각각 86 또는 87 인스턴스)에 따라 더 많은 것을 해결했습니다.

또한 선택된 성능 메트릭 (12 스레드 사용) MIPCL 측면에서 MIPCL은 벤치마킹 된 SCIP 파생물 (FSCIPC, FSCIPS) 및 오픈 소스 솔버 CBC보다 빠릅니다. 다시 상용 솔버 만 CPLEX, GUROBI 및 XPRESS OutCompete MIPCL 만 성능 측면에서 크게 중요하게 생각합니다.

Answer 13

오픈 소스는 아니지만 Microsoft Academic Alliance 라이센스가있는 경우 Microsoft Solver Foundation (MSF) Enterprise Edition이 포함되어 있습니다. 구로비 학업 목적으로도 무료이며 논문 연구에 사용했습니다.