ươ

Ch

ng 4

BÀI TOÁN TỐI ƯU TỔ HỢP BÀI TOÁN TỐI ƯU TỔ HỢP

a ĩ h g N   c ứ Đ n ễ y u g N

1

ộ

N i dung

 1. Phát biểu bài toán  2. Duyệt toàn bộ  3. Thuật toán nhánh cận

a ĩ h g N   c ứ Đ n ễ y u g N

2

ể 1. Phát bi u bài toán

 1.1. Bài toán tổng quát  1.2. Bài toán người du lịch  1.3. Bài toán cái túi  1.4. Bài toán đóng thùng

a ĩ h g N   c ứ Đ n ễ y u g N

3

ề

ượ ụ ổ ợ  h p đ

ớ

ụ ụ ụ ấ ệ

ấ ọ ố

ượ ấ

ậ ấ

 Trong r t nhi u v n đ   ng d ng th c t ấ ự ế ề ứ ấ   ấ ủ ổ ợ  h p, các c u hình t c a t c gán  ị ử ố ị ằ ộ cho m t giá tr  b ng s  đánh giá giá tr  s   ử ố ấ ủ d ng  c a  c u  hình  đ i  v i  m c  đích  s   ụ ể d ng  c   th  nào  đó. Khi  đó  xu t hi n  bài  ự toán:  Hãy  l a  ch n  trong  s   các  c u  hình  ị ấ ổ ợ  h p ch p nh n đ t c c u hình có giá tr   ố ử ụ t  nh t.  Các  bài  toán  nh   v y  s   d ng  t ẽ ọ chúng ta s  g i là bài toán t

ố ư ổ ợ ư ậ  h p. i  u t

a ĩ h g N   c ứ Đ n ễ y u g N

4

ể

Phát bi u bài toán

 D­íi d¹ng tæng qu¸t bµi to¸n tèi ­u tæ hîp

cã thÓ ph¸t biÓu nh­ sau:

T×m cùc tiÓu (hay cùc ®¹i) cña phiÕm

hµm

f(x) (cid:0) min (max),

x (cid:0)

víi ®iÒu kiÖn  D,      trong ®ã D lµ tËp h÷u h¹n phÇn tö.

a ĩ h g N   c ứ Đ n ễ y u g N

5

ữ

Các thu t ngậ

 f(x) - hµm môc tiªu cña bµi to¸n,  x (cid:0)  D - tËp c¸c ph­¬ng ¸n cña bµi to¸n.  Th«ng th­êng tËp D ®­îc m« t¶ nh­ lµ tËp c¸c cÊu h×nh tæ hîp tho¶ m·n mét sè tÝnh chÊt cho tr­íc nµo ®ã.

 Ph­¬ng ¸n x*  (cid:0)

D - ph­¬ng ¸n

a ĩ h g N   c ứ Đ n ễ y u g N

6

D ®em l¹i gi¸ trÞ nhá nhÊt (lín nhÊt) cho hµm môc tiªu ®­îc gäi lµ p h­¬ng   ¸n  tè i  ­u, khi ®ã gi¸ trÞ f*  =  f(x*)  ®­îc gäi lµ g i¸  trÞ  tè i  ­u cña bµi to¸n.

ể 1. Phát bi u bài toán

 1.1. Bài toán tổng quát  1.2. Bài toán người du lịch  1.3. Bài toán cái túi  1.4. Bài toán đóng thùng

a ĩ h g N   c ứ Đ n ễ y u g N

7

Bµi to ¸n ng ­ê i du lÞc h (Traveling Salesman Problem – TSP)

 Mét ng­êi du lÞch muèn ®i tham quan n

 Hành  trình  là  cách  đi  xuÊt  ph¸t  tõ  m é t  thµnh  phè   nµo  ®ã  ®i  qua  tÊt  c¶  c¸c  thµnh  phè   cß n  l¹i,  m çi  thµnh  phè   ®óng  m é t  lÇn,  råi  quay  trë   l¹i  thµnh  phè   xuÊt  ph¸t.

 BiÕt c ij lµ chi phÝ ®i tõ thµnh phè Ti ®Õn

thµnh phè T1, T 2, ..., T n.

a ĩ h g N   c ứ Đ n ễ y u g N

8

 T×m hµnh tr×nh víi tæng chi phÝ lµ nhá

thµnh phè Tj (i, j = 1, 2,..., n),

nhÊt.

ơ ượ

ử

S  l

ề ị c v  l ch s

the  1930's,  the  1930's,

reappeared  reappeared

 In   In

the  the

in  in

 The  origins  of  the  TSP  are  obscure.  In  the  1920's,  the   The  origins  of  the  TSP  are  obscure.  In  the  1920's,  the  mathematician and economist Karl Menger publicized it  mathematician and economist Karl Menger publicized it  among his colleagues in Vienna.  among his colleagues in Vienna.  the  problem  the  problem  mathematical circles of Princeton.  mathematical circles of Princeton.

 In   In

the  1940's,  the  1940's,

it  was   studied  by  statisticians  it  was   studied  by  statisticians  (Mahalanobis  (1940),  Jessen  (1942),  Gosh  (1948),  (Mahalanobis  (1940),  Jessen  (1942),  Gosh  (1948),  Marks  (1948))  in  connection  with  an  agricultural   Marks  (1948))  in  connection  with  an  agricultural   the  mathematician  Merill  Flood  application  and  application  and  the  mathematician  Merill  Flood  popularized  it  among  his  colleagues  at  the  RAND  popularized  it  among  his  colleagues  at  the  RAND  Corporation.   Eventually,   the  TSP  gained  notoriety  as  Corporation.   Eventually,   the  TSP  gained  notoriety  as  the  prototype  of  a  hard  problem  in  combinatorial  the  prototype  of  a  hard  problem  in  combinatorial  optimization: examining the tours one by one  is out of  optimization: examining the tours one by one  is out of  the question because of their large number, and no other  the question because of their large number, and no other  idea was on the horizon for a long time.  idea was on the horizon for a long time.

a ĩ h g N   c ứ Đ n ễ y u g N

 New  history  with  George  Dantzig,  Ray  Fulkerson,  and   New  history  with  George  Dantzig,  Ray  Fulkerson,  and

Selmer Johnson's 1954 breakthrough.  Selmer Johnson's 1954 breakthrough.

9

 Ta cã t­¬ng øng 1-1 gi÷a một hµnh tr×nh

... (cid:0) T(cid:0) (1) (cid:0) T(cid:0) (2) (cid:0) T(cid:0) (1) T(cid:0) (n) (cid:0)

víi mét ho¸n vÞ (cid:0) = ((cid:0) (1), (cid:0) (2),..., (cid:0) (n))

cña n sè tù nhiªn 1, 2,..., n.

§Æt

f((cid:0) ) = c (cid:0) (1),(cid:0) (2) +... + c (cid:0) (n­1),(cid:0) (n) + c (cid:0) (n),(cid:0) (1).

