AI 기반 운영 연구로 "리소그래피 기계"를 최적화합니다! 중국 과학 기술 대학 등은 수학적 프로그래밍 해결의 효율성을 크게 향상시키기 위해 계층적 시퀀스 모델을 제안했습니다.

수학 프로그래밍 솔버는 중요성과 다양성으로 인해 운영 연구 및 최적화 분야에서 "리소그래피 기계"로 알려져 있습니다.

그 중 MILP(혼합 정수 선형 계획법)는 수학적 프로그래밍 해결사의 핵심 구성 요소로, 산업 생산 일정 관리, 물류 일정 관리, 칩 설계, 경로 계획, 금융 투자, 등 주요 분야.

최근 중국 과학기술대학교 MIRA 연구소 왕지에 교수 팀과 화웨이 노아의 방주 연구소는 혼합 정수 선형 계획법 솔버의 해결 효율성을 크게 향상시키는 계층적 시퀀스 모델(HEM)을 공동으로 제안했습니다. 관련 결과는 ICLR 2023에 발표되었습니다.

현재 알고리즘은 Huawei의 MindSpore ModelZoo 모델 라이브러리에 통합되었으며, 관련 기술과 기능은 올해 안에 Huawei의 OptVerse AI 솔버에 통합될 예정입니다. 이 솔버는 운영 연구와 AI를 결합하여 업계의 운영 연구 최적화 한계를 극복하고 기업의 정량적 의사 결정 및 운영 개선을 지원하며 비용 절감 및 효율성 향상을 달성하는 것을 목표로 합니다!

저자 목록: Wang Zhihai*, Li Xijun*, Wang Jie**, Kuang Yufei, Yuan Mingxuan, Zeng Jia, Zhang Yongdong, Wu Feng

논문 링크: https://openreview.net/ forum?id=Zob4P9bRNcK

오픈 소스 데이터 세트: https://drive.google.com/drive/folders/1LXLZ8vq3L7v00XH-Tx3U6hiTJ79sCzxY?usp=sharing

PyTorch 버전 오픈 소스 코드: https://github.com/MIRALab -USTC/L2O-HEM- Torch

MindSpore 버전 오픈 소스 코드: https://gitee.com/mindspore/models/tree/master/research/l2o/hem-learning-to-cut

Tianchou(OptVerse) AI 솔버: https://www.huaweicloud.com/product/modelarts/optverse.html

그림 1. HEM과 솔버 기본 전략(기본값) 간의 해결 효율성 비교 HEM 해결 효율성은 다음을 통해 향상될 수 있습니다. 최대 47.28%

1 소개

절단면(절단)은 혼합 정수 선형 계획법 문제를 효율적으로 해결하는 데 중요합니다.

절단면 선택(컷 선택)은 MILP 해결 효율성을 높이기 위해 선택할 절단면의 적절한 하위 집합을 선택하는 것을 목표로 합니다. 절단 평면 선택은 두 가지 하위 문제, 즉 (P1) 어떤 절단 평면을 선호해야 하는지, (P2) 얼마나 많은 절단 평면을 선택해야 하는지에 크게 좌우됩니다.

많은 최신 MILP 솔버가 (P1) 및 (P2)를 수동으로 설계된 휴리스틱으로 처리하는 반면, 기계 학습 방법은 보다 효율적인 휴리스틱을 학습할 수 있는 잠재력을 가지고 있습니다.

그러나 기존의 많은 학습 기반 방법은 어떤 절단면을 우선적으로 선택해야 하는지 학습하는 데 중점을 두고 몇 개의 절단면을 선택해야 하는지 학습하는 것을 무시합니다. 또한, 우리는 많은 실험 결과를 통해 절단 평면 순서가 선호되어야 하는 또 다른 하위 문제, 즉 (P3)도 MILP 해결 효율성에 중요한 영향을 미친다는 것을 관찰했습니다.

이러한 문제를 해결하기 위해 우리는 새로운 Hierarchical Sequence Model(HEM)을 제안하고 강화 학습 프레임워크를 통해 절단면 선택 전략을 학습합니다.

우리가 아는 한, HEM은 (P1), (P2) 및 (P3)을 동시에 처리할 수 있는 최초의 학습 방법입니다. 실험에 따르면 HEM은 인위적으로 생성된 대규모 실제 MILP 데이터 세트에 대해 수동으로 설계하고 학습한 기준선에 비해 MILP 해결 효율성을 크게 향상시키는 것으로 나타났습니다.

2 배경 및 문제 소개

2.1 평면 절단(절단) 소개

혼합 정수 선형 계획법(MILP)은 공급망 관리 등 다양한 실무 응용 분야에서 널리 사용할 수 있는 일반 최적화 모델입니다. [1], 생산계획[2], 기획 및 파견[3], 공장입지 선정[4], 포장문제[5] 등

표준 MILP의 형식은 다음과 같습니다.

(1)

