공항근처 공역에서의 도착 비행 스케쥴 최적화

(1)

Optimal Arrival Flight Sequencing and Scheduling in a Terminal Airspace

은연주

^＊

(KAIST), 황인석(미국 퍼듀대학교), 방효충(KAIST)

1. 서 론

전 세계적으로 항공교통량 수요가 급증함에 따 라 그 동안 인력에 의존해 왔던 항공교통제어 (Air Traffic Control)를 자동화하여 날씨 변화 등의 급변하는 상황에도 최적화된 비행스케쥴을 얻으려는 노력이 계속되고 있다. 특히 Transportation Safety Board of Canada[1] 의 항공교통사고 사례 보고서들을 조사해본 결과 1995 년부터 2006 년까지 Ross of Separation, 즉 항공교통에서 충돌상황으로 인식하는 사고사 례가 약 85 건 있었으며, 이중 30% 이상이 갑자 기 증가한 업무량으로 인한 관제관의 상황인식 부족이나 관제관들 사이의 의사소통 실수, 통신 실수 등에 의한 사고로 분석되고 있다. 따라서 항공교통관제를 전면적으로 자동화하지 않더라 도 항공교통관제관들의 일 부담 (work load)을 줄이기 위한 Decision Support Tool 을 개발하 여 안정성과 효율을 높이는 것이 증가하는 항공 교통량 수요에 효과적으로 대처하는 방법이 될 것이다. 특히 공항주변의 출도착 항공기들의 비 행 스케쥴 최적화는 출도착시간 지연을 최적화 할 뿐만 아니라 공항이용 승객들에게 좀 더 정 확한 출도착 시간을 제공하여 항공사들 및 승객 들의 공항 이용 선호도를 높일 수 있다.

또한 우리나라의 경우 인천공항과 김포공항의 직선거리가 40km 에 불과하고 서울 상공 등 비 행 불가지역이 공항 주변에 산재하며, 특히 북 방한계선으로 인해 모든 항공기가 남쪽에서 공 항으로 접근해야 하는 등 공항주변의 항공관제 에 있어서 극도로 불리한 여건을 가지고 있다.

이러한 경우 비행 관제의 최적화, 자동화를 통 해 정확하고 안전한 비행스케쥴을 얻는 것이 증 가하는 항공교통량 수요 충족을 위해 필수적인

일이 될 것이다.

항공교통제어의 자동화 연구는 비행수요가 많아 전세계적으로 가장 심각한 문제를 겪고 있 는 미국에서 가장 활발하게 이루어지고 있다.

특히 NASA 의 Ames 연구소에서 주도하여 개 발하고 있는 CTAS (Center-TRACON (Terminal Radar Approach Control) Automation System)가 가장 발전된 형태의 항 공교통제어자동화 시스템으로 알려져 있으며 많 은 연구들이 이 CTAS 를 모델로 CTAS 의 각 기능별 모듈에서 해결 해야 할 문제들을 연구하 는 방향으로 이루어지고 있다. 특히 도착항공기 들의 시퀀싱 (sequencing) 및 스케쥴링은 공항 주변 공역이 밀리는 경우 항공기들이 공중대기 를 해야 하기 때문에 더욱 복잡한 문제가 되며 이러한 문제를 해결하기 위한 연구들이 이루어 져왔다. Bayen[2]와 Slater[3]는 Dynamic Programming 을 이용하여 도착항공기의 비행 스케쥴링을 최적화하였으나, 공중대기에 따른 도착지연시간이 연속변수로 고려됨에 따라 최적 화된 결과를 따르기 위해 정밀한 궤적제어가 이 뤄져야 하는 등 현재의 인력기반의 관제시스템 의 보조수단으로 사용하기 어려운 점이 있다.

