유상구해기 무료~ NEOS Server 사용법~

이 보도는 15일째에 쓴 것이다.
개시하다
이 글은 수리 최적화 문제를 해결하기 위해 공개 서버인 NEOS Server[1]의 개요와 사용 방법을 설명한다.
NEOS Server란
수리 최적화 Advent Calender 2020[1]은 각종 유상, 무상의 수리 최적화 구해기를 탑재한 공개 서버다.사용자가 최적화 문제를 정의한 파일(모델 파일)을 Neos Server에 업로드하면 지정된 해결자가 서버에서 해결한 결과를 얻을 수 있습니다.업무 기밀 정보를 포함한 최적화 문제를 해결해 모델 파일을 올릴 수는 없지만 인공적으로 만들어진 문제의 예와 선행연구에서 이미 해결된 문제의 예로 Solver의 기준을 얻는 것은 편리하다.
그나저나 이전NEOS Server에는 회사가 허가증을 받지 못한 유상 Solver와 비교 실험을 해야 했고, Neos Server로 실험 결과를 요약했다.자신의 환경에서 진행된 실험과 Neos Server를 사용한 실험은 계산 환경이 다르기 때문에 엄격한 비교를 할 수 없었지만, 논문에서 Neos Server의 결과를 수치 실험의 참고값으로 활용할 수 있었던 것이 당시 큰 도움이 됐다.
다음은 구체적인 최적화 문제의 예를 들어 NEOS Server를 사용하여 결과를 얻는 일련의 절차를 설명한다.
NEOS Server 사용 단계
여기서 구체적인 예를 들어 우리는 NEOS Server를 이용하여 다음과 같은 혼합 정수 선형 최적화 문제를 해결하고자 한다(출처: [1]).
$$
\begin{align}
\text{maximize}\quad &4x_1 + 5x_2\\
\text{subject to}\quad &2x_1 +2x_2\leq 7\\
&3x_1 + 5x_2\leq 14\\
&x_1,x_2\geq 0,\\
&x_1,x_2: 정수.
\end{align}
$$
1. 구해기 선택
우선 가장 최적화된 문제를 해결하는 구해기를 결정하다.먼저 다음 페이지를 방문하십시오.
그런 다음 다음과 같은 화면이 표시됩니다.
나의 연구
이 페이지에서는 NEOS 서버에서 해결할 수 있는 최적화 문제의 종류와 각자 적용되는 구해기의 일람을 볼 수 있다.이번에 해결하고 싶은 문제는混合整数線形最適化問題입니다. 그래서 저는 상술한 페이지Mixed-integer Liner Programming의 칸을 보겠습니다.이렇게 하면 아래의 화면을 볼 수 있다.

혼합 정수 선형 최적화 문제를 풀기 위한 구해기

Cbc

CPLEX

feaspump 등

사용 가능합니다.
그럼 여기는 유상 수리 최적화 구해기 CPEX로 문제를 해결해 봅시다.CPEX 프로젝트의 경우
CPLEX [AMPL] [GAMS] [LP] [MPS] [NL]
이렇게 기재되어 있다.구해기가 수리 최적화 문제를 해결할 때 최적화 문제를 정의하는 파일을 만들고 입력해야 한다.여기[AMPL Input][GAMS Input][LP Input]...에 기재된 부분은 구해기 CPPLEX 입력에 사용할 수 있는 입력 파일 형식의 종류를 나타낸다.
가장 최적화된 문제를 정의하는 파일을 준비합니다
그러면 CPEX에서 사용할 수 있는 파일 형식을 알아봤습니다.다음은 이 문서 양식에 따라 풀고 싶은 문제를 구체적으로 기술합니다.여기서 가장 최적화된 문제를 기술하는 대표적인 형식 중 하나인 LP 형식으로 문제를 기술해 봅니다.이전 혼합 정수 선형 최적화 문제
$$
\begin{align}
\text{maximize}\quad &4x_1 + 5x_2\\
\text{subject to}\quad &2x_1 +2x_2\leq 7\\
&3x_1 + 5x_2\leq 14\\
&x_1,x_2\geq 0,\\
&x_1,x_2: 정수.
\end{align}
$$
LP 형식으로 기술하면 다음과 같다(LP 형식에 대한 구체적인 쓰기 참조 문헌[5]).