주어진 문제 (1)에서 모든 정수 제약 조건을 버리고 선형 프로그래밍 완화(LPR) 문제를 얻습니다. 형식은 다음과 같습니다.

(2)

문제 (2)는 문제 (1)의 실행 가능한 집합을 확장하므로 LPR 문제의 최적 값은 원래 MILP 문제 Nether라는 것을 알 수 있습니다.

(2)의 LPR 문제에서 평면 절단(절단)은 선형 계획법 완화 문제에 추가될 때 LPR 문제에서 실현 가능한 도메인 공간을 축소할 수 있는 법적 선형 부등식의 클래스입니다. 원래 MILP 문제에 대한 정수 실현 가능 솔루션입니다.

2.2 컷 선택 소개

MILP 솔버는 MILP 문제를 해결하는 과정에서 많은 수의 컷팅 평면을 생성할 수 있으며, 연속 라운드에서 원래 문제에 컷팅 평면을 계속 추가합니다.

특히 각 라운드에는 5단계가 포함됩니다.

(1) 현재 LPR 문제를 해결합니다.

(2) 선택할 일련의 절단 평면을 생성합니다.

(3) 선택할 절단 평면에서

(4) 새로운 LPR 문제를 얻기 위해 (1)의 LPR 문제에 선택된 부분 집합을 추가합니다.

(5) 새로운 LPR 문제를 기반으로 주기를 반복하고 다음 라운드에 들어갑니다.

생성된 모든 절단 평면을 LPR 문제에 추가하면 문제의 실현 가능 영역 공간이 가능한 최대 범위로 줄어들어 하한이 최대화됩니다.

그러나 너무 많은 절단 평면을 추가하면 문제에 너무 많은 제약이 발생하고 문제 해결에 필요한 계산 오버헤드가 증가하며 수치적 불안정성 문제가 발생할 수 있습니다[6,7].

따라서 연구자들은 MILP 문제 해결의 효율성을 최대한 높이기 위해 후보 절단 평면의 적절한 하위 집합을 선택하는 것을 목표로 하는 절단 평면 선택(컷 선택)을 제안했습니다. 절단 평면 선택은 혼합 정수 선형 계획법 문제를 해결하는 효율성을 향상시키는 데 중요합니다[8, 9, 10].

2.3 경험적 실험 - 절단면 추가 순서

우리는 절단면 선택을 위해 RandomAll과 RandomNV라는 두 가지 경험적 알고리즘을 설계했습니다(자세한 내용은 원본 논문 3장 참조).

그들은 모두 컷 배치를 선택한 후 선택한 컷을 MILP 문제에 무작위 순서로 추가합니다. 그림 2의 결과에서 볼 수 있듯이 동일한 절단면을 선택한 경우 선택한 절단면을 다른 순서로 추가하는 것은 솔버의 해결 효율성에 큰 영향을 미칩니다(자세한 결과 분석은 원 논문 3장 참조).

그림 2. 각 열은 솔버에서 동일한 배치의 절단 평면을 선택하고 이러한 선택된 절단 평면을 10회 다른 순서로 추가할 때 솔버의 최종 솔루션 효율성의 평균값을 나타냅니다. 열의 편차 선은 다양한 순서에 따른 솔루션 효율성의 표준 편차를 나타냅니다. 표준 편차가 클수록 솔버의 해결 효율성에 대한 순서의 영향이 커집니다.

3 방법 소개

절단면 선택 작업에서는 선택해야 할 최적의 부분 집합을 미리 얻을 수 없습니다.

그러나 솔버를 사용하여 선택한 하위 집합의 품질을 평가하고 이 평가를 학습 알고리즘에 대한 피드백으로 사용할 수 있습니다.

따라서 우리는 강화 학습(RL) 패러다임을 사용하여 시행착오를 통해 절단면 선택 전략을 학습합니다.

이 섹션에서는 제안된 RL 프레임워크에 대해 자세히 설명합니다.

먼저 MDP(Markov Decision Process)로 절단 평면 선택 작업을 모델링한 다음 제안된 계층적 시퀀스 모델(HEM)을 자세히 소개합니다. 마지막으로 HEM의 효율적인 교육을 위한 계층적 정책 그라데이션을 도출합니다. 전체 RL 프레임워크 다이어그램은 그림 3에 나와 있습니다.

그림 3. 제안된 전체 RL 프레임워크의 다이어그램. MILP 솔버를 환경으로, HEM 모델을 에이전트로 모델링합니다. 에이전트와 환경 간의 지속적인 상호 작용을 통해 훈련 데이터를 수집하고 계층적 정책 그라데이션을 사용하여 HEM 모델을 훈련합니다.

3.1 문제 모델링