Ký hiÖu: (cid:0)

a ĩ h g N   c ứ Đ n ễ y u g N

10

- tËp tÊt c¶ c¸c ho¸n vÞ cña n sè tù nhiªn 1, 2,..., n.

 Khi ®ã bµi to¸n ng­êi du lÞch cã thÓ ph¸t biÓu d­íi d¹ng bµi to¸n tèi ­u tæ hîp sau:

(cid:0) min { f((cid:0) ) : (cid:0)  (cid:0) }.

ố ằ

ườ n!,  trong  đó  ch   có  (

ỉ ở

ố ấ ỳ ố

a ĩ h g N   c ứ Đ n ễ y u g N

 Có  th   th y  r ng  t ng  s   hành  trình  c a  ấ ể ủ ổ ị n­1)!  i  du  l ch  là  ng ể ự ự hành trình th c s  khác nhau (b i vì có th   ừ ộ ấ   m t  thành  ph   b t  k ,  nên  có  xu t  phát  t ộ ể ố ị th   c   đ nh  m t  thành  ph   nào  đó  là  thành  ấ ố ph  xu t phát). 11

ể 1. Phát bi u bài toán

 1.1. Bài toán tổng quát  1.2. Bài toán người du lịch  1.3. Bài toán cái túi  1.4. Bài toán đóng thùng

a ĩ h g N   c ứ Đ n ễ y u g N

12

ể ộ ộ

Bài toán cái túi  (Knapsack Problem)  M t  nhà  thám  hi m  c n  đem  theo  m t  cái  ầ ng không quá

ượ ọ b. túi có tr ng l

 Có n đ  v t có th  đem theo. Đ  v t th ể

ượ

ồ ậ ồ ậ ứ j

ng là

aj và

 giá tr  s  d ng là  ị ử ụ

cj (j = 1, 2,..., n).

có   tr ng l ọ

ầ

ỏ ằ ồ ậ ủ ể

a ĩ h g N   c ứ Đ n ễ y u g N

 H i  r ng  nhà  thám  hi m  c n  đem  theo  các  ể ổ đ  v t nào đ  cho t ng giá tr  s  d ng c a  các đ  v t đem theo là l n nh t? 13

ị ử ụ ấ ồ ậ ớ

ể

Phát bi u bài toán

 Mét ph­¬ng ¸n ®em ®å cña nhµ th¸m hiÓm cã thÓ biÓu diÔn bëi vect¬ nhÞ ph©n ®é dµi n: x  = (x1, x 2,..., x n), trong ®ã x j  = 1 nÕu ®å vËt thø j ®­îc ®em theo vµ xj = 0 nÕu tr¸i l¹i.

 Víi ph­¬ng ¸n x, gi¸ trÞ ®å vËt ®em theo lµ = (cid:0)

,

c x j

j

j

n f x ( ) = 1

n

= (cid:0)

tæng träng l­îng ®å vËt ®em theo lµ g x ( )

a x j

j

j

= 1

a ĩ h g N   c ứ Đ n ễ y u g N

14

Bài toán cái túi

 Bµi to¸n c¸i tói cã thÓ ph¸t biÓu d­íi d¹ng

bµi to¸n tèi ­u tæ hîp sau:

Trong sè c¸c vect¬ nhÞ ph©n ®é dµi n tho¶ m·n ®iÒu kiÖn g(x) (cid:0)  b,  h·y t×m vect¬ x* cho gi¸ trÞ lín nhÊt cña hµm môc tiªu f(x):

max { f(x): x(cid:0) Bn, g(x) (cid:0) b }.

a ĩ h g N   c ứ Đ n ễ y u g N

15

ể 1. Phát bi u bài toán

 1.1. Bài toán tổng quát  1.2. Bài toán người du lịch  1.3. Bài toán cái túi  1.4. Bài toán đóng thùng

a ĩ h g N   c ứ Đ n ễ y u g N

16

Bµi to ¸n ®ãng  thïng   (Bin Packing)

ượ ng  là ồ ậ ớ  Có  n  đ   v t  v i  tr ng  l

ầ ọ ế ồ ậ

ượ

ng  là  ỏ ử ụ

w1,  w2,  ...,  wn. C n tìm cách x p các đ  v t này vào các  b  sao  cho  cái  thùng  có  cùng  dung  l ể ấ ầ ố s   thùng  c n  s   d ng  là  nh   nh t  có  th   c.ượ đ

a ĩ h g N   c ứ Đ n ễ y u g N

17

ể

Phát bi u bài toán

b, i = 1, 2,.., n.

a ĩ h g N   c ứ Đ n ễ y u g N

 Ta cã thÓ gi¶ thiÕt lµ                       wi (cid:0)  Do ®ã sè thïng cÇn sö dông ®Ó chøa tÊt c¶ c¸c ®å vËt lµ kh«ng qu¸ n. VÊn ®Ò lµ cÇn sè thïng Ýt nhÊt. Ta sÏ më s½n n c¸i thïng. Bµi to¸n ®Æt ra lµ h·y x¸c ®Þnh xem mçi mét trong sè n ®å vËt cÇn ®­îc xÕp vµo c¸i thïng nµo trong sè n c¸i thïng ®· më ®Ó cho sè thïng chøa ®å lµ Ýt nhÊt. 18

Bài toán đóng thùng

ế

ư

ượ ế

j,

ồ ậ i đ

c x p vào thùng

ể

ể ướ

i

 Đ a vào bi n Bun ế     xij = 1, n u đ  v t  ạ ế i.            0, n u trái l Khi đó bài toán đóng thùng có th  phát bi u d n

n

d ng:ạ

) min,

