Home > Software > Algorithm Archive

Algorithm Archive

TSPをGLPKで解いてみる

2009-03-29 (Sun)
Algorithm

Flexで，TSPの近似解法の実行と，LPへの定式化を自動でできるようにしてみたが，ファイルの保存ができないので不便だったので結局Javaで再実装した．

頂点数30のユークリッド巡回セールスマン問題の定式化を以下に貼付ける．（長いのでブログに貼付けるようなものではないけど，ファイルをアップするのは面倒なので）

var x0x1 >= 0, <= 1;
var x0x2 >= 0, <= 1;
var x0x3 >= 0, <= 1;
var x0x4 >= 0, <= 1;
var x0x5 >= 0, <= 1;
var x0x6 >= 0, <= 1;
var x0x7 >= 0, <= 1;
var x0x8 >= 0, <= 1;
var x0x9 >= 0, <= 1;
var x0x10 >= 0, <= 1;
var x0x11 >= 0, <= 1;
var x0x12 >= 0, <= 1;
var x0x13 >= 0, <= 1;
var x0x14 >= 0, <= 1;
var x0x15 >= 0, <= 1;
var x0x16 >= 0, <= 1;
var x0x17 >= 0, <= 1;
var x0x18 >= 0, <= 1;
var x0x19 >= 0, <= 1;
var x0x20 >= 0, <= 1;
var x0x21 >= 0, <= 1;
var x0x22 >= 0, <= 1;
var x0x23 >= 0, <= 1;
var x0x24 >= 0, <= 1;
var x0x25 >= 0, <= 1;
var x0x26 >= 0, <= 1;
var x0x27 >= 0, <= 1;
var x0x28 >= 0, <= 1;
var x0x29 >= 0, <= 1;
var x1x2 >= 0, <= 1;
var x1x3 >= 0, <= 1;
var x1x4 >= 0, <= 1;
var x1x5 >= 0, <= 1;
var x1x6 >= 0, <= 1;
var x1x7 >= 0, <= 1;
var x1x8 >= 0, <= 1;
var x1x9 >= 0, <= 1;
var x1x10 >= 0, <= 1;
var x1x11 >= 0, <= 1;
var x1x12 >= 0, <= 1;
var x1x13 >= 0, <= 1;
var x1x14 >= 0, <= 1;
var x1x15 >= 0, <= 1;
var x1x16 >= 0, <= 1;
var x1x17 >= 0, <= 1;
var x1x18 >= 0, <= 1;
var x1x19 >= 0, <= 1;
var x1x20 >= 0, <= 1;
var x1x21 >= 0, <= 1;
var x1x22 >= 0, <= 1;
var x1x23 >= 0, <= 1;
var x1x24 >= 0, <= 1;
var x1x25 >= 0, <= 1;
var x1x26 >= 0, <= 1;
var x1x27 >= 0, <= 1;
var x1x28 >= 0, <= 1;
var x1x29 >= 0, <= 1;
（途中省略）
var x28x29 >= 0, <= 1;