상태 공간: 현재 LP 완화와 생성된 후보 컷에는 절단 평면 선택의 핵심 정보가 포함되어 있으므로 상태를 정의합니다. 여기서는 현재 LP 완화의 수학적 모델을 나타내고, 후보 절단 평면 세트를 나타내며, LP 완화의 최적 솔루션을 나타냅니다. 상태 정보를 인코딩하기 위해 정보를 기반으로 각 후보 절단 평면에 대해 13개의 특징을 설계합니다. 즉, 13차원 특징 벡터를 통해 상태 s를 표현합니다. 구체적인 내용은 원본 기사의 4장을 참조하세요.

액션 공간: 선택한 컷의 비율과 순서를 모두 고려하기 위해 액션 공간을 후보 컷 집합의 모든 순서화된 하위 집합으로 정의합니다.

보상 기능: 컷 추가가 MILP 해결에 미치는 영향을 평가하기 위해 솔루션 시간, 원시-쌍대 갭 적분 및 이중 경계 개선을 사용할 수 있습니다. 구체적인 내용은 원본 기사의 4장을 참조하세요.

전환 함수: 전환 함수는 현재 상태와 취해진 조치를 바탕으로 다음 상태를 출력합니다. 절단 평면 선택 작업의 전달 함수는 솔버에 의해 암시적으로 제공됩니다.

더 자세한 모델링 내용은 원문 4장을 참고해주세요.

3.2 정책 모델: 계층적 시퀀스 모델

그림 3과 같이 MILP 솔버를 환경으로 모델링하고 HEM을 에이전트로 모델링합니다. 읽기를 쉽게 하기 위해 방법의 동기를 단순화하고 방법 구현을 명확하게 설명하는 데 중점을 둡니다. 관심 있는 독자는 관련 세부 사항을 보려면 원본 논문의 4장을 참조하세요.

그림 3의 에이전트 모듈에서 볼 수 있듯이 HEM은 상위 정책 모델과 하위 정책 모델로 구성됩니다. 상위 레이어 모델과 하위 레이어 모델은 각각 상위 레이어 정책(policy)과 하위 레이어 정책을 학습합니다.

먼저 상위 정책은 적절한 비율을 예측하여 선택해야 할 컷 수를 학습합니다. 상태 길이가 이고 예측 비율이 이라고 가정하면 예측을 위해 선택해야 하는 컷 수는

이며, 여기서 는 반올림 함수를 나타냅니다. 우리는 을 정의합니다.

두 번째로, 하위 수준 정책은 주어진 크기의 정렬된 하위 집합을 선택하는 방법을 학습합니다. 하위 수준 정책은 로 정의할 수 있습니다. 여기서 는 상태 S와 비율 K가 주어진 행동 공간에 대한 확률 분포를 나타냅니다. 구체적으로 기본 정책을 시퀀스 대 시퀀스 모델(시퀀스 모델)로 모델링합니다.

마지막으로 컷 선택 전략은 전체 확률의 법칙, 즉

3.3 학습 방법: 계층적 전략 구배

최적화 목적 함수를 고려하여

그림 4 . 계층적 전략 그라데이션. 우리는 확률적 경사 하강 방식으로 HEM 모델을 최적화합니다.

4 실험 소개

실험은 다섯 가지 주요 부분으로 구성됩니다.

실험 1. 인위적으로 생성된 3가지 MILP 문제와 다양한 응용 분야의 6가지 까다로운 MILP 문제 벤치마크에 대한 방법을 평가합니다.

실험 2. 신중하게 설계된 절제 실험을 수행하여 HEM에 대한 심층적인 통찰력을 제공합니다.

실험 3. 문제 크기에 대한 HEM의 일반화 성능을 테스트합니다.

실험 4. 우리의 방법과 기준선에 따라 선택된 절단면의 특성을 시각화합니다.

실험 5. Huawei의 실제 생산 일정 문제에 우리 방법을 적용하여 HEM의 우수성을 검증합니다.

이 기사에서는 실험 1만 소개합니다. 더 많은 실험 결과를 보려면 원본 논문의 5장을 참조하세요. 우리 논문에 보고된 모든 실험 결과는 PyTorch 버전 코드를 사용한 훈련을 기반으로 얻은 결과입니다.

실험 1의 결과는 표 1에 나와 있습니다. 9개의 오픈 소스 데이터 세트에 대한 HEM과 6개의 기준선 결과를 비교했습니다. 실험 결과, HEM은 해결 효율성을 평균 약 20% 향상시킬 수 있음을 보여줍니다.

그림 5. 쉬움, 중간, 어려움 데이터 세트에 대한 전략 평가. 최적의 성능은 굵은 글씨로 표시되어 있습니다. m은 제약 조건의 평균 개수를 나타내고, n은 변수의 평균 개수를 나타냅니다. 풀이 시간과 원시-쌍대 간격 적분의 산술 평균(표준 편차)을 보여줍니다.

위 내용은 AI 기반 운영 연구로 "리소그래피 기계"를 최적화합니다! 중국 과학 기술 대학 등은 수학적 프로그래밍 해결의 효율성을 크게 향상시키기 위해 계층적 시퀀스 모델을 제안했습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!