� � sign x ( ij

i

j

= 1

= 1

n

=

=

(cid:0)

i

n

1,

1, 2,...,

x ij

j

= 1

n

=

(cid:0)

b

j

,

1, 2,...,

n ;

w x i ij

= 1

=

(cid:0) (cid:0)

a ĩ h g N   c ứ Đ n ễ y u g N

�

i

j

{0,1},

,

1, 2,...,

n .

i x ij

19

2. DUYỆT TOÀN BỘ

a ĩ h g N   c ứ Đ n ễ y u g N

20

Ộ

N I DUNG

ng pháp

ả ươ  ph 2.1. Mô t ụ ụ 2.2. Ví d  áp d ng: Bài toán cái túi

a ĩ h g N   c ứ Đ n ễ y u g N

21

Mô tả phương pháp

ể ữ

 M t  trong  nh ng  ph i bài toán t

ươ ố ư ổ ợ

ế

ươ

ị

ượ ể t  c   các  ph ng án t t kê đ  tìm ra ph c li

ươ

a ĩ h g N   c ứ Đ n ễ y u g N

ươ ố ư i  u.  ắ ệ ươ ọ ả ươ ư ng pháp xây d ng theo nguyên t c nh   ng  pháp  duy t  toàn

ộ ng  pháp  hi n  nhiên  ặ ấ ể ả nh t đ  gi  h p đ t ra là:  i  u t ổ ợ ệ ơ ở ậ   h p  ta  Trên  c   s   các  thu t  toán  li t  kê  t ủ ươ ệ ừ ng  án  c a  bài  ti n  hành  duy t  t ng  ph ề ỗ ố ớ ng án ta đ u tính giá  toán, đ i v i m i ph ị ạ ụ i nó, sau đó so sánh giá tr   tr  hàm m c tiêu t ạ ấ ụ hàm  m c  tiêu  t ng  án  i  t ệ đ  Ph ự ậ v y  có  tên  g i  là  ph 22 b .ộ

Ộ

N I DUNG

2.1. Mô t

ả ươ  ph ng pháp ụ ụ 2.2. Ví d  áp d ng: Bài toán cái túi

a ĩ h g N   c ứ Đ n ễ y u g N

23

ả

ụ Ví d : Gi

i bài toán cái túi

 XÐt bµi to¸n c¸i tói:

n

=

x D

f x m ax{ ( )

:

},

c x j

j

j

= 1

n

n

=

Σ

(cid:0) (cid:0)

trong ��

B

= D x {

(

,...,

)

:

b }

x n

w x j

j

x x , 1 2

j

= 1

(cid:0)

 cj , wj, b là các s  nguyên d

ố ươ ng, j=1,2,…,

n.

a ĩ h g N   c ứ Đ n ễ y u g N

 CÇn cã thuËt to¸n liÖt kª c¸c phÇn tö cña

D 24

ậ

Thu t toán quay lui  ươ

ấ ồ

ệ

t kê các ph

ng án ch t đ

li

 Xây d ng ự Sk:

ế

ạ i

S1={ 0, t1 }, v i ớ t1=1 n u ế b(cid:0) w1; t1 = 0, n u trái l ả ử

ươ

s  đã có ph

ng án (

 Gi

x1, …, xk­1). Khi đó

ạ

ượ

i là:

ị ủ

ng còn l Dung l         bk­1= b ­ w1x1­ …­wk­1xk­1 ồ ậ Giá tr  c a các đ  v t ch t vào túi là

ấ   fk­1= c1x1 + … + ck­1xk­1

ế

ạ

i

(cid:0) wk; tk = 0, n u trái l

Do đó: Sk = {0, tk}, v i ớ tk=1 n u ế bk­1

ả Sk?

a ĩ h g N   c ứ Đ n ễ y u g N

 Mô t                      For y := 0 to tk do

25

ươ

Ch

ng trình trên Pascal

type  arrint= array[1..20] of integer; var

x, xopt, c, w: arrint;       n,b, bk, fk, fopt: integer;

ươ

i  u: xopt;

ậ

ng án t ị ố ư

ố ư i  u: fopt }

procedure Nhapdl; var i: integer; begin       {Nh p vào n, c, w, b} end;

procedure Inkq; var j; begin      {Ph        Giá tr  t end;

a ĩ h g N   c ứ Đ n ễ y u g N

26

BEGIN {Main program}

procedure KP(i: integer); var j, t: integer; begin      if bk>=w[i] then t:=1  else t:=0; for j := t downto 0 do begin     x[i] := j; bk:= bk­w[i]*x[i];

Nhapdl; bk:=b;       fk:= 0;       fopt:= 0;       KP(1); InKq

fk:= fk + c[i]*x[i];     if  i = n then  begin

END.

if fk>fopt then begin                       xopt:=x; fopt:=fk;               end          end else KP(i+1);          bk:= bk+w[i]*x[i];           fk:= fk ­ c[i]*x[i];

end;

a ĩ h g N   c ứ Đ n ễ y u g N

end; 27

Bình lu nậ

ể ự

ệ

ộ

 Duy t  toàn  b   là  khó  có  th   th c  hi n  đ

ệ ử ệ

ượ ệ c  ạ  hi n đ i

ấ

ữ ả ngay c  trên nh ng máy tính đi n t ụ ể ệ nh t. Ví d  đ  li

ế t kê h t

ệ ử ớ ố

15! = 1 307 674 368 000     hoán v  trên máy tính đi n t

ế

ả ờ

ộ ị  v i t c đ  tính  ể ệ ộ ỷ t  kê    phép  tính  m t  giây,  n u  đ   li toán  1  t ộ ị ầ m t hoán v  c n ph i làm 100 phép tính, thì ta  ả ộ ầ c n m t kho ng th i gian là 130767 giây > 36  ồ ồ ế ti ng đ ng h !

a ĩ h g N   c ứ Đ n ễ y u g N

                    20! ===> 7645 năm

28

 V× vËy cÇn ph¶i cã nh÷ng biÖn ph¸p nh»m h¹n chÕ viÖc t×m kiÕm th× míi cã hy väng gi¶i ®­îc c¸c bµi to¸n tèi ­u tæ hîp thùc tÕ. TÊt nhiªn ®Ó cã thÓ ®Ò ra nh÷ng biÖn ph¸p nh­ vËy cÇn ph¶i nghiªn cøu kü tÝnh chÊt cña bµi to¸n tèi ­ u tæ hîp cô thÓ.

a ĩ h g N   c ứ Đ n ễ y u g N

 Nhê nh÷ng nghiªn cøu nh­ vËy, trong mét sè tr­êng hîp cô thÓ ta cã thÓ x©y dùng nh÷ng thuËt to¸n hiÖu qu¶ ®Ó gi¶i 29 bµi to¸n ®Æt ra.

 Tuy nhiªn ph¶i nhÊn m¹nh r»ng trong nhiÒu tr­êng hîp (vÝ dô trong c¸c bµi to¸n ng­êi du lÞch, bµi to¸n c¸i tói, bµi to¸n ®ãng thïng) chóng ta ch­a thÓ x©y dùng ®­îc ph­¬ng ph¸p h÷u hiÖu nµo kh¸c ngoµi ph­¬ng ph¸p duyÖt toµn bé.

a ĩ h g N   c ứ Đ n ễ y u g N

30

 Khi ®ã, mét vÊn ®Ò ®Æt ra lµ trong qu¸ tr×nh liÖt kª lêi gi¶i ta cÇn tËn dông c¸c th«ng tin ®· t×m ®­îc ®Ó lo¹i bá nh÷ng ph­¬ng ¸n ch¾c ch¾n kh«ng ph¶i lµ tèi ­ u.

a ĩ h g N   c ứ Đ n ễ y u g N

 Trong môc tiÕp theo chóng ta sÏ xÐt mét s¬ ®å t×m kiÕm nh­ vËy ®Ó gi¶i c¸c bµi to¸n tèi ­u tæ hîp mµ trong tµi liÖu tham kh¶o ®­îc biÕt ®Õn víi tªn gäi: thuËt to¸n nh¸nh cËn. 31

3. THUẬT TOÁN NHÁNH CẬN 3. THUẬT TOÁN NHÁNH CẬN (Branch and Bound Algorithm)

a ĩ h g N   c ứ Đ n ễ y u g N

32

Ộ

N I DUNG

 3.1. Sơ đồ chung

 3.2. Bài toán cái túi

 3.3. Bài toán người du lịch

a ĩ h g N   c ứ Đ n ễ y u g N

33

ơ ồ

S  đ  chung

ậ

ủ ụ

ậ

ậ

 Phân  nhánh:

ươ

ạ ớ

ậ ế

ạ ộ

ư

ầ

ụ

a ĩ h g N   c ứ Đ n ễ y u g N

ủ ậ

ươ

ạ

ậ ỗ ậ ng án.

 Thu t toán bao g m hai th  t c:  ồ  Phân nhánh (Branching Procedure)  Tính c n (Bounding Procedure) Phân  nhánh:  Quá  trình  phân  ho ch  t p  các  ướ ph c  ng  án  ra  thành  các  t p  con  v i  kích  th ượ ỏ c  phân  càng  ngày  càng  nh   cho  đ n  khi  thu  đ ậ ươ ậ ho ch  t p  các  ph ng  án  ra  thành  các  t p  con  ầ ử m t ph n t  Tính  c n: ậ Tính  c n: ậ C n  đ a  ra  cách  tính  c n  cho  giá  tr   ị ủ hàm  m c  tiêu  c a  bài  toán  trên  m i  t p  con  A  trong phân ho ch c a t p các ph 34

ơ ồ

S  đ  chung

 Ta sÏ m« t¶ t­ t­ëng cña thuËt to¸n trªn m« h×nh

bµi to¸n tèi ­u tæ hîp tæng qu¸t sau

D },