뿐만 아니라 만약 이미 결정된 여러가지 비행모 드나 궤적에 따라 이용가능한 도착지연시간이 불연속적인 값으로 미리 지정되어 있고, 이러한 불연속적인 도착지연시간을 이용하여 스케쥴링 을 할 수 있으면 날씨 변화등 급변하는 상황에 좀 더 빠르게 대응할 수 있고 스케쥴링과 동시 에 대략적인 궤적이 정해짐으로써 좀 더 정밀한 스케쥴링이 가능하다. 미리 정해진 이용 가능한 도착지연시간을 이용한 스케쥴링 방법으로 유전 자알고리즘이 이용되기도 하였으나 [4~6], 유

(2)

전자알고리즘은 대표적인 휴리스틱 알고리즘으 로 최대계산시간이 얼마나 걸릴 지 알 수 없을 뿐만 아니라 구한 해가 전역최적해임을 보장할 수 없다. 본 논문에서는 수행 가능한 공중대기 비행모드를 고려하여 불연속적인 도착지연시간 을 최적화 변수로 이용한 도착비행 스케쥴 최적 화 문제를 설정한 후 계산상의 편의를 위해 조 합최적화 문제로 재설정하였으며, Branch-and- Bound 알고리즘을 이용하여 최적해를 찾는 알 고리즘을 개발하였다. 특히 polynomial time algorithm 이 아닌 Branch-and-Bound 알고리 즘의 단점을 최소화 하기 위해 Lagrangian Dual Decomposition 을 이용하여 LP(Linear Programming)-relaxation 을 이용한 경우보다 조금 더 최적해에 근접한 해의 범위를 제공하게 함으로써 항공기가 밀집된 경우 Branch-and- Bound 알고리즘의 계산시간을 줄이도록 하였다.

2. 최적화 문제 설정

도착 항공기들의 스케쥴링 최적화 문제는 정 적최적화 문제로 설정되었으며 항공기들의 도착 지연시간에 따른 가격함수와 안전거리유지, 지 연시간 모델에 따른 제한조건은 다음과 같다.

min ( ) f td k,

i i

{ }

{

¹ ²

}

. . or

for , {1, 2, , },

for 1, 2, ,

, , ,

i

j i ij i j ji

ac

i i i i i

ac Ntd

i i i i i

s t STA STA STA STA

i j N i j

STA ETA td k T

i N

td TD td td td

k

- ³ D - ³ D

" Î ¹

= + +

" Î

Î =

L

L L

( ) ( )

, 0=min max

iÎZ ki £ki£ ki

(1)

여기에서 밑첨자 i는 항공기의 식별번호를 나 타내고, 스케쥴링에 고려해야 할 항공기가 모두

Nac 대가 있는 것으로 가정한다. STA는 합류 지점 등 스케쥴링을 적용 해야 하는 지점에의 도착예정시간 (Scheduled Time of Arrival)을, ETA 는 도착예상시간 (Estimated Time of Arrival)을 나타낸다. 즉, 각 항공기의 ETA를 적절히 변화시켜 다른 항공기와의 안전거리를 만족하는 STA로 변화시키는 것이 이 스케쥴링

의 목적이라고 할 수 있다. td_i 는 이용 가능한 도착지연시간 중에 air-borne holding 을 제외 한 나머지 대기비행에 의한 지연시간을 나타내 며, 이용 가능한 비행 궤적, 비행 모드 등을 고 려하여 유한집합 TD_i의 원소중 하나이다. 이용 가능한 지연시간들의 집합인 TD_i는 항공기마다 다르게 주어질 수 있으며, 이용 가능한 비행모 드에 따라 음의 값을 갖는 원소가 포함될 수 있 다. T_i는 air-borne holding 을 한번 수행했을 때 걸리는 시간으로, 항공기의 접근 경로나 항 공기 종류에 따라 다르게 주어질 수 있고 여러 번 수행할 수 있으므로 0 또는 양의 정수 값을 갖는 k_i에 의해 도착지연시간이 달라지는 위와 같은 모델을 사용하게 된다. 가격함수는 도착지 연시간을 결정하는 두 개의 변수 td_i와 k_i에 의 해 결정되며, 보통 다음과 같이 항공편에 따른 도착우선권을 위한 가중치 w_i를 이용한 선형함 수로 표현된다.

