이 제약 프로그래밍 문제를 해결할 수 있는 알고리즘은 무엇입니까?
https://stackoverflow.com/questions/1251079
-
12-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 직업 가식 문제를 해결해야 하며 이 문제를 해결하기 위해 바람직하게는 효율적인 알고리즘을 찾고 싶습니다.
여러 종류의 작업을 수행할 수 있는 작업자가 있다고 가정해 보겠습니다.또한 매주 완료해야 하는 작업 풀도 있습니다.각 작업에는 시간이 걸립니다.각 작업은 누군가가 수행해야 합니다.각 근로자는 주당 N시간에서 P시간까지 일해야 합니다.
문제의 첫 번째 부분은 제약 프로그래밍 알고리즘의 좋은 후보인 것 같습니다.
그러나 여기에 복잡한 문제가 있습니다.작업자는 다양한 작업을 수행할 수 있기 때문에 선호 사항(또는 희망 사항)도 있을 수 있습니다.모든 사람의 모든 소망을 충족시키려면 문제에 대한 해결책이 없습니다(제약 사항이 너무 많음).
그래서 이 문제를 해결하려면 알고리즘이 필요합니다.완벽한 바퀴가 이미 존재한다면 나는 바퀴를 재발명하고 싶지 않습니다.
알고리즘은 공정해야 합니다(이 단어를 정의할 수 있는 경우). 예를 들어 "사람당 최소한 하나의 소원을 충족시키려고 노력하십시오"와 같은 제약 조건을 추가할 수 있어야 합니다.이 문제가 여기에 설명된 Constraint Hierarchies 방법으로 해결될 수 있는지 확신할 수 없습니다. 제약 계층.사실 나는 "공정성"과 희망 사항이 이 알고리즘 범주에 대한 유효한 제약 조건으로 표현될 수 있는지 확신하지 못합니다.
나에게 조언을 해줄 제약 프로그래밍 전문가가 있나요?효율적인 CP 알고리즘을 사용하는 대신 몇 가지 경험적 방법을 사용하여 새로운 휠을 개발해야 합니까?
감사해요 !
해결책
귀하의 문제는 일반적인 솔루션이 아마도 공식화해야 할 정도로 복잡합니다. 선형-인트거 문제. 반면에 특정 요구 사항을 완화 할 수 있다면 더 간단한 접근 방식을 사용할 수 있습니다. 예를 들어, 양파자 일치 여러 근로자를 여러 작업으로 예약 할 수 있으며 선호도를 처리 할 수도 있지만 일반적인 '공정성'제약을 시행 할 수는 없습니다. 예를 들어 이것을 참조하십시오 관련 질문. 정점 색칠 작업 분리 제약을 시행하기위한 효율적인 알고리즘이 있습니다.
다른 포스터가 언급했습니다 단순성 그리고 직업 상점 일정. Simplex는 최적화 알고리즘입니다. 일부 객관적인 기능을 최대화하려는 솔루션 공간을 통과합니다. 객관적인 기능을 공식화하는 것은 확실히 수행 될 수 있지만 사소한 일입니다. 이당 일치와 같은 고전적인 구인 일정은 문제의 일부 측면을 모델링 할 수 있지만 전부는 아닙니다. 예를 들어 우선 순위 제약이 없습니다. 예를 들어 작업에 시간 경과를 배치하는 등 일부 제약 조건을 처리 할 수있는 확장 버전이 있습니다.
기존 구현에 관심이 있다면 Python 네트워크 라이브러리는 구현이 있습니다 이 일치 알고리즘. 관심있는 오픈 소스 시간표 프로그램의 예는 다음과 같습니다. tablix.
다른 팁
제약 프로그램 형태로 간주 될 수있는 시간표를 수행했습니다. 당신은 단단한 (불가능한) 제약 조건과 소프트 제약 조건 (예 : 간격 환경 설정)이 있습니다.
선형 정수 프로그래밍은 일반적으로 30 개가 넘는 변수 후에 쓸모가 없으며 이는 단순에 대해서도 말할 수 있습니다.
솔루션이 발견 된 것은 휴리스틱 알고리즘의 트로프 도메인-특이 적 최적화였다.
사용 된 휴리스틱 알고리즘은이었다 심화 된 어닐링, 유전자 알고리즘, Metaheuristic 알고리즘 및 유사하지만 결국 최상의 결과는 "지능형"도메인에 의해 제공되었습니다. 욕심 많은 검색 연산.
기본적으로 여기에서 휴리스틱 중 하나를 사용하여 괜찮은 결과를 얻을 수 있지만 문제가 과도하게 구속 될 때 주된 문제는 식별 할 수 있습니다.
연구를위한 훌륭한 오픈 소스 도구는입니다 휴리스틱 랩.
나는 여기에 제안된 내용에 동의합니다.그러나 매우 큰 크기(변수 30개를 훨씬 초과!)의 MIP(혼합 정수 프로그래밍 문제)는 요즘 상용 코드(Xpress, Cplex, Gurobi) 또는 오픈 소스(Coin-Or/Cbc) 덕분에 실질적으로 해결됩니다.또한 OPL Studio, GAMS, AMPL, Flop과 같은 멋진 모델링 언어도 있습니다.API를 사용하는 대신 쉽게 수학적 모델을 작성할 수 있습니다.
NEOS 서버(http://neos.mcs.anl.gov/neos/solvers/index.html) 매우 다양한 MIP를 사용해 볼 수 있습니다.AMPL 형식으로 모델을 보냅니다.AMPL은 무료 제한 버전으로 제공되지만 NEOS는 무제한 인스턴스를 처리할 수 있습니다.
모델링 언어는 CP(COMET/OPL Studio) 및 로컬 검색(COMET)에도 존재합니다.
제 웹사이트 www.rostudel.com('연락처' 페이지)을 통해 언제든지 저에게 연락해주세요.
데이비드
이것은 것 같습니다 직업 상점 일정.
