knapsack

배낭

배낭 문제는 잘 알려진 최적화 문제입니다. 예를 들어 선적 컨테이너를 포장할 때 발생합니다. 선적 컨테이너에는 담을 수 있는 무게 용량이 있습니다. 각 품목에 값과 무게가 있는 배송할 품목 모음이 주어지면 문제는 배송 컨테이너에 포장할 최적의 품목을 선택하는 것입니다. 이 최적화 문제는 제약 조건이 있는 목표로 정의될 수 있습니다.

• 목표: 화물 가치(선택한 품목의 가치 합계)를 최대화합니다.
• 제약조건: 총 화물 중량(선택한 품목의 중량 합계)은 컨테이너 용량보다 작거나 같아야 합니다.

이 예에서는 이러한 배낭 문제를 CQM(제약 2차 모델)로 다시 공식화하고 Leap 하이브리드 CQM 솔버에 제출하여 문제를 해결합니다.

용법

기본 데모를 실행하려면 다음 명령을 입력하십시오.

python knapsack.py

사용 가능한 옵션을 보려면 다음 명령을 입력하십시오.

python knapsack.py --help

명령줄 인수를 사용하면 여러 데이터 세트( /data 폴더 아래) 중 하나를 선택하고 화물 용량을 설정할 수 있습니다. 데이터 파일은 항목의 행으로 구성되며 각 항목은 무게와 값의 쌍으로 정의됩니다.

코드 개요

knapsack.py 의 코드에는 세 가지 주요 기능이 포함되어 있습니다.

• build_knapsack_cqm() 다음과 같이 목표와 제약 조건을 설정하여 CQM을 생성합니다.

  • 목표: 각 항목에 대해 이진 변수가 생성되고 항목 값의 음수 값과 동일한 선형 편향이 할당됩니다. 최적의 품목 세트를 선택하여 이러한 목표를 최소화하는 것은 화물의 총 가치를 최대화하는 것과 같습니다. 솔루션은 선택된 항목에 대해 1의 값을 설정하고 선택되지 않은 항목에 대해 0의 값을 설정합니다.
  • 제약 조건: 선형 편향이 각 항목의 무게와 동일하게 설정된 이전에 생성된 이진 변수를 사용하는 2차 모델은 총 무게가 컨테이너 용량을 초과해서는 안 된다는 요구 사항으로 생성됩니다.

• parse_inputs() 는 예제 파일에서 데이터를 읽는 유틸리티 함수입니다.

• parse_solution() 솔버에서 반환된 결과를 구문 분석하고 표시합니다.

특허

Apache License 2.0에 따라 출시되었습니다. 라이센스 파일을 참조하세요.