설명

이 다중 배낭 문제는 사용자가 제공한 절단 평면의 사용을 보여줍니다.
슬롯 BCH(분기 및 절단 및 휴리스틱) 시설에서. 참고로 저 표지는
이 예에 사용된 컷은 최신 MIP 솔버에 이미 구현되어 있습니다.

OR-Library에서 가져온 예http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.htmlmknap1의 첫 번째 예.

소형 모델 유형 :MIP

메인 파일 : bchmknap.gms 포함: bchcover.inc

$title BCH 기능을 사용하는 다중 배낭 문제 (BCHMKNAP,SEQ=289)

$onText
이 다중 배낭 문제는 사용자가 제공한 절단 평면의 사용을 보여줍니다.
슬롯 BCH(분기 및 절단 및 휴리스틱) 시설에서. 참고로 저 표지는
이 예에 사용된 컷은 최신 MIP 솔버에 이미 구현되어 있습니다.

OR-Library에서 가져온 예
http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html
mknap1의 첫 번째 예입니다.

Beasley, J E, OR-Library: 전자적으로 테스트 문제 배포
메일. 운영연구학회지 41(11)(1990),
1069-1072.

Petersen, C C, Balas 변형에 대한 컴퓨팅 경험
R&D 프로젝트 선정에 알고리즘을 적용합니다. 경영과학
13(9)(1967), 736-750.

Linderoth, J, IE418 - 정수 프로그래밍 강의 노트 - 강의 #15, 2005.
위스콘신 대학교 매디슨,
http://homepages.cae.wisc.edu/~linderot/classes/ie418/lecture15.pdf

키워드: 혼합 정수 선형 계획법, 배낭 문제, 분기 및 절단
          그리고 휴리스틱 시설
$offText

세트
   j '열' / c1*c6 /
   i '행' / r1*r10 /;

매개변수
   obj(j) / c1 100, c2 600, c3 1200, c4 2400, c5 500, c6 2000 /
   rhs(i) / r1 80, r2 96, r3 20, r4 36, r5 44
            r6 48, r7 10, r8 18, r9 22, r10 24 /;

테이블 a(i,j)
        c1 c2 c3 c4 c5 c6
   r1 8 12 13 64 22 41
   r2 8 12 13 75 22 41
   r3 3 6 4 18 6 4
   r4 5 10 8 32 6 12
   r5 5 13 8 42 6 20
   r6 5 13 8 48 6 20
   r7 8
   r8 3 4 8
   r9 3 2 4 8 4
   r10 3 2 4 8 8 4;

이진변수 x(j);
양의 변수 slack(i);

변수 z;

방정식 mk(i), defobj;

defobj.. z =e= sum(j, obj(j)*x(j));

mk(i).. sum(j, a(i,j)*x(j)) + slack(i) =e= rhs(i);

모델 m / 모두 /;

* 기본 데이터 내보내기
Execute_unload 'mkdata', j, i, a, rhs;

$ifThenI %system.mip% == cplex $set 솔버 cplex
$else
$abort 'MIP 솔버 %system.mip%에는 BCH 기능을 사용할 수 없습니다.'
$endIf

m.opt파일 = 1;
m.optCr = 0;

* 사용자 제공 컷 생성기를 활성화하고 모든 고급 CPLEX 옵션을 끕니다.
$onEcho > %solver%.opt
userCutCall bchcover.inc 밉 = %solver%
안 잘라
사전 0
heurFreq -1
밉간격 1
$offEcho

mip를 사용하여 m max z를 해결합니다.