석박사/최적화는 사기가 아니얏! (11) 썸네일형 리스트형 Gurobi 로그 파일 시각화 (log file visualization) Gurobi 로그 파일을 보면 대강 이렇게 생겼다. 저 노드정보에 있는 Gap 이랑 Time 을 시각화하고 싶었는데 은근 파싱하기가 까다로웠다. 이렇게 어려울리 없어! 하고 찾아낸게 다음 라이브러리. https://github.com/Gurobi/gurobi-logtools GitHub - Gurobi/gurobi-logtools: Extract and visualize information from Gurobi log files Extract and visualize information from Gurobi log files - GitHub - Gurobi/gurobi-logtools: Extract and visualize information from Gurobi log files github.c.. Gurobi Constraint Matrix Format 으로 작성하기 Gurobi 코드를 어떻게 작성하느냐에 따라서 연산 시간이 달라진다는 것을 예전부터 들어서 알고 있었다. 가능한 원인을 조금 더 자세히 살펴보자면.. 1. Model 을 불러오는데 시간이 오래 걸리는 경우 2. Solution 을 찾는데 시간이 오래 걸리는 경우 이다. 전자의 경우에는 변수 이름을 다 생략해버리고 variables 이나 constraints 를 구성하기 위한 for 문을 잘 설계함으로써 (불필요한 iteration 을 피할 수 있게 함으로써) 줄일 수 있다. 나는 두번째 경우에 초점을 맞춰서 포스팅을 해볼까 한다. MILP 를 다룰 것이고 제목에서 언급했듯 제약식을 한줄한줄 hard coding 하는게 아니라 matrix form 에 맞춰서 구현하면 성능이 얼마나 좋아질지를 다뤄볼 것이다.. Operations Research Cheat Sheet Technical Interview This is a cheat sheet in operations research for preparing technical interviews. We will skim through the types of Mathematical Program that is commonly used and the solution techniques for the programing. Types of Mathematical Program¶ Objective function Constraints Variable Solution approach Linear Program Linear Linear real Simplex method Mixed Integer Linear Program Linear Linear integer & r.. nonlinear convex optimization을 푸는 CVXOPT 솔버 https://cvxopt.org/userguide/solvers.html Nonlinear Convex Optimization — CVXOPT User's Guide F(x), with x a dense real matrix of size (, 1), returns a tuple (f, Df). f is a dense real matrix of size (, 1), with f[k] equal to . (If is zero, f can also be returned as a number.) Df is a dense or sparse real matrix of size ( + 1, ) with Df[k,:] equal cvxopt.org nonlinear convex optimization 문제를 위한 .. VRP state-of-the-art solver - LKH 대부분의 전문가들의 LKH (링컨핸휴리스틱)가 state-of-the-art 라는데에 동의함 http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3_REPORT.pdf http://webhotel4.ruc.dk/~keld/research/LKH-3/ Column Generation 과 Dantzig-Wolfe Decomposition Column Generation 을 한 문장으로 정의하면? Column generation은 많은 수의 변수 (제약식의 수 보다 변수의 수가 훨씬 클때)를 다뤄야하는 LP/ILP 문제를 풀기 위한 알고리즘이다. 왜 "Column" Generation 이라 부르는가? Column generation 은 변수의 개수가 많은 linear programming (LP) 를 다룰때 사용하기 적절한 방법이다. 대표적인 LP 문제를 써보면 아래와 같이 쓸 수 있다. Constraints 를 표현하는 행렬 A 가 m by n 형태라고 할때 우리는 n 은 변수의 개수를 의미하고 m 은 제약식의 개수를 의미한다 (무슨 의미인지 모르겠다면 LP 의 기초를 먼저 공부하자). 이때 A 의 입장에서 다시 서술해보면 n (변수) .. [Gurobi] big-M constraint 가 일으킬 수 있는 문제 big-M constraint 은 gurobi 를 포함한 많은 최적화 솔버에서 해의 불안정성 (instability) 문제를 일으킨다. 우선 아래 예시를 통해 big-M constraint 가 무엇인지부터 살펴보자. y는 도로를 사용할지 말지 결정하는 binary variable 이고 10^6은 도로의 용량을 나타내며 x는 차량의 통행량이라고 해보자. 첫번째 수식을 살펴보면 y=0이면 x ILP 문제를 푸는 exact method (cutting plane, branch-and-bound, branch-and-cut) ILP in practice ILP는 np hard 이기 때문에 이론적으로 optimal solution 을 구할 수 있을 것이라 기대할 수 없다. 하지만 현실에서 많은 경우 ILP 솔버가 최적해를 준다. 이는 ILP 의 정확해를 찾아주는 Exact algorithm 이 많이 발전했기 때문이다. 아주 나이브하게 생각해보면 ILP 를 풀기 위한 첫걸음으로 LP relaxation 을 생각해볼 수 있다. 쉽게말해 변수가 integer 라는 제약만 없애고 LP 문제를 푸는것이다. 당연히 얻은 결과는 정수가 아니라 실수일 수 있다. 이를 정수해로 변환하기 위해 반올림을 하면 어떨까? 이렇게 구한 해는 최적해가 아닐 수 있을 뿐더러 심지어는 feasible 한 해가 아닐 수도 있다. 우리에게는 반올림 보다는 조금.. 이전 1 2 다음