( ) ( )

1

,

Nac

i i i i i i

i

f td k w td k T

=

å

+ (2)

공항근처 공역에서는 항공기들이 정해진 경로 를 따라 움직이도록 되어 있으며, 같은 경로상 의 항공기들 간의 안전거리 유지는 시간으로 표 시될 수 있다 (seconds in trail).[7] 특히 활주 로 최종 접근 지점에서는 앞선 항공기와 뒤따르 는 항공기 각각의 등급에 따라 다른 간격이 적 용될 수 있다.[7] 따라서 안전거리 D 는 어느 항공기가 앞서느냐에 따라 다르게 적용될 수 있 으므로 (1)의 첫번째 줄과 같은 조건식으로 표 현될 수 있다. 이 조건식은 다음과 같이 추가적 으로 이진변수 a_ij, a_ji와 충분히 큰 양의 상수

M 을 이용하여 다음과 같이 표현할 수 있으며 이 경우 해의 검색영역은 convex space 가 된 다. 이로 인해 주어진 최적화 문제는 LP relaxation 에 의해 Branch-and-Bound 알고리 즘을 이용하여 풀 수 있게 된다.

j i ij ij

i j ji ji

STA STA Ma

- ³ D -

- ³ D - (3)

(3)

{ }

1 , 1, 0

ij ji

ij ij

a a

+ =

Î

3. 최적화 알고리즘

앞서 설정한 최적화 문제는 Integer Linear Programming (ILP)에 많이 이용되는 Branch- and-Bound 알고리즘을 이용하였다.

그림 1. Branch-and-Bound 알고리즘 위의 그림 1 은 N_ac=5일 때 가능한 Branching 기법을 나타내고 있다. i 번째 level 의 임의의 분기점을 n_j라 하고 n_j의 부모 분기점으로부터 분기하여 i 번째 level 에 존재하는 모든 분기점 을 P_ij라고 하면, n_iÎP_ij이다. n_j로부터 분기하 는 분기점들의 집합을 O_ij 라 하면, O_ij=P_ij-

{ }

nij 이다. 이렇게 Branch-and-Bound 알고리 즘을 이용하면 도착비행 스케쥴링에서 실제 적 용되고 있는 다른 여러가지 제한조건을 적용할 수 있다. 예를 들어 두 개 이상의 경로를 통해 접근하는 항공기들이 한 지점에서 합류해야 하 는 경우, 앞에서 설정한 최적화 문제를 통해 시 퀀싱 및 스케쥴링 문제를 해결할 수 있는데, 이 경우 같은 경로를 통해 접근하는 항공기들은 그 상대적인 순서가 바뀌지 않도록 해야 하는 경우 가 있다. 같은 경로를 통해 접근하는 항공기들 의 상대순서를 바꾸려면 관제관들의 일부담이 급증하기 때문이며, 같은 이유로 합류지점에의 ETA 순서에 따라 정해질 수 있는 원래 도착순 서를 최대 몇 자리나 바꿀 수 있는지 제한하기 도 한다 (MPS: Maximum Position Shift constraint). 이러한 제한 조건들을 어기는 도착 시퀀스는 앞서 설명한 Branch-and-Bound 알고

리즘의 branching 과정에서 모두 손쉽게 제외 될 수 있다.

이후 (1)~(3)에서 표현된 최적화 문제는 LP- relaxation 을 통해 다음과 같은 형태의 LP 로 주어질 수 있다.

min ( ) . .

f x s t Ax b

x X

£ Î

(4)

위의 (4)에서 LMI (Linear Matrix Inequality)로 표현된 조건식은 안전거리 유지를 위한 조건 식 들로부터 유도될 수 있으며, 최적화 변수로 이 뤄진 벡터

x

^는^부록에^주어진^집합

X

^의^원소

이어야 한다.