min { f(x) : x (cid:0) trong ®ã D lµ tËp h÷u h¹n phÇn tö.

Gi¶ thiÕt r»ng tËp D ®­îc m« t¶ nh­ sau ... (cid:0)

A2

A1

An:

D = {x = (x 1, x2, ..., x n) (cid:0)                          x tho¶ m·n tÝnh chÊt P},

(cid:0) (cid:0)

a ĩ h g N   c ứ Đ n ễ y u g N

víi A1,  A2,  ...,  A n   lµ c¸c tËp h÷u h¹n, cßn P lµ

... (cid:0)

A2 (cid:0)

35

tÝnh chÊt cho trªn tÝch §Òcac A1 (cid:0) An.

ậ Nh n xét

ở ụ

ừ

m c

ậ ề

ấ ằ ể ề

1 đ u có th  mô t  Yêu c u v  mô t ầ

ươ

ủ

 Nh n th y r ng, các bài toán v a trình bày  ả ướ ạ i d ng bài toán trên.  d ể ử ụ ể ả ủ ậ D là đ  có th  s  d ng   c a t p  ể ệ ng  án  c a

t  kê  các  ph

D}

ươ

ươ

ng v i bài toán

D}, trong đó g(x) = ­f(x)

a ĩ h g N   c ứ Đ n ễ y u g N

ế ở ệ

ậ thu t  toán  quay  lui  đ   li bài toán.   Bài toán                 max {f(x): x (cid:0) ớ ng đ     là t                min {g(x): x (cid:0)  Do đó ta có th  h n ch   ể ạ

vi c xét bài toán min.

36

Ph©n nh¸nh

 Qu¸ tr×nh ph©n nh¸nh ®­îc thùc hiÖn nhê

thuËt to¸n quay lui:

1

na 1

1 1a

. . .

1

)

)

)n

