Gurobi Constraint Matrix Format 으로 작성하기
Gurobi 코드를 어떻게 작성하느냐에 따라서 연산 시간이 달라진다는 것을 예전부터 들어서 알고 있었다. 가능한 원인을 조금 더 자세히 살펴보자면..
1. Model 을 불러오는데 시간이 오래 걸리는 경우
2. Solution 을 찾는데 시간이 오래 걸리는 경우
이다.
전자의 경우에는 변수 이름을 다 생략해버리고 variables 이나 constraints 를 구성하기 위한 for 문을 잘 설계함으로써 (불필요한 iteration 을 피할 수 있게 함으로써) 줄일 수 있다.
나는 두번째 경우에 초점을 맞춰서 포스팅을 해볼까 한다. MILP 를 다룰 것이고 제목에서 언급했듯 제약식을 한줄한줄 hard coding 하는게 아니라 matrix form 에 맞춰서 구현하면 성능이 얼마나 좋아질지를 다뤄볼 것이다.
Term based modeling vs Matrice based modeling
Term based modeling 과 Matrices based modeling 을 비교하며 소개한다. 해당 레퍼런스에 들어가보면 Matrix variable 을 의미하는 MVars 를 정의하고 이를 linear quadratic constraints 로 반영하는 것을 소개하고 있다.
Naive approach, 조금 더 똑똑한 솔루션, MVar 을 이용했을때의 연산 시간을 비교해놓았는데, 확연히 다른 것을 볼 수 있다.
더 빠른 이유는 Sparse matrices 구조가 매우 흔하고 이러한 data structure 를 더 잘 활용할 수 있기 때문이다.
또한 연산을 벡터화 함으로써 복잡한 연산을 한번에 해낼 수 있다.
MVar, MConstr, MQConstr 오브젝트
다음은 그루비 공식 문서를 읽고 핵심 내용을 간추려보았다.
MVar 이란 Gurobi 변수를 NumPy ndarray 처럼 정의한 것이다. 실제 많은 성질이 numpy ndarray 에 기반하기 때문에 공식 문서를 참고할 것을 권장한다.
다음과 같은 Linear & Quadratic matrix operation 이 가능하다.
expr1 = A @ x
expr2 = A @ x + B @ y + z
expr3 = x @ A @ x + y @ B @ y여기서 A나 B 가 ndarray 나 Scipy.sparse 로 정의될 수가 있다.
공식문서를 참고해 파악한 내용은 다음과 같다.
- A와 x는 최소 한개의 dimension 은 가져야한다.
- inner-most dimension 은 일치해야 한다.
여기까지 공부하고 코딩에 성공했는데 혹시나 헤매는 사람들을 위해 github 링크를 걸어두겠다 (to be updated)