석박사/최적화는 사기가 아니얏! (12) 썸네일형 리스트형 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, HGS 대부분의 전문가들의 LKH (링컨핸휴리스틱)는 popular 한 적당히 좋은 솔버라 생각함. http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3_REPORT.pdf http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3 (Keld Helsgaun)LKH-3 is an extension of LKH-2 for solving constrained traveling salesman and vehicle routing problems. The extension has been desribed in the report Extensive testing on benchmark instances from the literature has sho.. 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 이전 1 2 3 다음
