[최적화] Google OR-Tools 최적화 오픈소스
in Data on Optimization
Google OR-Tools 에서 어떤 문제를 해결하는가 궁금해서 쓰윽 읽어봤다.
나중에 비슷한 최적화 프로젝트 있을 때 후딱 여기서 찾아서 해결하면 되겠다.
선형 최적화
- LP 문제 해결
- 뻔한 목적함수 3x+4y, 제약조건 같은거
- 고급 LP 문제 해결
- 어려운 LP 문제 솔버랑 알고리즘 선택 팁
- 영양가 계산 식단 문제
- 영양소 측면에서 일일 권장 섭취량 충족한 식단 만들기
정수 최적화
- MIP 문제
- 일부 변수를 정수로 해야하는 선형 최적화 문제를 혼합 정수 프로그램(MIP)라고 한다.
- MIP문제는 MPSolver(정수변수때 적합) 또는 CP-SAT 솔버(제약조건 프로그래밍 솔버, 변수가 불리언일때 이득)를 쓰면된다.
제약조건 최적화
- CP-SAT 솔버
- 간단한 제약조건(x!=y)
- CP 문제 해결
- 우리가 알고있는 목적함수와 제약조건으로
- 암호학
- 기호를 숫자 치환한거 맞추기
- N-퀸즈 문제
- 대각 직선 공격 불가능하게 체스판 만들기
- 해결자 제한 설정
- 시간제한으로 종료
- 솔루션 개수 종료
- 원본 CPI 솔버
- 더 좋아진 CP-SAT 솔버를 써라
할당
- 과제 문제 해결하기
- 예를들어 4개의 일을 3명한테 시킬경우 뭐가 가장 이득이냐?
- 노동자팀 배정
- 팀으로 일할경우 일 배분
- 일에 대한 크기(노력,시간)이 있는 경우
- 각 작업자의 실행할수 있는 일에 대한 총 크기 한도가 있음.
- 허용된 그룹이 있는 할당
- 특정 작업자 그룹에만 할당할수 있는 할당 문제
- 선형 합 할당 문제 해결사
- MIP 또는 CP-SAT을 써라. 옛날꺼다.
라우팅
- 여행사 영업 담당자 문제
- TSP 문제, 1개 차량 문제
- 차량 라우팅 문제
- VRP 문제, 여러차량 문제
- 용량 제약 문제
- 정전식 차량 라우팅 문제(CVRP)
- 차량에는 운송할수있는 최대 용량이 있다.
- 픽업 및 배달 문제
- 픽업과배달 주문이 있을때 차량들로 어떻게 효율적으로 보내는가
- 기간 제약 문제
- 고객의 방문 예약을 고려한 차량 경로(VRPTW)
- 크기
- 측정기준이라는 객체를 사용하는데(이동시간이나 누적수량 같은거), 이걸로 추적하면서 제약조건을 적용할수 있다.
- 여기서 Slack이 나오는데 느슨함으로 이해하면 된다.(예시가 있다)
- 리소스 제약조건
- VRPTW 문제에서 충전대에서 2대의 차량많이 차량이 로드할수 있다.
- 불이익 및 방문 감소
- 솔루션이 없는 라우팅문제
- 예를들어 용량 제약 문제에서 솔루션이 없을경우 일부경로를 삭제해야된다는거고 문제는 그걸 결정하는 방법
- 해결을 위해서는 페널티를 적용, 위치방문이 누락될때마다 이동거리 패널티 추가
- 일반적인 라우팅 작업
- 문제 해결 시간이 오래걸릴경우 검색종료 한도 설정이 좋다.
- 초기 경로 설정도 가능(왜하는지는 모르겠음)
- 이전엔 같은 창고에서 출발했다면 각 차량이 다른 시작,종료위치 설정가능
- 라우팅 옵션
- 솔루션 제한, 검색시간제한, 인접 로컬 검색 소요시간 제한
- 검색 상태(문제해결x, 해결완료, 찾을수없음, 시간제한, 플래그 잘못)
- 지역 검색 옵션(타부 같은거 써서 로컬 최솟값 등)
- 전파 제어(깊이 우선 검색 사용 등에 필요?)
- Google 경로 API
- 그냥 OR-Tools 쓰지말고 API로 간단하게 쓰면된다.
배낭에 공넣는 포장 문제
- 배낭 문제
- 부피가 다른 공을 컨테이너에 최대용량(무게)으로 넣어야한다면?
- 여러 배낭 문제
- 배낭 문제를 여러 배낭으로 효율적으로
- 배낭수까지 정하는 포장 문제
- 배낭의 개수도 안정해져있고 배낭의 개수까지 정해야할때
네트워크 흐름
- 최대 흐름
- 교통망이 노드 엣지로 되어있는 문제
- 최소 비용 흐름
- 여기 나온 예시는 20의 공급(노드0지점)-> -5, -15만큼 노드3, 4에 나눌껀데 가장 비용이 적게 보낼수 있냐 문제(네트워크가 최대용량과 비용으로 되어있음)
- 최소 비용 흐름 문제로 할당
- min_cost_flow 임포트해서 써도 좋지만 MIP, CP_SAT이 많은 종류 커버 치니까 이거써라
예약
- 직원 교대근무 문제
- 간호사 교대근무문제(8시간 단위 교대, 한명 간호사가 1개 일만 하지않고, 3일동안 두번 교대근무 해야되고)
- 기계 작업 문제
- 티, 바지, 벨트 만드는 기계가 있으면 처리시간이나, 시간이 겹치지않게해서 최소 시간으로 할수 있는지