minimize route: 377.06763319065186*x0x1 + 155.87815754620658*x0x2 + 314.40260813167566*x0x3 + 331.2099032335839*x0x4 + 643.5666243676718*x0x5 + 246.45486402179202*x0x6 + 206.24257562394823*x0x7 + 240.03333101883996*x0x8 + 148.60686390607938*x0x9 + 105.07616285342742*x0x10 + 42.638011210655684*x0x11 + 224.35017272112808*x0x12 + 535.3400788284023*x0x13 + 593.6876283029654*x0x14 + 428.72951846123215*x0x15 + 424.70813507631334*x0x16 + 470.3743190268788*x0x17 + 568.1065040993634*x0x18 + 231.60742647851342*x0x19 + 87.31551981177229*x0x20 + 185.21878954360974*x0x21 + 201.93315725754402*x0x22 + 511.22010915064754*x0x23 + 633.4224498705426*x0x24 + 657.0007610345668*x0x25 + 492.44085939328795*x0x26 + 406.51814227657786*x0x27 + 349.2921413373052*x0x28 + 149.57606760441325*x0x29 + 436.4882587195216*x1x2 + 64.4437739428721*x1x3 + 56.356011214421486*x1x4 + 352.85407748813105*x1x5 + 176.1817243643619*x1x6 + 230.8679276123039*x1x7 + 202.15835377248203*x1x8 + 471.9745755864398*x1x9 + 464.61274196905106*x1x10 + 337.6536687198882*x1x11 + 172.59490143106777*x1x12 + 246.0101623917191*x1x13 + 226.99118925632334*x1x14 + 189.52836199366047*x1x15 + 259.25470101813005*x1x16 + 285.5591007129697*x1x17 + 310.49798711102784*x1x18 + 345.33751606218516*x1x19 + 447.2001788908408*x1x20 + 319.0015673942685*x1x21 + 175.13708916160505*x1x22 + 147.03060905811415*x1x23 + 261.9389241789009*x1x24 + 303.014851121195*x1x25 + 153.05554547287727*x1x26 + 36.345563690772494*x1x27 + 79.88116173416608*x1x28 + 241.306858584666*x1x29 + 383.8814921300583*x2x3 + 405.44543405987446*x2x4 + 751.4093425024738*x2x5 + 266.3719204420766*x2x6 + 334.0808285430339*x2x7 + 361.13432404023854*x2x8 + 52.478567053607705*x2x9 + 102.00490184299969*x2x10 + 154.77725931156684*x2x11 + 327.3178882982108*x2x12 + 639.5193507627428*x2x13 + 663.4282176694024*x2x14 + 538.9109388386915*x2x15 + 551.8197169366097*x2x16 + 597.0946323657582*x2x17 + 683.0995535059293*x2x18 + 384.6296920415791*x2x19 + 211.96697856034086*x2x20 + 131.0267148332736*x2x21 + 279.5800422061632*x2x22 + 582.4671664566167*x2x23 + 697.7922326882122*x2x24 + 736.9613287004956*x2x25 + 576.3471176296451*x2x26 + 471.3650390090466*x2x27 + 382.3885458535598*x2x28 + 201.03979705520993*x2x29 + 23.08679276123039*x3x4 + 381.08398024582453*x3x5 + 137.78606605894515*x3x6 + 169.95587662684687*x3x7 + 144.64093473149293*x3x8 + 416.10215091969906*x3x9 + 404.7715405015526*x3x10 + 275.87859648765794*x3x11 + 109.288608738514*x3x12 + 269.5514793133215*x3x13 + 282.591578076913*x3x14 + 189.2828571212935*x3x15 + 243.88931915932687*x3x16 + 278.28941769316344*x3x17 + 326.58842600435185*x3x18 + 288.0919991947017*x3x19 + 383.0469945058961*x3x20 + 274.23530042647684*x3x21 + 112.92475370794483*x3x22 + 200.35218990567586*x3x23 + 320.39506862621965*x3x24 + 353.27184999657135*x3x25 + 193.0932417253385*x3x26 + 92.19544457292888*x3x27 + 89.82204629154248*x3x28 + 184.45595680270128*x3x29 + 357.9972066930132*x4x5 + 160.822883943797*x4x6 + 174.73408368146153*x4x7 + 145.83552379307312*x4x8 + 436.7150100465978*x4x9 + 423.64725893129537*x4x10 + 293.65626163935275*x4x11 + 118.0889495253472*x4x12 + 246.48935068274247*x4x13 + 263.4406954135978*x4x14 + 167.91962362987834*x4x15 + 225.88713996153035*x4x16 + 258.6426105652354*x4x17 + 303.9161068452937*x4x18 + 289.15393824051574*x4x19 + 397.17502439101077*x4x20 + 297.06901555025894*x4x21 + 131.3202193114221*x4x22 + 180.93645293306707*x4x23 + 302.3177136722227*x4x24 + 332.34018715767735*x4x25 + 171.00292395160966*x4x26 + 76.60939890117922*x4x27 + 103.07764064044152*x4x28 + 205.29247428973133*x4x29 + 518.6231772684287*x5x6 + 438.5635643780728*x5x7 + 403.655793963124*x5x8 + 774.3087239596362*x5x9 + 747.0963793246491*x5x10 + 616.0292200861904*x5x11 + 425.7945513977369*x5x12 + 112.37882362794157*x5x13 + 209.33466029303412*x5x14 + 215.00930212434997*x5x15 + 237.00843866833097*x5x16 + 199.0226117806718*x5x17 + 84.07734534343957*x5x18 + 478.81938139553205*x5x19 + 681.7697558560368*x5x20 + 653.3911539039996*x5x21 + 472.51772453528133*x5x22 + 233.3838040653207*x5x23 + 231.19256043393784*x5x24 + 156.46085772486356*x5x25 + 202.48456731316588*x5x26 + 318.68009037277494*x5x27 + 432.1770470536352*x5x28 + 551.7435998722596*x5x29 + 211.02606474082768*x6x7 + 209.3895890439637*x6x8 + 307.25884853003015*x6x9 + 312.37317426437244*x6x10 + 203.82835916525454*x6x11 + 155.68236894394946*x6x12 + 407.304554357056*x6x13 + 401.60303783711595*x6x14 + 323.6309626719916*x6x15 + 367.2342576612373*x6x16 + 406.3988188959215*x6x17 + 463.76826109599176*x6x18 + 327.33163611236847*x6x19 + 330.6055050963308*x6x20 + 143.28293687665675*x6x21 + 97.98469268207153*x6x22 + 323.03869737231173*x6x23 + 433.6311796907598*x6x24 + 479.12628815376013*x6x25 + 326.02147168553176*x6x26 + 212.3982109152523*x6x27 + 116.05602095539895*x6x28 + 97.3498844375277*x6x29 + 36.76955262170047*x7x8 + 345.8612438536587*x7x9 + 311.0064308016797*x7x10 + 184.09236811991963*x7x11 + 64.13267497929586*x7x12 + 332.45902003104084*x7x13 + 414.1074739726391*x7x14 + 224.7420743875076*x7x15 + 219.86586820150143*x7x16 + 265.5484889808262*x7x17 + 362.0013812128346*x7x18 + 121.92620719107111*x7x19 + 246.73872821265817*x7x20 + 277.1894658893083*x7x21 + 113.05308487608819*x7x22 + 334.6072324382723*x7x23 + 457.1389285545479*x7x24 + 466.7697505194611*x7x25 + 304.7917321713304*x7x26 + 247.88101984621574*x7x27 + 247.42069436488129*x7x28 + 163.68567438844488*x7x29 + 376.19675703014775*x8x9 + 344.17582715815473*x8x10 + 214.96511344867102*x8x11 + 53.71219600798314*x8x12 + 296.5889411289639*x8x13 + 378.038357842164*x8x14 + 189.16923639957952*x8x15 + 190.68560512005095*x8x16 + 236.00847442411893*x8x17 + 328.34280866192273*x8x18 + 143.6175476743702*x8x19 + 283.365488371467*x8x20 + 293.4655005277452*x8x21 + 114.54693361238441*x8x22 + 299.0819285747636*x8x23 + 421.283752357007*x8x24 + 430.0255806344548*x8x25 + 268.28715958837836*x8x26 + 216.11339616044165*x8x27 + 228.06358762415363*x8x28 + 179.0111728356641*x8x29 + 62.64982043070834*x9x10 + 161.7714437099453*x9x11 + 348.5182922028627*x9x12 + 663.3649071212616*x9x13 + 698.0150428178464*x9x14 + 559.9758923382327*x9x15 + 565.6721665417169*x9x16 + 611.3198835307093*x9x17 + 702.917491601966*x9x18 + 379.80258029665885*x9x19 + 183.61917111238685*x9x20 + 179.13681921927719*x9x21 + 307.18886698576824*x9x22 + 616.2093800000126*x9x23 + 733.9128013599436*x9x24 + 769.0526639964262*x9x25 + 606.4931986428207*x9x26 + 505.88239740081883*x9x27 + 423.01891210677564*x9x28 + 231.65707414193074*x9x29 + 132.23085872821065*x10x11 + 324.2344830520036*x10x12 + 637.960813843609*x10x13 + 687.0589494359273*x10x14 + 532.0939766620179*x10x15 + 529.7791992896663*x10x16 + 575.4485207210112*x10x17 + 672.5027880983097*x10x18 + 329.1519405988669*x10x19 + 122.00409829181969*x10x20 + 204.1298606279836*x10x21 + 292.3285822494954*x10x22 + 604.5800195176814*x10x23 + 725.1351598150513*x10x24 + 753.9555689826822*x10x25 + 589.7567295080235*x10x26 + 496.56822290597694*x10x27 + 424.98470560715475*x10x28 + 224.51725991557976*x10x29 + 192.04426573058618*x11x12 + 506.2854925829892*x11x13 + 556.9245909456683*x11x14 + 401.0797925600341*x11x15 + 403.92697359795125*x11x16 + 449.5887009256349*x11x17 + 542.7863299678797*x11x18 + 231.93102422918759*x11x19 + 128.35108102388543*x11x20 + 153.06207890917986*x11x21 + 162.96318602678338*x11x22 + 474.3838108536167*x11x23 + 595.9144233864456*x11x24 + 622.347169994369*x11x25 + 457.9650641697465*x11x26 + 368.06657006579667*x11x27 + 307.2930197710322*x11x28 + 106.96261028976434*x11x29 + 315.0142853903613*x12x13 + 372.550667695013*x12x14 + 211.85844330590177*x12x15 + 230.41267326256167*x12x16 + 274.21342053225624*x12x17 + 355.8033164544704*x12x18 + 185.9704277566732*x12x19 + 282.36324123369883*x12x20 + 247.19425559668656*x12x21 + 62.289646009589745*x12x22 + 290.766229125736*x12x23 + 413.8900820266173*x12x24 + 432.976904695851*x12x25 + 268.47904946196456*x12x26 + 194.164878389476*x12x27 + 183.35757415498276*x12x28 + 134.16407864998737*x12x29 + 167.20047846821492*x13x14 + 107.93516572461452*x13x15 + 154.20765220960988*x13x16 + 132.23085872821065*x13x17 + 70.32780389006896*x13x18 + 386.9431482789171*x13x19 + 578.2672392588049*x13x20 + 541.1108943645471*x13x21 + 360.347054934545*x13x22 + 150.6154042586614*x13x23 + 205.91503102007877*x13x24 + 165.20593209688326*x13x25 + 105.68348972285122*x13x26 + 213.82703290276467*x13x27 + 325.88648330361906*x13x28 + 439.5383942273985*x13x29 + 228.2673870705143*x14x15 + 302.3375596911505*x14x16 + 293.2047066470796*x14x17 + 227.49505489130968*x14x18 + 501.4508949039776*x14x19 + 654.7465158364724*x14x20 + 544.8825561531586*x14x21 + 394.7378877179134*x14x22 + 82.54089895318563*x14x23 + 44.68780594300866*x14x24 + 84.69356528095862*x14x25 + 112.43220179290273*x14x26 + 192.21342304844373*x14x27 + 291.3863414781139*x14x28 + 466.51259361350577*x14x29 + 81.30190649671138*x15x16 + 96.77293009927931*x15x17 + 144.55448799674122*x15x18 + 283.73403038761495*x15x19 + 470.33286085494814*x15x20 + 448.50975463193663*x15x21 + 262.6404386228442*x15x22 + 170.60187572239644*x15x23 + 272.6554602424092*x15x24 + 257.2411320143029*x15x25 + 120.70211265756701*x15x26 + 168.61791126686393*x15x27 + 264.5600120955546*x15x28 + 341.53184331772053*x15x29 + 45.70557952810576*x16x17 + 153.73353570382747*x16x18 + 241.91940806805889*x16x19 + 451.7488240161783*x16x20 + 477.31017169132275*x16x21 + 289.9137802864845*x16x22 + 250.88044961694405*x16x23 + 345.77015487170087*x16x24 + 318.15247916682966*x16x25 + 199.88246546408217*x16x26 + 243.7580767892625*x16x27 + 328.10059433045836*x16x28 + 364.5408070436011*x16x29 + 114.94781424629178*x17x18 + 283.0441661649291*x17x19 + 496.32650543770075*x17x20 + 520.4325124355703*x17x21 + 332.6695056659086*x17x22 + 253.16002844051033*x17x23 + 334.7416914577567*x17x24 + 297.0420845604205*x17x25 + 201.12185361118767*x17x26 + 265.3846265328872*x17x27 + 358.66558240232644*x17x28 + 408.35401308178666*x17x29 + 395.63746030930895*x18x19 + 602.2001328462159*x18x20 + 592.3655965702262*x18x21 + 407.1412531296724*x18x22 + 220.56518310921152*x18x23 + 261.37520922994975*x18x24 + 203.9730374338726*x18x25 + 175.86642658563346*x18x26 + 280.14282071829007*x18x27 + 390.1281840626232*x18x28 + 486.08229755875703*x18x29 + 226.36695871968595*x19x20 + 364.66422912043345*x19x21 + 230.4886114323222*x19x22 + 427.85044115905737*x19x23 + 545.9322302264266*x19x24 + 540.5515701577417*x19x25 + 389.03470282225464*x19x26 + 356.7534162415267*x19x27 + 368.89700459613385*x19x28 + 261.1225765804252*x19x29 + 269.8332818612263*x20x21 + 274.2207140243056*x20x22 + 573.1195337798215*x20x23 + 696.2528276423731*x20x24 + 712.141839804403*x20x25 + 548.6073276944084*x20x26 + 473.7140487678194*x20x27 + 428.05723916317544*x20x28 + 233.25736858671797*x20x29 + 187.8430195668713*x21x22 + 466.0171670657638*x21x23 + 576.6749517709261*x21x24 + 622.0032154257725*x21x25 + 466.47615158762403*x21x26 + 355.0225344960514*x21x27 + 257.14781741247583*x21x28 + 114.47707194019246*x21x29 + 312.2515011973521*x22x23 + 433.17086697976356*x22x24 + 462.68888035050077*x22x25 + 299.42110814035806*x22x26 + 205.10485123467947*x22x27 + 157.54364474646383*x22x28 + 79.2464510246358*x22x29 + 123.1665539016173*x23x24 + 156.11534197509224*x23x25 + 52.03844732503075*x23x26 + 111.28791488746656*x23x27 + 217.1013588165675*x23x28 + 384.5841910427416*x23x29 + 83.00602387778854*x24x25 + 157.00318468107582*x24x26 + 228.65913495856665*x24x27 + 320.5635662392094*x24x28 + 503.0159043211258*x24x29 + 164.5600194457937*x25x26 + 267.0074905316328*x25x27 + 372.1088550411022*x25x28 + 537.5769712329575*x25x29 + 117.5457357797381*x26x27 + 230.99134182908242*x26x28 + 375.76721517450136*x26x29 + 113.59577456930342*x27x28 + 274.5541840875859*x27x29 + 202.03960007879644*x28x29;
s.t. v0: x0x1 + x0x2 + x0x3 + x0x4 + x0x5 + x0x6 + x0x7 + x0x8 + x0x9 + x0x10 + x0x11 + x0x12 + x0x13 + x0x14 + x0x15 + x0x16 + x0x17 + x0x18 + x0x19 + x0x20 + x0x21 + x0x22 + x0x23 + x0x24 + x0x25 + x0x26 + x0x27 + x0x28 + x0x29 = 2;
s.t. v1: x0x1 + x1x2 + x1x3 + x1x4 + x1x5 + x1x6 + x1x7 + x1x8 + x1x9 + x1x10 + x1x11 + x1x12 + x1x13 + x1x14 + x1x15 + x1x16 + x1x17 + x1x18 + x1x19 + x1x20 + x1x21 + x1x22 + x1x23 + x1x24 + x1x25 + x1x26 + x1x27 + x1x28 + x1x29 = 2;
s.t. v2: x0x2 + x1x2 + x2x3 + x2x4 + x2x5 + x2x6 + x2x7 + x2x8 + x2x9 + x2x10 + x2x11 + x2x12 + x2x13 + x2x14 + x2x15 + x2x16 + x2x17 + x2x18 + x2x19 + x2x20 + x2x21 + x2x22 + x2x23 + x2x24 + x2x25 + x2x26 + x2x27 + x2x28 + x2x29 = 2;
s.t. v3: x0x3 + x1x3 + x2x3 + x3x4 + x3x5 + x3x6 + x3x7 + x3x8 + x3x9 + x3x10 + x3x11 + x3x12 + x3x13 + x3x14 + x3x15 + x3x16 + x3x17 + x3x18 + x3x19 + x3x20 + x3x21 + x3x22 + x3x23 + x3x24 + x3x25 + x3x26 + x3x27 + x3x28 + x3x29 = 2;
s.t. v4: x0x4 + x1x4 + x2x4 + x3x4 + x4x5 + x4x6 + x4x7 + x4x8 + x4x9 + x4x10 + x4x11 + x4x12 + x4x13 + x4x14 + x4x15 + x4x16 + x4x17 + x4x18 + x4x19 + x4x20 + x4x21 + x4x22 + x4x23 + x4x24 + x4x25 + x4x26 + x4x27 + x4x28 + x4x29 = 2;
s.t. v5: x0x5 + x1x5 + x2x5 + x3x5 + x4x5 + x5x6 + x5x7 + x5x8 + x5x9 + x5x10 + x5x11 + x5x12 + x5x13 + x5x14 + x5x15 + x5x16 + x5x17 + x5x18 + x5x19 + x5x20 + x5x21 + x5x22 + x5x23 + x5x24 + x5x25 + x5x26 + x5x27 + x5x28 + x5x29 = 2;
s.t. v6: x0x6 + x1x6 + x2x6 + x3x6 + x4x6 + x5x6 + x6x7 + x6x8 + x6x9 + x6x10 + x6x11 + x6x12 + x6x13 + x6x14 + x6x15 + x6x16 + x6x17 + x6x18 + x6x19 + x6x20 + x6x21 + x6x22 + x6x23 + x6x24 + x6x25 + x6x26 + x6x27 + x6x28 + x6x29 = 2;
s.t. v7: x0x7 + x1x7 + x2x7 + x3x7 + x4x7 + x5x7 + x6x7 + x7x8 + x7x9 + x7x10 + x7x11 + x7x12 + x7x13 + x7x14 + x7x15 + x7x16 + x7x17 + x7x18 + x7x19 + x7x20 + x7x21 + x7x22 + x7x23 + x7x24 + x7x25 + x7x26 + x7x27 + x7x28 + x7x29 = 2;
s.t. v8: x0x8 + x1x8 + x2x8 + x3x8 + x4x8 + x5x8 + x6x8 + x7x8 + x8x9 + x8x10 + x8x11 + x8x12 + x8x13 + x8x14 + x8x15 + x8x16 + x8x17 + x8x18 + x8x19 + x8x20 + x8x21 + x8x22 + x8x23 + x8x24 + x8x25 + x8x26 + x8x27 + x8x28 + x8x29 = 2;
s.t. v9: x0x9 + x1x9 + x2x9 + x3x9 + x4x9 + x5x9 + x6x9 + x7x9 + x8x9 + x9x10 + x9x11 + x9x12 + x9x13 + x9x14 + x9x15 + x9x16 + x9x17 + x9x18 + x9x19 + x9x20 + x9x21 + x9x22 + x9x23 + x9x24 + x9x25 + x9x26 + x9x27 + x9x28 + x9x29 = 2;
s.t. v10: x0x10 + x1x10 + x2x10 + x3x10 + x4x10 + x5x10 + x6x10 + x7x10 + x8x10 + x9x10 + x10x11 + x10x12 + x10x13 + x10x14 + x10x15 + x10x16 + x10x17 + x10x18 + x10x19 + x10x20 + x10x21 + x10x22 + x10x23 + x10x24 + x10x25 + x10x26 + x10x27 + x10x28 + x10x29 = 2;
s.t. v11: x0x11 + x1x11 + x2x11 + x3x11 + x4x11 + x5x11 + x6x11 + x7x11 + x8x11 + x9x11 + x10x11 + x11x12 + x11x13 + x11x14 + x11x15 + x11x16 + x11x17 + x11x18 + x11x19 + x11x20 + x11x21 + x11x22 + x11x23 + x11x24 + x11x25 + x11x26 + x11x27 + x11x28 + x11x29 = 2;
s.t. v12: x0x12 + x1x12 + x2x12 + x3x12 + x4x12 + x5x12 + x6x12 + x7x12 + x8x12 + x9x12 + x10x12 + x11x12 + x12x13 + x12x14 + x12x15 + x12x16 + x12x17 + x12x18 + x12x19 + x12x20 + x12x21 + x12x22 + x12x23 + x12x24 + x12x25 + x12x26 + x12x27 + x12x28 + x12x29 = 2;
s.t. v13: x0x13 + x1x13 + x2x13 + x3x13 + x4x13 + x5x13 + x6x13 + x7x13 + x8x13 + x9x13 + x10x13 + x11x13 + x12x13 + x13x14 + x13x15 + x13x16 + x13x17 + x13x18 + x13x19 + x13x20 + x13x21 + x13x22 + x13x23 + x13x24 + x13x25 + x13x26 + x13x27 + x13x28 + x13x29 = 2;
s.t. v14: x0x14 + x1x14 + x2x14 + x3x14 + x4x14 + x5x14 + x6x14 + x7x14 + x8x14 + x9x14 + x10x14 + x11x14 + x12x14 + x13x14 + x14x15 + x14x16 + x14x17 + x14x18 + x14x19 + x14x20 + x14x21 + x14x22 + x14x23 + x14x24 + x14x25 + x14x26 + x14x27 + x14x28 + x14x29 = 2;
s.t. v15: x0x15 + x1x15 + x2x15 + x3x15 + x4x15 + x5x15 + x6x15 + x7x15 + x8x15 + x9x15 + x10x15 + x11x15 + x12x15 + x13x15 + x14x15 + x15x16 + x15x17 + x15x18 + x15x19 + x15x20 + x15x21 + x15x22 + x15x23 + x15x24 + x15x25 + x15x26 + x15x27 + x15x28 + x15x29 = 2;
s.t. v16: x0x16 + x1x16 + x2x16 + x3x16 + x4x16 + x5x16 + x6x16 + x7x16 + x8x16 + x9x16 + x10x16 + x11x16 + x12x16 + x13x16 + x14x16 + x15x16 + x16x17 + x16x18 + x16x19 + x16x20 + x16x21 + x16x22 + x16x23 + x16x24 + x16x25 + x16x26 + x16x27 + x16x28 + x16x29 = 2;
s.t. v17: x0x17 + x1x17 + x2x17 + x3x17 + x4x17 + x5x17 + x6x17 + x7x17 + x8x17 + x9x17 + x10x17 + x11x17 + x12x17 + x13x17 + x14x17 + x15x17 + x16x17 + x17x18 + x17x19 + x17x20 + x17x21 + x17x22 + x17x23 + x17x24 + x17x25 + x17x26 + x17x27 + x17x28 + x17x29 = 2;
s.t. v18: x0x18 + x1x18 + x2x18 + x3x18 + x4x18 + x5x18 + x6x18 + x7x18 + x8x18 + x9x18 + x10x18 + x11x18 + x12x18 + x13x18 + x14x18 + x15x18 + x16x18 + x17x18 + x18x19 + x18x20 + x18x21 + x18x22 + x18x23 + x18x24 + x18x25 + x18x26 + x18x27 + x18x28 + x18x29 = 2;
s.t. v19: x0x19 + x1x19 + x2x19 + x3x19 + x4x19 + x5x19 + x6x19 + x7x19 + x8x19 + x9x19 + x10x19 + x11x19 + x12x19 + x13x19 + x14x19 + x15x19 + x16x19 + x17x19 + x18x19 + x19x20 + x19x21 + x19x22 + x19x23 + x19x24 + x19x25 + x19x26 + x19x27 + x19x28 + x19x29 = 2;
s.t. v20: x0x20 + x1x20 + x2x20 + x3x20 + x4x20 + x5x20 + x6x20 + x7x20 + x8x20 + x9x20 + x10x20 + x11x20 + x12x20 + x13x20 + x14x20 + x15x20 + x16x20 + x17x20 + x18x20 + x19x20 + x20x21 + x20x22 + x20x23 + x20x24 + x20x25 + x20x26 + x20x27 + x20x28 + x20x29 = 2;
s.t. v21: x0x21 + x1x21 + x2x21 + x3x21 + x4x21 + x5x21 + x6x21 + x7x21 + x8x21 + x9x21 + x10x21 + x11x21 + x12x21 + x13x21 + x14x21 + x15x21 + x16x21 + x17x21 + x18x21 + x19x21 + x20x21 + x21x22 + x21x23 + x21x24 + x21x25 + x21x26 + x21x27 + x21x28 + x21x29 = 2;
s.t. v22: x0x22 + x1x22 + x2x22 + x3x22 + x4x22 + x5x22 + x6x22 + x7x22 + x8x22 + x9x22 + x10x22 + x11x22 + x12x22 + x13x22 + x14x22 + x15x22 + x16x22 + x17x22 + x18x22 + x19x22 + x20x22 + x21x22 + x22x23 + x22x24 + x22x25 + x22x26 + x22x27 + x22x28 + x22x29 = 2;
s.t. v23: x0x23 + x1x23 + x2x23 + x3x23 + x4x23 + x5x23 + x6x23 + x7x23 + x8x23 + x9x23 + x10x23 + x11x23 + x12x23 + x13x23 + x14x23 + x15x23 + x16x23 + x17x23 + x18x23 + x19x23 + x20x23 + x21x23 + x22x23 + x23x24 + x23x25 + x23x26 + x23x27 + x23x28 + x23x29 = 2;
s.t. v24: x0x24 + x1x24 + x2x24 + x3x24 + x4x24 + x5x24 + x6x24 + x7x24 + x8x24 + x9x24 + x10x24 + x11x24 + x12x24 + x13x24 + x14x24 + x15x24 + x16x24 + x17x24 + x18x24 + x19x24 + x20x24 + x21x24 + x22x24 + x23x24 + x24x25 + x24x26 + x24x27 + x24x28 + x24x29 = 2;
s.t. v25: x0x25 + x1x25 + x2x25 + x3x25 + x4x25 + x5x25 + x6x25 + x7x25 + x8x25 + x9x25 + x10x25 + x11x25 + x12x25 + x13x25 + x14x25 + x15x25 + x16x25 + x17x25 + x18x25 + x19x25 + x20x25 + x21x25 + x22x25 + x23x25 + x24x25 + x25x26 + x25x27 + x25x28 + x25x29 = 2;
s.t. v26: x0x26 + x1x26 + x2x26 + x3x26 + x4x26 + x5x26 + x6x26 + x7x26 + x8x26 + x9x26 + x10x26 + x11x26 + x12x26 + x13x26 + x14x26 + x15x26 + x16x26 + x17x26 + x18x26 + x19x26 + x20x26 + x21x26 + x22x26 + x23x26 + x24x26 + x25x26 + x26x27 + x26x28 + x26x29 = 2;
s.t. v27: x0x27 + x1x27 + x2x27 + x3x27 + x4x27 + x5x27 + x6x27 + x7x27 + x8x27 + x9x27 + x10x27 + x11x27 + x12x27 + x13x27 + x14x27 + x15x27 + x16x27 + x17x27 + x18x27 + x19x27 + x20x27 + x21x27 + x22x27 + x23x27 + x24x27 + x25x27 + x26x27 + x27x28 + x27x29 = 2;
s.t. v28: x0x28 + x1x28 + x2x28 + x3x28 + x4x28 + x5x28 + x6x28 + x7x28 + x8x28 + x9x28 + x10x28 + x11x28 + x12x28 + x13x28 + x14x28 + x15x28 + x16x28 + x17x28 + x18x28 + x19x28 + x20x28 + x21x28 + x22x28 + x23x28 + x24x28 + x25x28 + x26x28 + x27x28 + x28x29 = 2;
s.t. v29: x0x29 + x1x29 + x2x29 + x3x29 + x4x29 + x5x29 + x6x29 + x7x29 + x8x29 + x9x29 + x10x29 + x11x29 + x12x29 + x13x29 + x14x29 + x15x29 + x16x29 + x17x29 + x18x29 + x19x29 + x20x29 + x21x29 + x22x29 + x23x29 + x24x29 + x25x29 + x26x29 + x27x29 + x28x29 = 2;