ILP 로 표현될 수 있는 다양한 조합 최적화 문제들은 Branch-and-Bound 알고리즘을 적용 하여 전역 최적해를 구할 수 있지만 Branch- and-Bound 알고리즘의 가장 큰 단점은 polynomial time algorithm 이 아니라는 것이며 이 경우 가장 문제시 되는 computation time 을 줄이려면 각각의 branch 의 가격함수의 범위를 제한하는데 있어서 dual gap 을 최소화 해야한 다. 이 때 다음과 같이 Lagrangiana dual decomposition 을 이용하면 dual gap 을 줄여 (1)~(3)으로 표현된 원래의 최적화 문제의 원래 최적해에 좀 더 근접한 해를 얻을 수 있으며, 이 경우 최적해를 찾기까지 조사 해야 하는 branch 의 수를 줄일 수 있다.

먼저 f x( )= f x( _ij)을 dualize 하여 다음 (5)와 같은

(

LDu

)

를 설정한다.

(

LDu

)

:

{ }

1

1 1

min ( ) ( ) ( )

i j i j

t t

R R R R

i j i

f x u f x f x

-

= = +

æ ö

+ -

ç ÷

è

å å

ø

1

1 1

. . , , , ,

, 0, 1

i j i j

i j i j i j i j

R R R R

s s

R R R R R R R R

i j i

s t Ax b x X x x Ax b

x X u u

-

= = +

£ Î = £

Î ³

å å

= ⁽⁵⁾

여기에서

i j

XR R 는 부록에 주어져 있으며. 이

(4)

후 다시

i j

xR R =y 를 dualize 하여 다음 식(6)과 같이

(

LDuv

)

를 설정한다.

(

LDuv

)

:

{ }

( )

1 1

( ) ( )

min ( )

i j i j

R R R R

t t

i j i R RT R R

i j i

u f x f x

f x

v y x

- -

= = +

æ æ - öö

ç ç ÷÷

ç + ç ÷÷

ç çç+ - ÷÷÷

ç ÷

è ø

å å å å

1

1 1

. . , , ,

, ,

, 0, 1

i j i j

i j i j i j

i j i j

R R R R

R R R R R R

s s

R R R R

i j i

s t Ax b x X x x Ax b

x X y x Ay b

y Y u u

-

= = +

£ Î = £

Î = £

Î ³

å å

=

(6)

여기에서 집합Y 는 부록에 주어져 있다.

이후 (4)로 주어진 원래 풀고자 하는 문제의 Dual 문제,

( )

^D 는 다음과 같이 주어진다.

( )

^{D :} max₍₁₎

(

LDuv

)

t t R Ri j v

- v

ÎR ^� (7)

어떤 최적화 문제 P 의 최적해를 ^{v P}

( )

^라고

하고, (1)~(3)으로 주어진 문제를 P , LP- relaxation 을 이용하여 P를 재설정한, (4)로 주 어진 문제를 (LP)라고 하면 weak duality theory 를 이용하여 다음의 (8)을 증명할 수 있으며 이 는 LP-relaxation 을 이용한 (LP)보다 위에서 제 안 바와 같은 Lagrangian Dual Decomposition 을 이용한 Dual 문제

( )

^D ^가 ^v

(

^LP

)

^더욱 ^근접한 ^해

를 제공함으로써 Branch-and-Bound 알고리즘에 서 계산상의 효율을 높일 수 있게 된다. 식 (8) 의 증명은 부록에 나타나 있다.

( )

LP

(

LDu

) ( )

D

( )

P

v £v £v £v % (8)

4. 시뮬레이션

앞서 제안한 알고리즘은 한국 공항공사에서 제공한 김포공항의 도착 항공기 궤적데이터를 이용해 시뮬레이션 되었다.

그림 2 에서 F 는 활주로 최종 접근 지점을 나타내며 R2, R1 을 스케쥴링 결과에 따른 대기

비행 시작 지점으로 가정하고 합류 지점인 M 에서의 최적화된 합류를 위해, 위에서 제안한 시퀀싱 및 스케쥴링 문제를 적용하였다.

-0.5 0 0.5 1 1.5 2 2.5

x 10⁵ -3