1 D a ( 1

2 D a ( 1

D a ( 1

=

=

�

trong ��

i

= ) {

1, 2,...,

},

:

i D a ( 1

x D x 1

i a 1

)

n 1 i l� t�p c�c ph��ng �n c� th� ph�t tri�n t� pabp ( a 1

1

(

...

)n

= Ta cã ph©n ho¹ch: 1 D D a ) 1

2 ��� D a ( ) 1

D a ( 1

( )   D 2 1a

a ĩ h g N   c ứ Đ n ễ y u g N

37

Ph©n nh¸nh

ể ặ ươ

ỗ

ứ ng  ng m i ph ộ ậ

ộ

ng án  ươ ng

 Nh  v y ta có th  đ t t ươ ớ ậ a1, a2, ..., ak) v i m t t p con các ph

ư ậ b  ph n ( ủ án c a bài toán:

ủ

ậ

D(a1,..., ak)= { x(cid:0) D: xi = ai , i = 1,..., k }.    b

át  c a  thu t  to

án  quay  lui  ta  s  ẽ ậ a1, a2, ..., ak) và

ươ ế ụ

Ở ướ ổ c  t ng  qu ớ ệ làm vi c v i ph xét các cách ti p t c ph

ộ ng án b  ph n ( ươ ể át tri n ph

ng

án này.

ươ

ươ

ệ

 Đi u đề

ó t

ng v i vi c ph

ạ ân ho ch t p

ậ D

ớ ỏ ơ

ng đ ậ ra thành các t p con nh  h n.

a ĩ h g N   c ứ Đ n ễ y u g N

38

Ph©n nh¸nh

ể ễ ả ư

:

 Quá trình phân nhánh có th  di n t

nh  sau

( )  D(a1,…,ak)

p ka + 1

1 1ka +

2 1ka +

. . .

,...,

)

D a ( 1

1 a a + , k k 1

 Ta cã ph©n ho¹ch:

p

,...,

)

,...,

)

a k

D a ( 1

D a ( 1

i a a + , k k 1

= U

i

= 1

a ĩ h g N   c ứ Đ n ễ y u g N

39

Tính c n ậ Tính c n ậ

 C n  có  ầ

g(a1,..., a k) (cid:0)

min{f(x): x(cid:0) D, xi=ai, i=1,..., k}

(*)

hµm g x¸c ®Þnh trªn tËp tÊt c¶ c¸c ph­¬ng ¸n bé phËn cña bµi to¸n tho¶ m·n bÊt ®¼ng thøc sau:

víi m iỗ lêi gi¶i bé phËn (a 1, a 2, ..., a k), vµ

víi mäi k = 1, 2, ...

a ĩ h g N   c ứ Đ n ễ y u g N

40

 BÊt ®¼ng thøc (*) cã nghÜa lµ gi¸ trÞ cña hµm g t¹i ph­¬ng ¸n bé phËn (a 1,  a 2,  ...,  a k) lµ kh«ng v­ît qu¸ gi¸ trÞ nhá nhÊt cña hµm môc tiªu cña bµi to¸n trªn tËp con c¸c ph­¬ng ¸n

a ĩ h g N   c ứ Đ n ễ y u g N

41

D(a1,..., a k)= { x(cid:0) D: x i = a i , i = 1,..., k }, hay nãi mét c¸ch kh¸c, g(a 1, a 2, . . . , a k) lµ c Ën d­íi cña gi¸ trÞ hµm môc tiªu trªn tËp D(a 1, a 2, ..., a k).

 V× lÏ ®ã, hµm g ®­îc gäi lµ hµm cËn d­íi, vµ gi¸ trÞ g(a 1,  a 2,  .  .  .  ,  a k) ®­îc gäi lµ cËn d­íi cña tËp D(a 1, a 2, ..., a k).

 Do cã thÓ ®ång nhÊt tËp D(a1,...,  a k) víi ph­¬ng ¸n bé phËn (a 1,..., a k), nªn ta còng gäi gi¸ trÞ g(a 1,..., a k) lµ cËn d­íi cña ph­ ¬ng ¸n bé phËn (a 1,..., a k).

a ĩ h g N   c ứ Đ n ễ y u g N

42

ậ

ờ ử ụ

ắ C t nhánh nh  s  d ng c n  iướ d  Gi¶ sö ®· cã hµm g. Ta xÐt c¸ch sö dông hµm nµy ®Ó gi¶m bít khèi l­îng duyÖt trong qu¸ tr×nh duyÖt tÊt c¶ c¸c ph­¬ng ¸n theo thuËt to¸n quay lui.

 Trong qu¸ tr×nh liÖt kª c¸c ph­¬ng ¸n cã thÓ ®· thu ®­îc mét sè ph­¬ng ¸n cña bµi to¸n. Gäi (cid:0) x lµ ph­¬ng ¸n víi gi¸ trÞ hµm môc tiªu nhá nhÊt trong sè c¸c ph­¬ng ¸n ®· t×m ®­îc, ký hiÖu(cid:0) f = f((cid:0) x ).  Ta sÏ gäi

a ĩ h g N   c ứ Đ n ễ y u g N

 (cid:0) x lµ ph­¬ng ¸n tèt nhÊt hiÖn cã,  cßn (cid:0) f lµ kû lôc. 43

ậ

ờ ử ụ

ắ C t nhánh nh  s  d ng c n  iướ d  Gi¶ sö ®· cã (cid:0) f , khi ®ã nÕu         g(a 1, a 2, ..., a k)  > (cid:0) f ,

min{f(x): x (cid:0)

th× tõ bÊt ®¼ng thøc (*) suy ra   (cid:0)  f  < g(a 1,..., a k) (cid:0) D(a 1,...,a k)},

ể ạ

a ĩ h g N   c ứ Đ n ễ y u g N

 V× thÕ tËp D(a 1,...,  a k)  ch¾c ch¾n kh«ng chøa ph­¬ng ¸n tèi ­u và có th  lo i  ệ ỏ b  kh i quá trình duy t. 44

ỏ

ậ

ậ Thu t toán nhánh c n

ươ

ậ

procedure  Branch(k); ể (*   Phát tri n ph

ộ ng án b  ph n (x

1, x2, ..., xk­1)  *)

begin

(cid:0) Ak  do (cid:0) Sk then

for  ak    if   ak    begin

ậ ỷ ụ

ậ

(cid:0) f    then  Branch(k+1)

xk :=  ak;  if   (k = n)   then  < C p nh t k  l c> else   if   g(x1,..., xk)  (cid:0)

end;

a ĩ h g N   c ứ Đ n ễ y u g N

end; 45

ậ

ậ Thu t toán nhánh c n

;

ế

procedure  BranchAndBound; begin  (cid:0) f := +(cid:0) ế (* N u bi

t p/án

(cid:0) x  nào đó thì đ tặ (cid:0) f = f((cid:0) x ) *)

Branch(1); if  (cid:0) f  <  +(cid:0)

ố ư

i  u,

ị ố ư (cid:0) x  là p/án t

i  u >

ươ

ng án > ;

then               <(cid:0) f  là giá tr  t    else  <  bài toán không có ph end;

a ĩ h g N   c ứ Đ n ễ y u g N

46

ơ ồ

ệ

ộ

Chú ý: S  đ  duy t toàn b

 Chó ý r»ng nÕu trong thñ tôc Branch ta

thay c©u lÖnh

(cid:0) f the n if (k = n) the n < CËp nhËt kû lôc> e ls e if g(a1,..., ak) (cid:0)

Branch(k+1)

bëi

if (k = n) the n < CËp nhËt kû lôc> e ls e Branch(k+1)

a ĩ h g N   c ứ Đ n ễ y u g N

47

th× ta thu ®­îc thuËt to¸n duyÖt to µn bé .

Chú ý:

 Vi c  xây  d ng  hàm

ệ ụ ừ

ụ ể ộ g  ph   thu c  vào  t ng    h p  c   th .  Thông u  t

ệ

ơ

ả ơ ố ư ổ ợ ở ế

ự ố ư i  ố ắ

ả ả ủ  v  ph i c a (*).

h p

gi

ả

ớ

ị ủ ế ị ủ g(a1,..., ak) ph i sát v i giá tr  c a v

 Giá tr  c a  ả ủ

ph i c a (*).

ổ ợ bài  toán  t ườ ự th ng ta c  g ng xây d ng nó sao cho:  Vi c tính giá tr  c a  ị ủ g ph i đ n gi n h n vi c  ệ ả i  u t i bài toán t

 R t  ti c  là  hai  yêu  c u  này  trong  th c  t

ế ầ ự ế

ố ậ ấ ườ ng đ i l p nhau. th

a ĩ h g N   c ứ Đ n ễ y u g N

48

Ộ

N I DUNG

 3.1. Sơ đồ chung  3.2. Bài toán cái túi 3.2. Bài toán cái túi  3.3. Bài toán người du lịch

a ĩ h g N   c ứ Đ n ễ y u g N

49

Bài toán cái túi

ượ

 Có n lo i đ  v t.   Đồ v t lo i   ạ j có  ậ  tr ng l ọ ng

aj và

 giá tr  s  d ng là ị ử ụ

cj (j = 1, 2,..., n) .

ạ ồ ậ

ồ ậ ộ

ng  là

 C n ch t các đ  v t này vào m t cái túi có  ầ ọ ị ử ổ b  sao  cho  t ng  giá  tr   s   tr ng  l ớ ồ ậ ụ d ng  c a  các  đ   v t  ch t  trong  túi  là  l n  nh t.ấ

ấ ượ ủ ấ

a ĩ h g N   c ứ Đ n ễ y u g N

50

Bài toán cái túi (KP)

ế ố

ố ượ

ượ

ấ

ồ ậ ng đ  v t lo i

c ch t vào túi,

ạ j đ

ọ ủ

ạ

 Đ a vào bi n s ư         xj – s  l         j=1,2, ..., n  Mô hình toán h c c a bài toán có d ng sau: Tìm

n

n

*

=

=

=

+

f

Z

j

n

f x max { ( )

�� b x ,

,

1, 2,..., }

j

a x j

j

j

� � c x : j

j

j

= 1

= 1

trong ®ã Z+ lµ tËp c¸c sè nguyªn kh«ng ©m.

a ĩ h g N   c ứ Đ n ễ y u g N

51

 Ký hiÖu D lµ tËp c¸c ph­¬ng ¸n cña bµi to¸n:

n

=

=

+

Z

j

n

= D x {

(

,...,

) :

�� b x ,

,

1, 2,..., }

x n

a x j

j

j

x 1

j

= 1

 Gi¶ thiÕt r»ng c¸c ®å vËt ®­îc ®¸nh sè sao cho

bÊt ®¼ng thøc sau ®­îc tho¶ m·n

. . . (cid:0)

c1 /a 1 (cid:0)

c 2 / a 2 (cid:0)

cn / an .

ồ ậ ượ ế

ứ ự

(có nghĩa là các đ  v t đ

không

ị ộ ơ

ị ọ

ủ

c x p theo th  t ượ

tăng c a giá tr  m t đ n v  tr ng l

ng)

(cid:0)

a ĩ h g N   c ứ Đ n ễ y u g N

52

ự

ậ

Xây d ng hàm c n trên

 §Ó x©y dùng hµm tÝnh cËn trên, cïng víi bµi to¸n c¸i tói (KP) ta xÐt bµi to¸n c¸i tói biÕn liªn tôc (KPC) sau đây: T×m

n

n

*

=

=

=

g

j

n

f x max { ( )

b x ,

0,

1, 2,..., }

j

a x j

j

j

� � c x : j

j

j

= 1

= 1

 MÖnh ®Ò. Ph­¬ng ¸n tè i ­u cña bµi to¸n KPC  lµ ve ct¬(cid:0) x = ((cid:0) x1 ,(cid:0) x 2 , ...,(cid:0) xn ) víi c¸c thµnh  phÇn ®­îc x¸c ®Þnh bë i c«ng thø c:

(cid:0) (cid:0)

a ĩ h g N   c ứ Đ n ễ y u g N

(cid:0) x 1 = b / a 1 , (cid:0) x2 = (cid:0) x3 = . . . = (cid:0) xn = 0.      vµ gi¸ trÞ tè i ­u lµ g* = c 1b /a 1.

53

 Chø ng  minh.  XÐt x = (x1,..., x n) lµ mét ph­¬ng

¸n tuú ý cña bµi to¸n KPC. Khi ®ã   (c1 / a 1 ) aj , j = 1, 2, ..., n 0, ta suy ra

(c1 / a 1 ) aj x j , j = 1, 2, ..., n

cj  (cid:0) do xj (cid:0)          c j xj (cid:0)  T  đó ta có ừ

n

n

/

c x j

j

j

j

c a a x ) 1 1

� � (

j

j

= 1

= 1

n

=

(cid:0)

(

)

a x j

j

c a / 1 1

j

*

= 1 =

(cid:0)

g

(

c a b / ) 1 1

(cid:0)

a ĩ h g N   c ứ Đ n ễ y u g N

ề ượ

ệ

ứ

 M nh đ  đ

c ch ng minh.

54

 B©y giê, gi¶ sö ta cã ph­¬ng ¸n bé phËn

 Khi ®ã gi¸ trÞ sö dông cña c¸c ®å vËt

cÊp k: (u 1, u 2, ..., u k).

®ang cã trong tói lµ

k = c 1u 1 + c 2u 2 + . . . + c kuk

(cid:0)

vµ träng l­îng cßn l¹i cña c¸i tói lµ

bk = b – (a 1u 1 + a 2u 2 + . . . + a ku k).

a ĩ h g N   c ứ Đ n ễ y u g N

55

ậ Tính c n trên

=

=

 Ta cã f x

� x D x

k

max{ ( ) :

,

1, 2,..., }

j

u j , j

n

n

=

+

+

x

= + k

k

s max {

Z j , +

1,

n 2,..., }

k

j

a x j

j

�� b , k

j

� � c x : j

= + j k 1

= + j k 1

n

n

+

s

+

x

j

= + k

k

,

0,

1,

n 2,..., }

max {

b k

j

j

a x j

j

k

� � c x : j

= + j k 1

= + j k 1

=

s

+

/

.

k

c b a + k k k 1

+ 1

 VËy ta cã thÓ tÝnh cËn trªn cho ph­¬ng ¸n bé phËn (u 1, u 2, ..., u k) bëi c«ng thøc

(cid:0) (cid:0) (cid:0)

a ĩ h g N   c ứ Đ n ễ y u g N

k + c k+1 b k / a k+1.

56

g(u1, u 2,..., u k) = (cid:0)

 Chó   ý: Khi tiÕp tôc x©y dùng thµnh phÇn thø k+1 cña lêi gi¶i, c¸c ứng cö viên cho x k+1 sÏ lµ 0, 1, ..., [b k / a k+1 ].

 Do cã kÕt qu¶ cña mÖnh ®Ò, khi chän gi¸ trÞ cho x k+1 ta sÏ duyÖt c¸c ứng cö viên theo thø tù gi¶m dÇn.

a ĩ h g N   c ứ Đ n ễ y u g N

57

Ví dụ

thuËt to¸n nh¸nh cËn võa tr×nh bµy f(x) = 10 x1 + 5 x 2 + 3 x 3 + 6 x4 (cid:0) max,

Gi¶i bµi to¸n c¸i tói sau theo

8, 5 x1 + 3 x 2 + 2 x3 + 4 x 4 (cid:0)

xj (cid:0) Z+ , j =1, 2, 3, 4.

a ĩ h g N   c ứ Đ n ễ y u g N

ồ ậ ủ

 Chú ý: Trong ví d  đang xét, các đ  v t đã  ị  không tăng c a giá tr   ng.

ụ ứ ự c x p theo th  t ượ ượ ế ộ ơ ị ọ đ 58 m t đ n v  tr ng l

 Qu¸ tr×nh gi¶i bµi to¸n ®­îc m« t¶ trong c©y t×m kiÕm trong h×nh 1. Th«ng tin vÒ mét ph­¬ng ¸n bé phËn trªn c©y ®­îc ghi trong c¸c « trªn h×nh vÏ t­¬ng øng theo thø tù sau:  c¸c thµnh phÇn cña ph­¬ng ¸n,  (cid:0) - gi¸ trÞ cña c¸c ®å vËt ®ang chÊt trong

tói,

a ĩ h g N   c ứ Đ n ễ y u g N

 w - träng l­îng cßn l¹i cña tói  g - cËn trªn.

59

max,

f(x) =  10 x1 + 5 x2 + 3 x3 + 6 x4  (cid:0)            5 x1 + 3 x2 + 2 x3 + 4 x4 (cid:0)

8,  Z+ , j =1, 2, 3, 4.

xj (cid:0)

a ĩ h g N   c ứ Đ n ễ y u g N

60

KÕt thóc thuËt to¸n, ta thu ®­îc:  Ph­¬ng ¸n tèi ­u: x* = (1, 1, 0, 0),  Gi¸ trÞ tèi ­u: f* = 15.

a ĩ h g N   c ứ Đ n ễ y u g N

61

Ộ

N I DUNG

 3.1. Sơ đồ chung

 3.2. Bài toán cái túi

 3.3. Bài toán người du lịch 3.3. Bài toán người du lịch

a ĩ h g N   c ứ Đ n ễ y u g N

Sir William Rowan Hamilton 1805 ­ 1865

62

 Cè ®Þnh thµnh phè xuÊt ph¸t lµ T1, bµi

min,

to¸n ng­êi du lÞch dÉn vÒ bµi to¸n: T×m cùc tiÓu cña hµm f(1,x 2,..., x n) = c[1,x 2]+c[x 2,x 3]+...+c[x n­1,x n] + c[x n,1] (cid:0) víi ®iÒu kiÖn

(1, x 2, x 3, ..., x n) lµ ho¸n vÞ cña c¸c sè 1,2, ..., n.

a ĩ h g N   c ứ Đ n ễ y u g N

63

ậ ướ

Hàm c n d

i

 Ký hiÖu

c m in = min { c[i, j] , i, j = 1, 2, ..., n, i (cid:0) j }

lµ chi phÝ ®i l¹i nhá nhÊt gi÷a c¸c thµnh

phè.

a ĩ h g N   c ứ Đ n ễ y u g N

64

 CÇn ®¸nh gi¸ cËn d­íi cho ph­¬ng ¸n bé phËn (1, u 2,  ...,  u k) t­¬ng øng víi hµnh tr×nh bé phËn qua k thµnh phè: . . . (cid:0)

T(u2) (cid:0) T1 (cid:0) T(u k-1) (cid:0) T(u k).

ậ ướ

Hàm c n d

i

 Chi phÝ ph¶i tr¶ theo hµnh tr×nh bé

phËn nµy lµ

(cid:0) = c[1,u 2] + c[u2, u 3] + ... + c[u k-1, u k].  §Ó ph¸t triÓn thµnh hµnh tr×nh ®Çy ®ñ, ta cßn ph¶i ®i qua n­k+1 ®o¹n ®­êng n÷a, mçi ®o¹n cã chi phÝ kh«ng Ýt h¬n c m in, nªn cËn d­íi cho ph­¬ng ¸n bé phËn (1, u 2, ..., u k) cã thÓ tÝnh theo c«ng thøc

a ĩ h g N   c ứ Đ n ễ y u g N

65

g(1, u 2, ..., u k) = (cid:0) + (n­k+1) c m in .

Ví dụ

 Giải bài toán người du lịch với ma trận

chi phí sau:

C =

0 3 14 18 15 3 0 4 22 20 17 9 0 16 4 9 20 7 0 18 9 15 11 5 0

a ĩ h g N   c ứ Đ n ễ y u g N

66

 Ta cã  c m in = 3. Qu¸ tr×nh thùc hiÖn thuËt to¸n ®­îc m« t¶ bëi c©y t×m kiÕm lêi gi¶i.

 Th«ng tin ®­îc ghi trong c¸c « trªn h×nh vÏ

 c¸c thµnh phÇn cña ph­¬ng ¸n,  (cid:0) lµ chi phÝ theo hµnh tr×nh bé phËn

 g - cËn d­íi.

theo thø tù sau:

a ĩ h g N   c ứ Đ n ễ y u g N

67

0  3  14  18  15  3  0   4  22  20       C = 17  9   0  16   4  9  20  7   0  18  9 15  11   5   0

a ĩ h g N   c ứ Đ n ễ y u g N

68

ả

K t quế

 K t thúc thu t toán, ta thu đ ậ ế ươ ố ư i  u  (1, 2, 3, 5, 4, 1) t t trình        T1  (cid:0)

ươ ượ ng án  c ph ớ ứ ng  ng v i hành

T2  (cid:0) T5  (cid:0) T3  (cid:0) T4  (cid:0) T1 ,

 Chi phí nh  nh t là 25. ỏ

ấ

a ĩ h g N   c ứ Đ n ễ y u g N

69

Kỷ lục Kỷ lục về giải bài toán người du lịch về giải bài toán người du lịch

a ĩ h g N   c ứ Đ n ễ y u g N

70

ướ

i đ

ỷ ụ K  l c  c TSP gi

(Kích th

ả ượ ) c

1954

1962

1977

1987

1987

1987

1994

1998

2001

2004

49

33

120

532

666

2392

7397

13509

15112

24978

http://www.tsp.gatech.edu/index.html

a ĩ h g N   c ứ Đ n ễ y u g N

71

Year

Research Team

Size of Instance

1954

G. Dantzig, R. Fulkerson, and S. Johnson

49 cities

1971

M. Held and R.M. Karp

64 cities

1975

P.M. Camerini, L. Fratta, and F. Maffioli

67 cities

1977

M. Grötschel

120 cities

1980

H. Crowder and M.W. Padberg

318 cities

1987

M. Padberg and G. Rinaldi

532 cities

1987

M. Grötschel and O. Holland

666 cities

1987

M. Padberg and G. Rinaldi

2,392 cities

1994

D. Applegate, R. Bixby, V. Chvátal, and W.

7,397 cities

Cook

1998

D. Applegate, R. Bixby, V. Chvátal, and W.

13,509 cities

Cook

2001

D. Applegate, R. Bixby, V. Chvátal, and W.

15,112 cities

Cook

2004

D. Applegate, R. Bixby, V. Chvátal, W.

24,978 cities

a ĩ h g N   c ứ Đ n ễ y u g N

Cook,  and K. Helsgaun

72

The First Big TSP

a ĩ h g N   c ứ Đ n ễ y u g N

Dantzig, Ray Fulkerson, and Selmer Johnson (1954) published a description of a method for solving the TSP and illustrated the power of this method by solving an instance with 49 cities, an impressive size at that time. They created this instance by picking one city from each of the 48 states in the U.S.A. (Alaska and Hawaii became states only in 1959) and adding Washington, D.C.; the costs of travel between these cities were defined by road distances. Rather than solving this problem, they solved the 42-city problem obtained by removing Baltimore, Wilmington, Philadelphia, Newark, New Y ork, Hartford, and Providence. As it turned out, an optimal tour through the 42 cities used the edge joining Washington, D.C. to Boston; since the shortest route between these two cities passes through the seven removed cities, this solution of the 42-city problem yields a solution 73 of the 49-city problem.

Procter and Gamble's Contest

 Proctor and Gamble ran a contest in 1962.  The contest required solving a TSP on a specified 33 cities.  There was a tie between many people who found the optimum.  An early TSP researcher, Professor Gerald Thompson of Carnegie Mellon University, was one of the winners.

a ĩ h g N   c ứ Đ n ễ y u g N

74

120 Western German Cities

 Groetschel (1977)  found  the  optimal  tour  of  from  120  cities  what  was  then  West Germany.

a ĩ h g N   c ứ Đ n ễ y u g N

75

532 Locations in America

 Padberg  and  Rinaldi  (1987)  found  the  optimal  tour  of  532  AT&T  switch  locations  in the USA.

a ĩ h g N   c ứ Đ n ễ y u g N

76

666 Cities Worldwide

 Groetschel  and  Holland  (1987)  found  the  optimal  tour  of  666  interesting  places in the world.

a ĩ h g N   c ứ Đ n ễ y u g N

77

2,392 Points

 Padberg and

Rinaldi (1987)  found the optimal  tour through a  layout of 2,392  points obtained  from Tektronics  Incorporated.

a ĩ h g N   c ứ Đ n ễ y u g N

78

7,397­city TSP

 Applegate, Bixby, Chvátal, and Cook (1994) found the optimal  tour for a 7,397­city TSP that arose in a programmable logic  array application at AT&T Bell Laboratories.

a ĩ h g N   c ứ Đ n ễ y u g N

79

13509 Cities in the USA

 Applegate,  Bixby,  Chvátal,  and  Cook  (1998)  found  the optimal tour of the 13,509 cities in the USA with  populations greater than 500.

a ĩ h g N   c ứ Đ n ễ y u g N

80

15112 Cities in Germany

 Applegate,

Bixby,  Chvátal, and  Cook (2001)  found the  optimal tour  of 15,112  cities in  Germany.

a ĩ h g N   c ứ Đ n ễ y u g N

81

24978 Swedish Cities

 Applegate,

Bixby, Chvátal,  Cook, and  Helsgaun (2004)  found the  optimal tour of  24,978 cities in  Sweden.

a ĩ h g N   c ứ Đ n ễ y u g N

82

Optimal Tour of Sweden

 In  May  2004,  the  traveling  salesman  problem  of  visiting  all  24,978  cities  in  Sweden  was  solved:  a  tour of length 855,597 TSPLIB units (approximately  72,500 kilometers) was found and it was proven that  no  shorter  tour  exists.  This  is  currently  the  largest  solved TSP instance, surpassing the previous record  of 15,112 cities through Germany set in April 2001.

a ĩ h g N   c ứ Đ n ễ y u g N

83

Optimal Tour of Sweden

 Research Team

 David Applegate, AT&T Labs - Research  Robert Bixby, ILOG and Rice University  Vašek Chvátal, Rutgers University  William Cook, Georgia Tech  Keld Helsgaun, Roskilde University

 Support for this research was provided by the following

grants  Office of Naval Research Grant N00014-03-1-0040,

"Experimental Modules for Combinatorial Optimization and Mixed-Integer Programming"

 National Science Foundation, Grant DMI-0245609, "Local

a ĩ h g N   c ứ Đ n ễ y u g N

Cuts in Discrete Optimization and Mixed-Integer Programming"

84

Finding Sweden Tour

 The traveling salesman problem (TSP) asks for the cheapest possible tour through a given collection of cities. Solving the problem means to not only find the best tour but also to prove that no cheaper tour is possible. Early work on the TSP in the 1950s focused exclusively on the this full solution of the problem.

 Starting in the mid-1960s researchers began to study the relaxed version of the TSP where we ask only for a tour of low cost. This task is much easier, but performing it well is an important ingredient in a full (exact) solution method, as well as being an interesting problem in its own right. Indeed, tour finding is a very popular topic, having a large and growing literature devoted to its various aspects. And like the TSP itself, tour finding has led researchers to discover general purpose search techniques that have found application in many domains.

 The Sweden TSP was attacked by a number of groups with some of the top tour-finding methods that have been developed to date. Information on the improvements in the best known tour length can be found in the Sweden Computation Log; the results are summarized in the following table.

a ĩ h g N   c ứ Đ n ễ y u g N

85

Finding Sweden Tour

 The final improvement in the tour length was

a ĩ h g N   c ứ Đ n ễ y u g N

made by Keld Helsgaun using a version of his LKH code. This 855,597 value was proved to be optimal by the Concorde TSP code. 86

Finding Sweden Tour

The Concorde solver can accept as an input parameter the value of the best known tour for a TSP instance if one is available. As a full (exact) TSP solver, Concorde is designed to find optimal solutions regardless of the quality of the estimate, but knowledge of a good tour allows for better tuning of parameters that are set in the computer code.

 In the case of the Sweden TSP, the results of the tour-finding attacks guided our choices in approaching the full solution of the problem. Most importantly, the final stages that improved the lower bound from 855,595 up to the optimal value 855,597 required approximately 8 years of computation time (running in parallel on a network of Linux workstations) and without knowledge of the 855,597 tour we would not have make the decision to carry out this final computation.

a ĩ h g N   c ứ Đ n ễ y u g N

87

New record: 85900 cities, 2006

 The  largest  solved  instance  of  the  traveling  salesman  problem  consists  of  a  tour  through  85,900  cities  in  a  VLSI  application that arose in Bell Laboratories in the late 1980s.  The computation with Concorde was carried out in 2005/06  and reported in the book The Traveling Salesman Problem:  A  Computational  Study.  The  instance  is  called  pla85900  in  Gerd  Reinelt's  TSPLIB;  the  shortest  possible  tour  for  the  problem has length 142,382,641 units.

 With  the  solution  of  pla85900,  the  complete  TSPLIB  collection of challenge problems has now been successfully  solved with the Concorde code.

 http://www.tsp.gatech.edu/index.html

a ĩ h g N   c ứ Đ n ễ y u g N

88

Picture of pla85900 tour

a ĩ h g N   c ứ Đ n ễ y u g N

89

15 year race for better tours

Iterated Lin-Kernighan Tour Merging Tour Merging LKH Tour Merging LKH LKH Tour Merging with LKH LKH

 Date Tour Length  07.06.1991 142,514,146  29.03.1996 142,487,006  23.09.1997 142,482,068  14.10.1998 142,416,327  22.10.1999 142,409,553  18.06.2001 142,406,493  27.06.2001 142,405,532  31.08.2001 142,395,130  14.12.2001 142,393,738  15.09.2002 142,385,237  12.12.2002 142,383,704  19.03.2003 142,383,467  28.04.2003 142,383,189  23.12.2003 142,383,011  02.05.2004 142,382,641

Research Team Method David S. Johnson Concorde Concorde Keld Helsgaun Concorde Keld Helsgaun Keld Helsgaun Concorde Keld Helsgaun Hisao Tamaki Approximate Tour Merging Keld Helsgaun LKH Nguyen Dinh Hung Hybrid Genetic Algorithm LKH Keld Helsgaun LKH Keld Helsgaun LKH Keld Helsgaun

a ĩ h g N   c ứ Đ n ễ y u g N

90

Questions? Questions?

a ĩ h g N   c ứ Đ n ễ y u g N

91

Merci à tous !

a ĩ h g N   c ứ Đ n ễ y u g N

92

a ĩ h g N   c ứ Đ n ễ y u g N

93