maximize
4 x(1) + 5 x(2)
subject to
c1: 2 x(1) + 2 x(2) <= 7
c2: 3 x(1) + 5 x(2) <= 14
bounds
0 <= x(1)
0 <= x(2)
general
x(1) x(2)
end

공식화와 LP 파일을 비교하면 LP 파일이 가장 최적화된 문제를 비교적 공식적으로 기술할 수 있다고 생각합니다.이렇게 기술한 문서는 example.lp로도 파일 이름을 적당히 붙여 보존한다.
Lp 파일 가져오기 및 풀기
그렇다면 실제 제작된 LP 파일을 NEOS 서버에 업로드해 CPEX로 해결하자.아까
CPLEX [AMPL] [GAMS] [LP] [MPS] [NL]
항목[LP]을 클릭합니다.다음이 표시됩니다.
모델 파일을 업로드할 페이지
이 페이지에서 LP file 부분에서 방금 만든 LP 파일을 선택하여 업로드하고 E-mail address 부분에 자신의 연락처를 입력합니다(연락처를 입력할 필요가 없습니다).그리고 Submit to NEOS를 누르면 모델 파일이 NEOS 서버에 업로드되고 CPEX의 계산이 시작됩니다.
결과를 확인하다
NEOS Server의 계산이 끝나면 브라우저에 다음 해결사의 로그가 표시됩니다.

Executing on prod-exec-5.neos-server.org

Welcome to IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 12.7.0.0
  with Simplex, Mixed Integer & Barrier Optimizers
5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5655-Y21
Copyright IBM Corp. 1988, 2016.  All Rights Reserved.

Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.

CPLEX> New value for default parallel thread count: 4
CPLEX> Problem 'cplex.lp' read.
Read time = 0.00 sec. (0.00 ticks)
CPLEX> Found incumbent of value 0.000000 after 0.00 sec. (0.00 ticks)
Tried aggregator 1 time.
MIP Presolve modified 4 coefficients.
Reduced MIP has 2 rows, 2 columns, and 4 nonzeros.
Reduced MIP has 0 binaries, 2 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.00 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 2 columns.
All rows and columns eliminated.
Presolve time = 0.00 sec. (0.00 ticks)

Root node processing (before b&c):
  Real time             =    0.00 sec. (0.01 ticks)
Parallel b&c, 4 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.00 sec. (0.01 ticks)

Solution pool: 2 solutions saved.

MIP - Integer optimal solution:  Objective =  1.4000000000e+01
Solution time =    0.00 sec.  Iterations = 0  Nodes = 0
Deterministic time = 0.01 ticks  (2.83 ticks/sec)

여기 일지에서
MIP - Integer optimal solution: Objective = 1.4000000000e+01
따라서 앞의 최적화 문제의 최적치는 14임을 알 수 있다.
또한 이 로그의 출력은 LP 파일을 올릴 때 지정한 연락처로 전송됩니다.따라서 브라우저를 닫아도 NEOS Server 결과는 메시지에 표시됩니다.
결어:기타 참조 정보
이 기사는 Neos Server를 사용하는 데 필요한 최소한의 방법에 대해 설명합니다.실제로 Neos Server를 사용하기 위해서는 해결할 최적화 문제를 미리 정해 모델 파일로 기술해야 합니다.예를 들어 혼합 정수 최적화 문제에 대한 공식은 참고 문헌[2-4]이다.또한 LP 형식의 작성법, NEOS Server의 사용법을 언급한 일본어 문헌은 문헌[5]이 있고 그 외에 블로그 글의 해설도 있다[6].
참고 문헌
[1] NEOS Server: NEOS Server for Optimization. University of Wisconsin-Madison, 2020.
[2] 등강철도.정수 계획법의 공식화 입문.경영조사 57.4(2012):190-197.
[3] 구보간웅, J.P. 페드로소, 촌송정화, A.Leis: 새로운 수리 최적화~Python 언어와 Gurobi 문제풀이~.근대 과학사.
[4] 매곡준치.잘 배우는 최적화 모델링부터 알고리즘까지.강담사.
[5] 궁대 융평.정수 계획 구해기 입문.조작 연구, 57-4(2012), pp.183-189.
[6] 섬 선생.NEOS Server: 어려운 것은 NEOS Server가 해결합니다.https://www.neos-server.org/neos/, 2020년 12월 14일 열람.