-2.5 -2 -1.5 -1 -0.5 0 0.5x 10⁵

(m)

F M

R1 R2

그림 2. 김포공항 접근 비행 궤적 예시 스케쥴링은 적용 대상의 실시간성을 감안하여 Receding Horizon Control 을 적용하였으며, 스케쥴링의 Time window 는 2 시간, frequency 는 3/hr 로 적용하였다. MPS 조건은 최대 4 로 주어졌으며, 동일 경로를 통해 접근하는 항공기 의 도착순서 변경은 air-borne holding 을 통해 가능한 것으로 가정하였으며, air-borne holding 에 적용되는 시간은 3 분으로 가정하였 다.

그림 3 은 실제 항공기의 도착 순서가 바뀌는 것과 계산에 사용된 시간을 나타내고 있으며, 표 1 은 전체 113 대 항공기중 94~103 번 항공 기의 스케쥴링 결과를 나타낸다. 시뮬레이션 결 과와 같이 도착 지연시간의 합을 최대 26%로 줄 일 수 있는 것으로 나타났으며 특히 도착비 행이 밀집하는 특정시간대에 급격하게 증가하는 계산시간을 제안한 Lagrangian Dual Decomposition 을 이용하여 최대 72%정도로 줄일 수 있음을 확인하였다.

5. 결론

본 논문에서는 수행 가능한 공중대기 비행모 드를 고려하여 불연속적인 도착지연시간을 최적

(5)

화 변수로 이용한 도착비행 스케쥴 최적화 문제 를 설정한 후 Branch-and-Bound 알고리즘을 이용하여 최적해를 찾는 알고리즘을 개발하였다.

특히 polynomial time algorithm 이 아닌 Branch-and-Bound 알고리즘의 단점을 최소화 하기 위해 Lagrangian Dual Decomposition 을

표 1. 실제 비행 데이터와 시뮬레이션 결과의 비교

Basic Inform Actual Flight Data Simulation Result

Aircra ft ID numbe r

Call sign Aircr

aft Type

ETA (at M)

(sec)

Arrival Order

STA (at M)

(sec)

Delay (A) (sec)

Arrival Order

STA (at M)

(sec)

Delay (B) (sec)

Delay(B) Delay(A)

94 AAR8738 2 67784 95 67784 0 94 67784 0 /

95 HSF1097 2 67724 94 67966 242 95 67904 180 0.74

96 KAL1138 2 67964 96 68105 141 96 68144 180 1.28

97 AAR8708 2 69104 97 69196 92 97 69104 0 0

98 KAL1260 2 70364 98 70562 198 98 70364 0 0

99 KAL6816 2 70604 99 70739 135 99 70604 0 0

100 AAR3625 2 70664 100 70982 318 101 71204 540 1.70

101 JJA124 2 70784 101 72244 146 100 70964 180 1.23

102 HSF1092 2 71684 102 71867 183 102 71684 0 0

103 KAL1140 2 73364 103 73576 212 105 73724 360 1.70

2.5 3 3.5 4 4.5 5

x 10⁴ time(sec)

2.5 3 3.5 4 4.5 5

x 10⁴ 0

1 2 3 4 5

Time (sec)

Computation time (sec)

LP D_X' STAs at M

STAs at R₁ or R₂

approaching from R₁ approaching from R₂

(a) 스케쥴링 결과 (time = 25000sec ~ 52000sec)

5 5.5 6 6.5 7 7.5

x 10⁴ time(sec)

5 5.5 6 6.5 7 7.5

x 10⁴ 0

20 40 60 80

Time (sec)

Computation time (sec)

Congested Time Periods STAs at M

STAs at R₁ or R₂

approaching from R₂ approaching from R₁

(b) 스케쥴링 결과 (time = 50000sec ~ 77000sec) 그림 3. 시뮬레이션 결과

(c)

(6)

