설명

과제는 다양한 크기의 종이 제품을 잘라내는 것입니다.
고객의 주문을 충족하기 위해 대형 원시 종이 롤. 목표
필요한 롤 용지 수를 최소화하는 것입니다.

CG 방식은 BCH를 이용하여 구현된다. 실행 중인 LP 솔버 호출
BCH 가격 책정 호출로 전환하여 새 열을 제공합니다.

소형 모델 유형 :MIP

메인 파일 : bchstock.gms

$title 절단 스톡 - BCH를 사용한 열 생성 접근 방식(BCHSTOCK,SEQ=349)

$onText
임무는 다양한 크기의 종이 제품을 잘라내는 것입니다.
고객의 주문을 충족하기 위해 대형 원시 종이 롤. 목표
필요한 롤 용지 수를 최소화하는 것입니다.

CG 방식은 BCH를 이용하여 구현된다. 실행 중인 LP 솔버 호출
BCH 가격 책정 호출에 참여하고 새 열을 제공합니다.

P. C. Gilmore 및 R. E. Gomory, 선형 계획법에 대한 접근 방식
절단 재고 문제, 1부, Operations Research 9(1961), 849-859.

P. C. Gilmore 및 R. E. Gomory, 선형 계획법에 대한 접근 방식
절단 재고 문제, 2부, Operations Research 11(1963), 863-888.

키워드: 혼합 정수 선형 계획법, 재고 절단, 열 생성,
          분기 및 절단 및 휴리스틱 시설, 제지 산업
$offText

$eolCom //

세트
   나는 '너비' / w1*w4 /
   p '패턴' / p1*p10 /;

매개변수
   r '원시 너비' / 100 /
   w(i) '너비' / w1 45, w2 36, w3 31, w4 14 /
   d(i) '수요' / w1 97, w2 610, w3 395, w4 211 /
   aip(i,p) 'p에서 성장하는 패턴의 너비 i 수';

* 마스터 모델
변수
   xp(p) '사용된 패턴'
   z '객관변수';

정수 변수 xp;
xp.up(p) = sum(i, d(i));

방정식
   numpat '사용된 패턴 수'
   수요(i) '수요 충족';

numpat..sum(p, xp(p)) =e= z;

수요(i).. sum(p, aip(i,p)*xp(p)) =g= d(i);

모델 마스터 / numpat, 수요 /;

* 초기화 - 초기 패턴은 단일 너비를 갖습니다.
aip(i,p)$(ord(i) = ord(p)) = Floor(r/w(i));

$echo userpricingcall Pricing.gms > cplex.opt

Execute_unload '데이터', i, w, d, r;
z.lo = 0; // 지금은 재구성을 방지해야 합니다.

옵션 rmip = cplex, optCr = 0; master.opt파일 = 1;

z를 최소화하는 rmip를 사용하여 마스터를 해결합니다.

* 추가 열을 다시 읽어보세요.
세트
   열 '열' / 1*1000 /
   cc(cols) '새 열'
   info '열 정보' / 레벨, 하위, 상위 /;

매개변수
   Demand_c(cols,i) '생성된 패턴'
   col_info(열, 정보);

Execute_load 'bchsol.gdx', col_info, Demand_c;

옵션 참조 < col_info;

* aip 데이터를 새로운 패턴으로 채웁니다.
loop((cc(cols),p)$(ord(cols) = ord(p) - 카드(i)), aip(i,p) = Demand_c(cols,i));

master.opt파일 = 0;

z를 최소화하는 mip를 사용하여 마스터를 해결합니다.

abort$(master.modelStat <> 1 or abs(z.l - 453) > 1e-6) '잘못된 해결 방법';

$onEchoV > 가격.gms
i를 설정합니다.

매개변수 w(i), d(i), r;

$gdxIn 데이터
$load 나는 w d r

방정식 수요(i);

$gdxIn bchout
$load 수요

* 가격 문제 - 배낭형 모델
변수
   지
   y(i) '새 패턴';

정수 변수 y;
y.up(i) = ceil(r/w(i));

방정식 defobj, 배낭;

defobj.. z =e= 1 - sum(i, 수요.m(i)*y(i));

배낭.. sum(i, w(i)*y(i)) =l= r;

모델 가격 / defobj, 배낭 /;

옵션 optCr = 0;

z를 최소화하는 mip를 사용하여 가격 책정을 해결합니다.

CC / 1 / 설정;
매개변수
   numcols '생성된 열 수' / 0 /
* 레벨, 하위, 상위, 유형: 0 cont, 1 bin, 2 int, 3 semicont, 4 semiint
   col_info(cc,*) '열 정보'
   numpat_c(cc), Demand_c(cc,i) '행렬 항목';

* 마스터 모델을 개선할 수 있는 패턴을 찾았나요?
if(z.l < -0.001,
   numcols = numcols + 1;
   numpat_c(cc) = 1;
   수요_c(cc,i) = round(y.l(i));
   col_info(cc,'lower') = 0;
   col_info(cc,'upper') = smax(i$demand_c(cc,i), d(i)/demand_c(cc,i));
   col_info(cc,'유형') = 2;
);
$offEcho