trnspwlx.gms : 조각별 선형 함수의 전송 문제

설명

이 문제는 다음을 충족하는 최소 비용 배송 일정을 찾습니다.
시장의 요구사항과 공장의 공급품. 이 인스턴스
규모의 경제를 적용하여 볼록하지 않은 결과를 얻습니다.
목표. 이는 슬롯의 trnsport 모델의 확장입니다.
모델 라이브러리.

원래의 비선형 항은 "sum((i,j), c(i,j)*sqrt(x(i,j)))"입니다. 우리
sqrt(x)의 다음 이산화 f(x)를 사용합니다.

  x <= 50인 경우: f(x) = 1/sqrt(50)*x,
  x >= 400의 경우: f(x) = 1/(2*sqrt(400))*(x-400) + sqrt(400)
  그 사이에 점 사이의 선형 보간으로 이산화합니다.

모델은 다음과 같이 구성됩니다.
  1) NLP 솔버의 시작점을 설정하여 중단되도록 합니다.
     전역 최적이 아닌 지역 최적이 됩니다.

  2) 조각별 선형을 얻기 위해 일반 pwlfunc.inc batinclude를 사용합니다.
     MIP 공식화는 전역 최적에 가까워집니다.

  3) 이산화된 해로부터 비볼록 NLP를 다시 시작합니다.
     모델을 만들고 NLP 솔버가 전역 솔루션을 찾길 바랍니다.

이 모델은 슬롯 모델 라이브러리의 모델 trnspwl을 기반으로 합니다.

대형 모델 유형 :MIP

카테고리 : 슬롯 모델 라이브러리

메인 파일 : trnspwlx.gms   포함: pwlfunc.inc

$title 조각 선형 함수의 운송 문제(TRNSPWLX,SEQ=386)

$onText
이 문제는 다음을 충족하는 최소 비용 배송 일정을 찾습니다.
시장의 요구사항과 공장의 공급품. 이 인스턴스
규모의 경제를 적용하여 볼록하지 않은 결과를 얻습니다.
목표. 이는 슬롯의 trnsport 모델의 확장입니다.
모델 라이브러리.

원래의 비선형 항은 "sum((i,j), c(i,j)*sqrt(x(i,j)))"입니다. 우리
sqrt(x)의 다음 이산화 f(x)를 사용합니다.

  x <= 50인 경우: f(x) = 1/sqrt(50)*x,
  x >= 400의 경우: f(x) = 1/(2*sqrt(400))*(x-400) + sqrt(400)
  그 사이에 점 사이의 선형 보간으로 이산화합니다.

모델은 다음과 같이 구성됩니다.
  1) NLP 솔버의 시작점을 설정하여 중단되도록 합니다.
     전역 최적이 아닌 지역 최적이 됩니다.

  2) 조각별 선형을 얻기 위해 일반 pwlfunc.inc batinclude를 사용합니다.
     MIP 공식화는 전역 최적에 가까워집니다.

  3) 이산화된 해로부터 비볼록 NLP를 다시 시작합니다.
     모델을 만들고 NLP 솔버가 전역 솔루션을 찾길 바랍니다.

이 모델은 슬롯 모델 라이브러리의 trnspwl 모델을 기반으로 합니다.

Dantzig, GB, 3.3장. 선형 프로그래밍 및 확장.
프린스턴 대학 출판부, 뉴저지주 프린스턴, 1963년.

키워드: 선형 계획법, 운송 문제, 스케줄링, 조각별
          선형 함수, 선형 보간
$offText

세트
   i '통조림 식물' / 시애틀, 샌디에고 /
   j 'markets' / 뉴욕, 시카고, 토피카 /;

매개변수
   a(i) '경우에 따라 식물 i의 용량'
        /시애틀 350
          샌디에이고 600 /

   b(j) '경우에 따라 시장 j의 수요'
        / 뉴욕 325
          시카고 300
          토피카 275 /;

테이블 d(i,j) '거리(천 마일)'
              뉴욕 시카고 토피카
   시애틀 2.5 1.7 1.8
   샌디에고 2.5 1.8 1.4;

스칼라 f '1,000마일당 케이스당 운임(달러)' / 90 /;

매개변수 c(i,j) '케이스당 운송 비용(단위: 수천 달러)';
c(i,j) = f*d(i,j)/1000;