이용하여 LP(Linear Programming)-relaxation 을 이용한 경우보다 조금 더 최적해에 근접한 해의 범위를 제공하게 함으로써 항공기가 밀집 된 경우 Branch-and-Bound 알고리즘의 계산 시간을 줄이도록 하였다. 특히 제안된 알고리즘 은 항공기의 종류나 항공기가 접근하는 비행 루 트, 또한 날씨변화 등의 여러가지 조건에 따라 다르게 최적화 변수로 이용되는 도착지연시간이 다르게 주어질 수 있으며, MPS (Maximum Position Shift) 제한이나 동일 경로를 통해 접 근하는 항공기의 순서 바꿈을 허용하지 않는 등 복잡한 경우의 스케쥴링이 가능하다.

참고문헌

[1] Transportation Safety Board of Cadada http://www.tsb.gc.ca/en/air/index.asp?section=1 [2] A. M. Bayen, T. Callantine, C. J. Tomlin, Y. Ye, J. Zhang, “ Optimal Arrival Traffic Spacing via Dynamic Programming” , AIAA Guidance, Navigation, and Control Conference and Exhibit, Aug. 2004, RI.

[3] G. L. Salter and D. Yang, “ Dynamic Optimization of Delay Distribution in an Uncertain Environment” , AIAA Guidance, Navigation and Control Conference and Exhibit, Aug. 2004, RI.

[4]V. H. L. Cheng, L. S. Crawford and P. K. Menon,

“ Air Traffic Control Using Genetic Search Techniques” , Proceedings of the 1999 IEEE International Conference on Control Applications, Hawaii, Aug. 1999.

[5] J. V. Hansen, “ Genetic Search Methods in Air Traffic Control” , Computers and Operations Research Vol. 31, pp. 445-459, 2004.

[6] X. B. Hu and W. H. Chen, “ Receding Horizon Control for Aircraft Arrival Sequencing and Scheduling” , IEEE Transactions on Intelligent Transportation Systems, Vol. 6, No. 2, Jun. 2005.

[7] Zhang, X., Zhang, X., Zhang, J., and Liu, B.,

“ Optimization of Sequencing for Aircraft Arrival Based on Approach Routes” , Proceedings of the 2007 IEEE Intelligent Transportation Systems Conference Seattle, WA, Sep.-Oct., 2007.

부록

( ) ( ) { }

{ } ( )

{ }

1 2 1 2 1 2 1 3 1

1 2

[ , , , , , , , , , ] ,

, 0 max for , , , ,

, , , for ,

0,1 for

t t t t

i i i

tdRi

i i i i i

i j

T

R R R R R R R R R R R R

R R R i all sequenced t

N

R R R R R i all sequenced

R R

x k k k td td td a a a

k k k R AC AC R R R

X x

td TD TD TD TD R AC AC

a

= -

Î £ £ " Î - =

=

Î = " Î -

= "

L L L

L L

Z

( )

, ,

i j all sequenced i j

R R AC AC R R

ì ü

ï ï

í ý

ï ï

ï Î - < ï

î þ

( ) ( ) { } { } { }

( ) ( )

1 2 1 2 1 2 1 3 1

1 2

[ , , , , , , , , , ] ,

0, max , for , , , , , ,

, , 0 max , 0 max ,

min , max f

t t t t

k k

i j i i j j

i j k k k

T

R R k all sequenced i j t i j

R R R R R R

R R R R R

x k k k td td td a a a

k k R AC AC R R R R R R R

k k k k k k

X x td TD TD

= -

é ù

= " Î - - = -

ë û

Î £ £ £ £

é ù

= Î

ë û

L L L

L Z

( ) { }

[ ] ( ) { }

{ }

or , ,

,

0,1 for , , , ,

0,1

i i j j

k l

i

k all sequenced i j

R R R R

R R k l all sequenced i j k l

R Rj

R AC AC R R

td TD td TD

a R R AC AC R R R R

a

ì ü

ï ï

" Î - -

í ý

ï ï

Î Î

ï ï

= " Î - - <

ï ï

ï = ï

î þ

(7)

( ) ( )

( ) ( ) ( )

[ ] ( )