これをGLPKで解く．

Problem:    tsp
Rows:       31
Columns:    435
Non-zeros:  1305
Status:     OPTIMAL
Objective:  route = 2482.464894 (MINimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 route        B        2482.46
(省略)

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
    11 x0x11        NU             1             0             1      -46.5473
    20 x0x20        B              1             0             1
    32 x1x4         NU             1             0             1      -1.51219
    55 x1x27        NU             1             0             1       -26.134
    64 x2x9         B              1             0             1
    65 x2x10        B              1             0             1
    85 x3x4         NU             1             0             1      -44.7223
   109 x3x28        B              1             0             1
   143 x5x13        B            0.5             0             1
   148 x5x18        NU             1             0             1       -41.133
   155 x5x25        B            0.5             0             1
   174 x6x21        B              1             0             1
   181 x6x28        B              1             0             1
   183 x7x8         B            0.5             0             1
   187 x7x12        B            0.5             0             1
   194 x7x19        NU             1             0             1      -32.1118
   208 x8x12        B            0.5             0             1
   215 x8x19        B              1             0             1
   226 x9x10        NU             1             0             1     -0.257966
   273 x11x20       NU             1             0             1      -5.09275
   292 x12x22       NU             1             0             1      -18.1886
   304 x13x18       B              1             0             1
   312 x13x26       B            0.5             0             1
   324 x14x23       B            0.5             0             1
   325 x14x24       B              1             0             1
   326 x14x25       B            0.5             0             1
   331 x15x16       B              1             0             1
   332 x15x17       NU             1             0             1       -20.362
   345 x16x17       NU             1             0             1      -65.1977
   407 x21x29       NU             1             0             1      -10.0676
   414 x22x29       B              1             0             1
   417 x23x26       NU             1             0             1      -95.5744
   418 x23x27       B            0.5             0             1
   421 x24x25       NU             1             0             1      -22.6486
   430 x26x27       B            0.5             0             1
（Activityが0の変数は省略）

頂点数30とかなり小規模な問題なのに，小数が残ってしまったので，やっぱり分枝するか，切除平面を加えるかしないと解けない．

調べてみたらGLPKってIPも解けるらしい．（内部的には整数計画問題に緩和して分枝しているみたい）

var x1 >= 0, <= 1, integer;
(以下略)

とすると，普通に解けた．

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
    11 x0x11        *              1             0             1
    20 x0x20        *              1             0             1
    55 x1x27        *              1             0             1
    56 x1x28        *              1             0             1
    64 x2x9         *              1             0             1
    65 x2x10        *              1             0             1
    85 x3x4         *              1             0             1
   109 x3x28        *              1             0             1
   133 x4x27        *              1             0             1
   148 x5x18        *              1             0             1
   155 x5x25        *              1             0             1
   174 x6x21        *              1             0             1
   175 x6x22        *              1             0             1
   187 x7x12        *              1             0             1
   194 x7x19        *              1             0             1
   208 x8x12        *              1             0             1
   215 x8x19        *              1             0             1
   226 x9x10        *              1             0             1
   273 x11x20       *              1             0             1
   304 x13x18       *              1             0             1
   312 x13x26       *              1             0             1
   324 x14x23       *              1             0             1
   325 x14x24       *              1             0             1
   331 x15x16       *              1             0             1
   332 x15x17       *              1             0             1
   345 x16x17       *              1             0             1
   407 x21x29       *              1             0             1
   414 x22x29       *              1             0             1
   417 x23x26       *              1             0             1
   421 x24x25       *              1             0             1

頂点数200でも80secくらいで解けた，メモリは3Gも使ってたけど．最大クリーク問題だと頂点数100，辺密度0.5でも解くのが難しかったので，TSPは比較的解きやすいのかもしれないなぁ．とおもったけど，複数のひとつの巡回路となっている保証はないので，解けていないですね．分枝しないといけないんだけっけなぁ．

Comments: 0
Trackbacks: 0

最短経路問題をあえてLPで解いてみる

2009-03-28 (Sat)
Algorithm

ちょっと一度，自分でシンプレックス法を実装してみるかなーと思っていろいろ調べてたら，最短経路問題が線形計画問題に緩和して簡単に解ける（最適解が小数にならない）ということを知った．よく考えれば確かにそうなのだけど，せっかくなので基本の基本なのかもしれないけど，試してみた．

とりあえず，GLPKを使ってみた．まず定式化して.modに記述する．たいした問題じゃないので（面倒なので）最短経路を求めるグラフは描画しないが，頂点はv1からv6からなる有向グラフにおいて，v1から，v6の最短経路を求める．その最短経路問題の定式化を以下に示す．

var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;
var x5 >= 0;
var x6 >= 0;
var x7 >= 0;
var x8 >= 0;
var x9 >= 0;
var x10 >= 0;

minimize profit: 8*x1 + 4*x2 + 6*x3 + 5*x4 + 3*x5 + 9*x6 + x7 + 7*x8 + x9 + 2*x10;
s.t. v1: - x1 - x2                                          = -1;
s.t. v2:   x1      - x3 - x4 + x5                           =  0;
s.t. v3:        x2           - x5 - x6                      =  0;
s.t. v4:             x3                - x7 - x8 + x9       =  0;
s.t. v5:                  x4      + x6 + x7      - x9 - x10 =  0;
s.t. v6:                                      x8      + x10 =  1;

結果は，以下の通りちゃんと整数で出力された．

Problem:    path
Rows:       7
Columns:    10
Non-zeros:  30
Status:     OPTIMAL
Objective:  profit = 14 (MINimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 profit       B             14
     2 v1           NS            -1            -1             =            -4
     3 v2           NS             0            -0             =             3
     4 v3           B              0            -0             =
     5 v4           NS             0            -0             =             7
     6 v5           NS             0            -0             =             8
     7 v6           NS             1             1             =            10

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           NL             0             0                           1
     2 x2           B              1             0
     3 x3           NL             0             0                           2
     4 x4           B              1             0
     5 x5           B              1             0
     6 x6           NL             0             0                           1
     7 x7           B              0             0
     8 x8           NL             0             0                           4
     9 x9           NL             0             0                           2
    10 x10          B              1             0
（以下略）