변수
   x(i,j) '케이스의 선적 수량'
   z '총 운송 비용(천 달러)';

양수 변수 x;

* 모델 인덱스를 제한하는 방법 시연
ij(i,j);ij(i,j) = yes로 설정합니다.

방정식
   비용 '규모의 경제로 목적 함수를 정의'
   Supply(i) '공장 i의 공급 제한을 준수합니다.'
   수요(j) '시장 j의 수요를 충족';

비용.. z =e= sum(ij(i,j), c(i,j)*sqrt(x(i,j)));

공급(i).. sum(ij(i,j), x(i,j)) =l= a(i);

수요(j).. sum(ij(i,j), x(i,j)) =g= b(j);

모델 운송 / 모두 /;

* 전역적으로 최적이 아닌 로컬 솔루션에서 로컬 NLP 솔버를 시작합니다.
x.l('시애틀','시카고') = 25;
x.l('시애틀','토피카') = 275;
x.l('샌디에고','뉴욕') = 325;
x.l('샌디에고','시카고') = 275;

옵션 nlp = conopt;

z를 최소화하는 nlp를 사용하여 전송을 해결합니다.

* 첫 번째 모델(공식 a)은 조각별 선형을 구현합니다.
* 인접 점의 볼록 결합을 기반으로 한 근사치
* 시작 부분에 무한한 세그먼트가 있는 SOS2 변수를 사용하고
* 이산화의 끝

세트
   s '세그먼트' / s0*s6 /
   sl '세그먼트 라벨' / x, y '좌표', l '길이', g '기울기' /;

테이블 sqrtp(s,sl) 'sqrt에 대한 조각별 선형 함수'
         xylg
   s0 50 [sqrt(50)] -inf [sqrt(50)/50]
   s1 50 [sqrt( 50)] 70 [(sqrt(120)-sqrt( 50))/70]
   s2 120 [sqrt(120)] 70 [(sqrt(190)-sqrt(120))/70]
   s3 190 [sqrt(190)] 70 [(sqrt(260)-sqrt(190))/70]
   s4 260 [sqrt(260)] 70 [(sqrt(330)-sqrt(260))/70]
   s5 330 [sqrt(330)] 70 [(sqrt(400)-sqrt(330))/70]
   s6 400 [sqrt(400)] +inf [1/(2*sqrt(400))];

$onText
다음 batinclude에는 첫 번째 인수로 매개변수 p가 있습니다.
조각별 선형 함수의 세그먼트를 정의합니다. 시작점 (x,y)
세그먼트와 길이 및 경사가 제공되어야 합니다.
매개변수. 실제 라벨은 바틴클루드에도 제공됩니다.
세그먼트 세트(인수 2)와 함께 호출(인수 3-6) 및
여러 항목을 정의하기 위해 색인화된 매개변수를 정의하는 선택적 색인 세트(idxp)
조각별 선형 함수(arg 7). 선택적 인수 8과 9는 다음을 허용합니다.
다른 내생 인수(idxm)를 사용하여 동일한 함수 f를 사용합니다.

batinclude는 활성 세그먼트 p_Seg(s)의 하위 집합을 제공합니다.
매개변수에는 batinclude 호출 이전에 데이터가 있어야 합니다. 바틴클루드는 또한
몇 가지 매크로를 제공합니다.
1) p_Func(x[,idxp])는 x 지점에서 함수를 평가합니다.
2) x(idxm) 값을 할당하는 p_x([idxp][,idxm]) 표현식
3) y(idxm) 값을 할당하는 p_y([idxp][,idxm]) 표현식

pwlfunc.inc의 헤더에는 그 사용법이 더 자세히 설명되어 있습니다.
$offText

$batInclude pwlfunc.inc sqrtp s x y l g '' 'i,j' 'ij'

방정식 defcoplex(i,j), defobjdisc;

defcoupx(ij(i,j)).. x(i,j) =e= sqrtp_x(i,j);

defobjdisc.. z =e= sum(ij(i,j), c(i,j)*sqrtp_y(i,j));

모델 trnspwl / 공급, 수요, defobjdisc, defcoupx, %sqrtp_EquList% /;

옵션 optCr = 0;

z를 최소화하는 mip를 사용하여 trnspwl을 해결합니다.
z를 최소화하는 nlp를 사용하여 전송을 해결합니다.