1 2 1 2 1 2 1 3 1

[ , , , , , , , , , ] ,

0, max for ,

min , max for ,

0,1 for , ,

t t t t

k k

k k k

k l

T

R R k all sequenced

R R R k all sequenced

R R k l all sequenced

y k k k td td td a a a

k k R AC AC

Y y

td TD TD R AC AC

a R R AC AC

= -

é ù

= " Î -

ë û

= Îé ù " Î -

ë û

= " Î -

L L L

k l

R R

ì ü

ï ï

í ý

ï ï

ï < ï

î þ

Theorem A.1 v(LD )_u £v(D)

Proof. ^u ¹

{ }

¹

1 1

, , ,

(LD ) min ( ) ( ) ( )

, 1, 0

i j

i j i j

i j i j i j i j

t t R R

t t

R R R R

i j i R R R R R R R R

i j i

Ax b Ax b x X

v f x u f x f x

x X u u

-

= = +

£ £ Î

ì ü

ï ï

= í + - ý

Î = ³

ï ï

î þ

å å å å

1 1

1 1 1 1

min ( ) , , 1, 0

i j i j i j i j i j i j i j

t t t t

R R R R R R R R R R R R R R

i j i i j i

u f x Ax b x X u u

- -

= = + = = +

ì ü

ï ï

= í £ Î = ³ ý

ï ï

î

å å å å

þ

{ }

1

1 1

, , , ,

min ( ) ( )

1, 0, 0

i j i j i j

i j i j i j i j

i j i j i j

R R R R R R

t t

T t t

R R R R R R R R

i j i R R R R R R

i j i

Ax b Ay b x X y Y

u f x v y x

u v u

-

= = +

£ £ Î Î

ì ü

ï ï

= í + - ý

= = ³

ï ï

î þ

å å å å

{

^{(LD )}^uv i j ⁰

}

^max

{

^{(LD )}^uv i j

}

^(D)

t(t -1) 2

R R R R

v v v v v

= = £ ÎR =

Theorem A.2 v(D)£v(P) Proof. In

i j

XR R , all elements of vector xare relaxed except for , , , ,

i j i j i j

R R R R R R

k k td td a

é ù

ë û. Then, by the definition of

i j

XR R above, XÍXR R_i _jÍconv X

( )

. Since

i j

XÍXR R , min ( ) min ( )

i j

f xR R £ f x for

i, j

R R

" .

{ }

1 1

1 1 1 1

(P) min ( ) , min _i _j ( _i _j) _i _j , _i _j _i _j, _i _j 1, _i _j 0

t t t t

i j i i j i

v f x Ax b x X u f x Ax b x X u u

- -

= = + = = +

ì ü

ï ï

= £ Î ³ í £ Î = ³ ý

ï ï

î

å å å å

þ

and

{ }

min , , , , 0

i j i j i j i j i j

R R R R R R R R R R

y-x Ax £b x ÎX Ay£b yÎY y=x £ .

Therefore,

1 1

1 1 1 1

(P) min ( ) , , 1, 0

t t t t

i j i i j i

v u f x Ax b x X u u

- -

= = + = = +

ì ü

ï ï

³ í £ Î = ³ ý

ï ï

î

å å å å

þ

{ }

1 1

1 1 1 1

min ( ) , , 1, 0

max min , , , ,

(D)

t t t t

i j i i j i

T t(t -1) 2

u f x Ax b x X u u

v y x Ax b x X Ay b y Y y x v

v

- -

= = + = = +

ì ü

ï ï

³ í £ Î = ³ ý

ï ï

î þ

+ - £ Î £ Î = Î

=

å å å å

R

Corollary A.1 ^v

( )

^LP ^£^v

(

^LD^u

)

^£^v

( )

^D ^£^v

( )

^P^%

Proof. As shown in the proof of Theorem A.2, min (f x_{R R}_i _j)£min ( )f x for "R R_i, _j by linear programming relaxation, so the first inequality is valid. The second and third inequalities can be easily proved by Theorems A.1 and A.2, respectively.