Resource Allocation (dcmpe06)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: dcmpe06 */
/* TITLE: Resource Allocation (dcmpe06) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: OPTMODEL */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 6 from the Decomposition Algorithm */
/* chapter of Mathematical Programming. */
/* */
/***************************************************************/
data TaskData;
input profit weight start end;
datalines;
100 74 1 12
98 32 1 9
73 27 1 22
98 51 1 31
37 61 1 6
29 32 1 2
66 76 1 14
97 59 1 5
94 12 1 4
58 36 1 19
80 57 2 3
43 42 3 7
83 58 4 10
11 95 5 33
39 42 6 8
26 97 7 13
78 97 8 27
43 78 9 11
91 49 10 17
12 62 11 25
56 53 12 40
13 40 13 15
74 47 14 18
20 85 15 16
63 58 16 53
85 13 17 24
70 27 18 20
69 85 19 21
71 80 20 26
29 56 21 28
92 16 22 23
11 86 23 48
37 96 24 32
98 27 25 43
67 61 26 30
27 54 27 51
87 68 28 29
33 49 29 38
28 91 30 36
86 98 31 42
99 54 32 35
59 52 33 34
14 83 34 39
100 50 35 44
38 87 36 37
82 90 37 46
17 32 38 41
81 51 39 45
56 87 40 47
87 64 41 61
26 65 42 62
15 32 43 55
63 33 44 50
88 81 45 49
67 57 46 56
75 61 47 57
50 22 48 54
37 59 49 71
92 52 50 52
71 19 51 58
37 31 52 59
42 75 53 74
99 22 54 66
63 72 55 60
72 54 56 64
45 98 57 90
19 97 58 84
75 91 59 70
24 10 60 63
91 27 61 73
92 55 62 75
36 31 63 85
81 36 64 65
11 70 65 67
41 69 66 68
30 27 67 76
92 69 68 69
72 85 69 82
19 29 70 77
78 22 71 72
19 46 72 80
16 85 73 81
28 39 74 94
26 14 75 95
36 89 76 98
74 77 77 78
18 72 78 79
79 14 79 83
25 91 80 86
82 29 81 93
86 32 82 100
55 33 83 104
39 26 84 87
66 27 85 103
37 41 86 89
98 10 87 88
39 96 88 99
65 78 89 97
55 42 90 91
96 31 91 92
13 90 92 112
87 45 93 102
61 86 94 105
31 27 95 96
65 19 96 110
24 15 97 107
19 16 98 101
59 10 99 147
36 98 100 129
46 34 101 113
42 64 102 106
25 78 103 111
50 27 104 115
17 78 105 116
44 36 106 108
83 43 107 109
40 46 108 118
31 87 109 120
14 24 110 119
41 30 111 127
91 38 112 122
66 23 113 114
92 52 114 149
74 70 115 117
52 68 116 125
65 73 117 124
64 23 118 121
44 11 119 123
54 94 120 139
90 90 121 132
37 52 122 126
63 84 123 137
97 22 124 150
89 69 125 128
35 18 126 172
82 85 127 130
62 45 128 168
31 87 129 133
64 80 130 131
54 52 131 134
14 98 132 138
91 23 133 135
64 61 134 136
10 55 135 140
86 76 136 141
41 51 137 144
18 48 138 143
63 84 139 148
39 98 140 145
23 85 141 142
43 37 142 146
57 13 143 153
76 24 144 161
18 63 145 158
63 87 146 160
75 90 147 152
41 93 148 181
25 86 149 151
99 84 150 156
72 48 151 154
25 96 152 179
41 44 153 157
82 18 154 155
21 21 155 159
60 16 156 169
79 62 157 164
78 70 158 163
87 10 159 162
77 86 160 173
60 28 161 167
48 71 162 165
52 84 163 176
92 72 164 166
73 21 165 180
73 77 166 174
40 22 167 235
45 79 168 170
99 32 169 171
81 59 170 178
94 75 171 186
89 71 172 183
49 46 173 175
11 50 174 216
38 42 175 199
97 89 176 177
40 82 177 184
15 42 178 185
19 45 179 189
55 89 180 182
99 46 181 193
26 68 182 188
10 41 183 191
68 72 184 187
55 53 185 202
50 23 186 192
100 77 187 190
67 60 188 206
35 98 189 196
98 99 190 194
59 83 191 215
32 92 192 207
45 56 193 197
81 53 194 195
20 75 195 222
40 28 196 198
80 81 197 203
70 24 198 201
21 81 199 200
28 65 200 204
44 38 201 212
76 54 202 205
44 70 203 210
64 61 204 213
66 37 205 218
86 97 206 208
71 36 207 209
61 10 208 221
85 85 209 232
92 81 210 211
34 54 211 214
68 66 212 219
93 17 213 224
22 14 214 226
31 62 215 217
89 71 216 240
44 52 217 242
70 53 218 230
71 14 219 220
77 85 220 225
22 58 221 223
84 34 222 251
87 17 223 228
32 42 224 257
12 77 225 229
26 27 226 227
84 54 227 234
24 59 228 231
78 90 229 249
45 36 230 239
42 34 231 233
53 20 232 237
71 80 233 243
52 23 234 238
58 91 235 236
29 74 236 247
72 31 237 241
68 11 238 267
66 73 239 248
83 35 240 245
67 14 241 253
52 92 242 244
99 83 243 246
55 43 244 250
67 61 245 293
78 32 246 254
52 30 247 252
26 55 248 255
48 48 249 261
83 86 250 260
82 50 251 259
59 91 252 271
27 97 253 256
26 81 254 262
75 85 255 264
96 61 256 283
62 29 257 258
99 50 258 268
30 74 259 270
89 81 260 266
46 19 261 282
72 50 262 263
18 60 263 265
41 65 264 288
21 92 265 278
43 27 266 269
80 12 267 273
38 33 268 274
25 80 269 276
51 23 270 279
28 57 271 272
78 17 272 275
20 65 273 277
22 66 274 280
51 71 275 319
64 98 276 285
10 60 277 284
91 71 278 289
73 26 279 297
64 74 280 281
76 74 281 298
28 10 282 287
84 47 283 300
59 86 284 286
23 97 285 290
88 11 286 295
31 15 287 291
50 30 288 296
57 17 289 299
57 31 290 310
77 67 291 292
33 23 292 306
67 35 293 294
51 100 294 304
39 67 295 331
89 94 296 305
24 92 297 312
73 57 298 302
72 57 299 308
59 21 300 301
15 83 301 307
16 64 302 303
50 83 303 309
61 28 304 318
57 71 305 316
27 74 306 322
44 66 307 326
61 77 308 314
74 83 309 313
51 66 310 311
95 52 311 317
33 89 312 333
78 53 313 321
43 99 314 315
36 50 315 336
64 79 316 320
87 25 317 345
87 31 318 332
47 65 319 324
93 89 320 325
11 69 321 343
34 42 322 323
98 98 323 347
85 65 324 329
20 92 325 330
57 31 326 327
18 51 327 328
29 45 328 350
96 90 329 337
92 15 330 334
84 78 331 335
54 56 332 341
98 99 333 344
48 69 334 357
37 46 335 338
47 13 336 339
23 56 337 340
26 97 338 371
39 14 339 351
20 73 340 352
65 88 341 342
44 48 342 368
34 91 343 346
45 66 344 354
65 86 345 380
60 50 346 348
73 94 347 363
30 68 348 349
95 40 349 376
12 77 350 358
33 55 351 355
44 19 352 353
37 100 353 356
59 53 354 360
49 93 355 359
36 28 356 375
54 93 357 365
96 44 358 370
47 12 359 362
66 78 360 361
77 30 361 366
50 49 362 364
63 19 363 372
89 57 364 373
74 93 365 367
39 69 366 378
81 40 367 369
44 37 368 398
30 26 369 382
45 33 370 381
66 55 371 374
90 81 372 379
43 61 373 385
54 45 374 377
65 53 375 399
11 51 376 408
66 22 377 401
36 39 378 388
59 49 379 395
17 79 380 384
31 28 381 393
35 82 382 383
75 67 383 389
20 52 384 386
75 46 385 387
83 67 386 402
61 19 387 390
30 18 388 404
81 84 389 391
60 100 390 397
30 22 391 392
14 57 392 394
81 94 393 400
73 71 394 415
68 35 395 396
44 27 396 412
99 43 397 423
80 97 398 429
13 52 399 407
74 52 400 414
13 12 401 405
37 47 402 403
10 36 403 430
54 29 404 406
80 68 405 409
75 86 406 411
12 27 407 410
44 17 408 418
11 44 409 413
83 45 410 416
40 34 411 426
81 12 412 422
61 50 413 419
47 91 414 417
95 14 415 450
29 61 416 436
54 13 417 420
45 63 418 432
96 89 419 421
42 38 420 428
60 50 421 424
23 26 422 433
74 96 423 425
88 42 424 431
40 46 425 439
99 53 426 427
44 55 427 448
53 57 428 435
73 11 429 442
72 92 430 471
100 86 431 469
45 23 432 434
85 37 433 467
24 33 434 438
76 98 435 441
60 95 436 437
63 78 437 440
98 26 438 444
51 99 439 453
64 100 440 446
21 99 441 445
69 53 442 443
71 11 443 449
10 58 444 459
64 82 445 454
47 36 446 447
82 67 447 472
81 11 448 468
90 20 449 452
79 21 450 451
14 81 451 464
32 96 452 455
70 44 453 457
76 42 454 456
76 32 455 461
10 78 456 473
85 66 457 458
74 82 458 466
44 37 459 460
10 77 460 462
60 67 461 484
84 80 462 463
65 45 463 498
63 11 464 465
83 100 465 475
60 75 466 478
59 95 467 481
82 32 468 480
71 57 469 470
19 61 470 486
14 83 471 474
76 76 472 482
24 15 473 477
22 41 474 476
97 98 475 490
49 41 476 497
20 85 477 485
23 28 478 479
50 41 479 505
17 42 480 493
19 83 481 483
32 18 482 492
49 27 483 496
67 12 484 508
85 52 485 487
19 89 486 491
37 12 487 488
77 36 488 489
39 10 489 500
36 41 490 527
20 16 491 504
51 86 492 494
34 92 493 495
21 92 494 499
99 15 495 506
61 54 496 511
44 60 497 501
77 44 498 517
88 69 499 507
79 100 500 502
65 75 501 526
12 61 502 503
70 66 503 532
15 97 504 514
51 80 505 524
74 11 506 520
83 82 507 510
60 70 508 509
99 44 509 522
59 24 510 512
85 26 511 519
14 19 512 513
57 46 513 515
29 33 514 516
60 68 515 531
18 82 516 518
85 29 517 521
25 14 518 537
59 41 519 528
20 61 520 525
19 68 521 523
20 96 522 529
23 48 523 533
53 88 524 536
68 48 525 530
61 70 526 540
17 82 527 554
45 32 528 534
77 11 529 538
20 38 530 535
32 71 531 544
16 45 532 550
43 14 533 542
62 31 534 545
58 37 535 541
69 23 536 549
23 38 537 555
64 17 538 539
74 74 539 553
25 53 540 548
84 28 541 561
51 36 542 543
96 15 543 565
95 96 544 546
50 15 545 547
17 61 546 597
100 61 547 552
31 21 548 560
51 59 549 556
93 32 550 551
51 10 551 562
46 23 552 568
61 76 553 558
57 57 554 564
100 71 555 557
83 99 556 583
54 13 557 559
94 44 558 563
94 60 559 569
30 83 560 572
22 63 561 574
13 29 562 576
21 37 563 578
49 53 564 571
63 34 565 566
71 24 566 567
55 98 567 570
59 13 568 586
69 10 569 573
50 59 570 585
18 44 571 580
93 90 572 575
60 79 573 577
82 22 574 589
84 92 575 581
98 43 576 588
95 93 577 579
31 82 578 587
28 41 579 602
78 24 580 584
55 13 581 582
25 66 582 593
100 16 583 598
66 66 584 590
99 60 585 591
100 83 586 600
19 33 587 596
14 25 588 616
48 41 589 592
23 32 590 603
69 34 591 599
31 78 592 595
88 62 593 594
15 98 594 607
16 19 595 617
61 35 596 645
17 10 597 626
26 55 598 601
59 47 599 610
14 18 600 605
26 97 601 604
51 27 602 615
58 18 603 606
33 96 604 613
85 11 605 609
41 84 606 608
58 77 607 611
29 20 608 614
48 28 609 644
17 82 610 612
80 48 611 620
41 13 612 622
71 51 613 629
84 80 614 623
24 51 615 618
90 69 616 624
47 31 617 639
96 73 618 619
17 77 619 625
85 62 620 621
48 22 621 637
12 89 622 627
18 90 623 634
48 80 624 628
31 18 625 655
44 50 626 636
63 50 627 633
94 10 628 631
63 94 629 630
23 66 630 632
89 70 631 638
35 89 632 640
100 49 633 635
11 86 634 643
69 51 635 650
11 74 636 649
44 55 637 642
20 80 638 653
13 52 639 641
73 62 640 687
23 31 641 672
17 40 642 646
23 41 643 648
56 86 644 668
70 45 645 647
71 81 646 660
10 18 647 693
55 71 648 652
38 96 649 657
64 14 650 651
43 61 651 661
78 34 652 654
20 14 653 664
72 34 654 681
37 49 655 656
11 42 656 658
43 41 657 662
61 42 658 659
31 85 659 671
38 64 660 669
92 87 661 663
35 90 662 666
35 74 663 667
37 12 664 665
35 57 665 675
66 34 666 674
85 77 667 670
84 36 668 690
20 16 669 678
97 39 670 673
37 13 671 695
80 39 672 692
40 17 673 676
53 34 674 677
84 59 675 680
98 62 676 685
44 70 677 679
76 19 678 688
65 93 679 682
58 38 680 683
92 11 681 697
51 60 682 684
62 13 683 686
57 40 684 691
30 91 685 700
77 12 686 708
45 81 687 717
29 12 688 689
63 67 689 724
88 62 690 694
50 73 691 705
33 35 692 696
79 49 693 706
52 70 694 698
97 43 695 702
31 13 696 711
46 60 697 703
65 37 698 699
57 59 699 707
30 85 700 701
74 35 701 704
82 83 702 710
52 48 703 735
43 19 704 709
33 14 705 727
77 53 706 726
48 54 707 746
36 41 708 715
62 99 709 712
91 12 710 714
87 97 711 713
14 19 712 722
44 64 713 720
93 25 714 716
16 81 715 733
70 82 716 732
74 23 717 718
37 33 718 719
46 97 719 721
23 50 720 729
35 100 721 723
72 91 722 725
81 59 723 734
53 98 724 742
90 37 725 736
77 21 726 731
92 76 727 728
38 66 728 730
60 68 729 737
47 92 730 749
53 39 731 741
94 36 732 744
87 84 733 740
54 50 734 739
48 63 735 738
78 39 736 777
29 36 737 756
35 80 738 745
50 58 739 748
36 33 740 743
99 91 741 752
98 95 742 762
90 23 743 755
29 79 744 750
14 85 745 767
46 72 746 747
51 27 747 758
99 79 748 757
22 80 749 761
18 53 750 751
25 92 751 753
85 31 752 768
63 82 753 754
52 35 754 779
79 76 755 771
57 85 756 760
26 38 757 765
94 77 758 759
12 75 759 776
68 27 760 766
18 21 761 764
44 83 762 763
12 48 763 785
58 90 764 784
55 61 765 781
97 71 766 770
36 57 767 769
22 74 768 772
44 94 769 783
52 90 770 774
40 30 771 775
52 45 772 773
35 42 773 780
97 23 774 778
64 47 775 809
24 78 776 782
36 98 777 790
20 89 778 802
33 65 779 789
16 42 780 786
43 33 781 791
20 89 782 787
86 53 783 794
62 89 784 788
82 27 785 800
64 51 786 797
95 78 787 796
26 95 788 801
35 17 789 793
88 80 790 798
47 30 791 792
45 58 792 803
37 11 793 795
85 81 794 820
79 44 795 799
66 61 796 806
34 14 797 813
98 83 798 807
99 15 799 822
54 80 800 811
23 37 801 805
67 82 802 808
63 100 803 804
48 73 804 815
43 86 805 810
68 87 806 814
24 72 807 816
24 72 808 817
22 24 809 832
71 65 810 812
10 74 811 831
54 70 812 824
22 54 813 819
27 88 814 828
41 75 815 838
47 90 816 826
23 34 817 818
58 25 818 823
78 16 819 821
10 42 820 836
10 27 821 829
52 64 822 825
16 34 823 850
68 99 824 827
33 68 825 835
38 78 826 834
20 65 827 830
14 44 828 868
10 17 829 837
68 28 830 839
64 37 831 841
13 15 832 833
81 58 833 845
32 24 834 840
86 39 835 852
95 47 836 846
95 22 837 842
98 65 838 848
49 93 839 892
32 27 840 844
15 78 841 843
50 77 842 871
23 76 843 866
100 69 844 851
30 12 845 849
33 68 846 847
84 61 847 875
52 12 848 853
12 49 849 858
52 49 850 864
77 25 851 854
63 18 852 855
22 58 853 856
72 60 854 861
100 78 855 860
62 41 856 857
49 21 857 859
14 55 858 872
69 70 859 863
32 60 860 867
48 39 861 862
67 24 862 865
23 10 863 869
95 24 864 879
49 82 865 876
75 96 866 878
53 66 867 884
59 63 868 874
82 90 869 870
82 59 870 885
57 19 871 873
56 76 872 890
36 81 873 883
65 16 874 881
35 34 875 877
14 54 876 903
44 70 877 887
26 76 878 880
26 97 879 891
94 83 880 882
62 73 881 886
96 93 882 925
50 56 883 894
65 45 884 888
43 80 885 897
46 88 886 911
27 72 887 889
36 10 888 898
100 80 889 900
62 94 890 893
92 82 891 896
89 21 892 907
36 57 893 895
96 95 894 904
62 40 895 901
30 66 896 909
49 52 897 902
40 91 898 899
23 36 899 923
92 37 900 906
67 96 901 913
98 14 902 915
43 29 903 905
25 100 904 910
100 58 905 919
83 50 906 918
89 71 907 908
56 29 908 916
51 98 909 943
93 46 910 945
54 95 911 912
95 76 912 914
17 53 913 931
43 65 914 917
47 53 915 920
76 32 916 921
59 60 917 928
46 94 918 922
75 97 919 924
96 73 920 929
24 75 921 933
29 76 922 947
51 67 923 930
75 15 924 927
46 41 925 926
53 96 926 932
12 16 927 956
32 22 928 942
10 58 929 939
64 92 930 936
33 86 931 938
70 61 932 934
39 91 933 935
59 54 934 937
15 31 935 959
47 51 936 950
56 35 937 941
37 71 938 944
48 55 939 940
87 10 940 954
19 86 941 965
33 83 942 949
79 35 943 946
65 46 944 948
89 80 945 952
100 20 946 990
17 59 947 962
66 75 948 958
49 66 949 951
70 16 950 955
67 65 951 953
76 92 952 957
41 27 953 998
48 84 954 971
68 63 955 960
35 60 956 974
56 49 957 963
20 58 958 976
44 34 959 964
94 32 960 961
56 37 961 966
83 80 962 968
39 86 963 970
52 53 964 973
54 56 965 967
33 27 966 992
68 96 967 969
33 84 968 984
19 14 969 977
52 64 970 979
53 28 971 972
85 77 972 994
19 93 973 975
22 55 974 986
97 18 975 981
24 54 976 978
16 84 977 980
45 55 978 1008
92 27 979 985
80 84 980 983
76 64 981 982
14 66 982 989
81 47 983 991
75 33 984 988
71 46 985 997
55 99 986 987
29 13 987 993
32 71 988 1003
49 61 989 1024
77 92 990 995
73 91 991 996
59 51 992 1014
16 10 993 1001
51 40 994 1013
96 57 995 1010
14 23 996 1000
19 41 997 999
17 56 998 1018
13 50 999 1002
92 59 1000 1007
11 22 1001 1004
75 19 1002 1012
59 17 1003 1005
100 70 1004 1021
36 84 1005 1006
50 76 1006 1009
26 31 1007 1016
64 56 1008 1011
25 90 1009 1030
84 50 1010 1037
64 89 1011 1017
14 81 1012 1015
26 41 1013 1022
52 98 1014 1032
46 63 1015 1034
11 33 1016 1047
55 53 1017 1025
85 21 1018 1019
50 55 1019 1020
35 50 1020 1043
85 43 1021 1027
32 56 1022 1023
11 87 1023 1049
20 38 1024 1026
21 81 1025 1028
77 45 1026 1046
62 52 1027 1029
92 61 1028 1041
79 42 1029 1033
88 71 1030 1031
34 72 1031 1036
54 39 1032 1038
55 83 1033 1050
53 89 1034 1035
18 78 1035 1042
12 87 1036 1055
41 37 1037 1039
21 80 1038 1058
45 77 1039 1040
24 96 1040 1061
27 29 1041 1056
71 87 1042 1044
66 10 1043 1064
94 66 1044 1045
70 45 1045 1048
87 43 1046 1051
42 86 1047 1065
97 65 1048 1052
10 76 1049 1054
92 12 1050 1057
99 56 1051 1053
10 12 1052 1066
55 73 1053 1070
49 61 1054 1063
40 15 1055 1060
100 64 1056 1069
83 91 1057 1076
33 79 1058 1059
73 19 1059 1062
76 12 1060 1072
36 11 1061 1077
52 14 1062 1067
51 62 1063 1073
24 59 1064 1068
91 28 1065 1083
22 80 1066 1081
74 66 1067 1080
53 34 1068 1075
18 14 1069 1071
90 14 1070 1074
65 53 1071 1084
13 64 1072 1091
60 91 1073 1093
54 54 1074 1078
39 12 1075 1079
17 36 1076 1082
95 62 1077 1086
11 18 1078 1090
71 36 1079 1094
53 83 1080 1087
60 37 1081 1095
99 56 1082 1112
42 38 1083 1085
15 41 1084 1088
36 19 1085 1089
44 57 1086 1103
78 66 1087 1097
20 71 1088 1096
52 49 1089 1100
45 40 1090 1092
96 98 1091 1138
21 42 1092 1102
42 20 1093 1107
92 97 1094 1126
57 16 1095 1098
16 100 1096 1099
44 53 1097 1106
19 79 1098 1101
95 19 1099 1114
29 15 1100 1110
38 85 1101 1128
85 86 1102 1111
82 52 1103 1104
27 87 1104 1105
60 24 1105 1120
46 26 1106 1109
48 49 1107 1108
26 16 1108 1131
65 58 1109 1133
92 57 1110 1113
48 84 1111 1136
74 45 1112 1116
41 46 1113 1118
62 51 1114 1115
97 59 1115 1117
100 68 1116 1124
85 43 1117 1119
81 71 1118 1125
19 36 1119 1121
68 30 1120 1122
32 79 1121 1123
43 95 1122 1127
76 41 1123 1129
82 78 1124 1148
96 44 1125 1135
98 86 1126 1130
53 17 1127 1137
45 30 1128 1143
34 97 1129 1134
74 60 1130 1153
28 66 1131 1132
72 39 1132 1141
70 32 1133 1140
80 46 1134 1142
22 69 1135 1149
91 40 1136 1144
40 35 1137 1139
19 80 1138 1146
35 79 1139 1154
92 95 1140 1159
72 11 1141 1162
40 18 1142 1145
67 50 1143 1147
98 12 1144 1169
68 32 1145 1170
96 62 1146 1158
55 59 1147 1152
68 95 1148 1150
98 27 1149 1151
75 36 1150 1165
56 23 1151 1171
81 82 1152 1166
62 92 1153 1157
77 36 1154 1155
62 88 1155 1156
47 44 1156 1172
62 47 1157 1168
56 88 1158 1161
44 70 1159 1160
16 70 1160 1164
87 77 1161 1163
40 15 1162 1183
15 80 1163 1190
63 26 1164 1175
18 23 1165 1173
67 26 1166 1167
48 91 1167 1180
36 65 1168 1181
26 39 1169 1174
76 26 1170 1213
59 32 1171 1177
77 99 1172 1197
73 70 1173 1185
33 92 1174 1178
34 98 1175 1176
37 26 1176 1188
76 98 1177 1191
73 79 1178 1179
36 87 1179 1182
56 30 1180 1186
56 36 1181 1187
91 80 1182 1198
12 23 1183 1184
74 100 1184 1195
63 36 1185 1192
78 45 1186 1194
16 80 1187 1189
57 19 1188 1200
30 13 1189 1205
53 50 1190 1193
29 74 1191 1203
61 97 1192 1204
41 11 1193 1219
47 94 1194 1202
10 90 1195 1196
58 60 1196 1208
24 14 1197 1199
30 48 1198 1215
87 39 1199 1206
54 44 1200 1201
48 75 1201 1207
76 23 1202 1243
66 57 1203 1218
58 33 1204 1209
62 30 1205 1212
61 56 1206 1216
34 56 1207 1210
85 64 1208 1211
87 91 1209 1224
99 94 1210 1234
12 90 1211 1214
35 80 1212 1231
20 34 1213 1217
37 52 1214 1246
66 26 1215 1220
51 41 1216 1230
68 88 1217 1221
97 87 1218 1227
70 76 1219 1237
80 25 1220 1222
55 97 1221 1223
82 85 1222 1225
96 27 1223 1226
76 84 1224 1228
95 16 1225 1233
40 25 1226 1253
63 52 1227 1229
30 68 1228 1232
84 80 1229 1241
54 55 1230 1236
44 73 1231 1239
65 13 1232 1240
42 52 1233 1238
70 48 1234 1235
18 99 1235 1303
72 88 1236 1244
11 39 1237 1248
20 24 1238 1242
90 89 1239 1245
81 76 1240 1251
40 30 1241 1252
39 77 1242 1262
19 19 1243 1249
52 53 1244 1260
72 92 1245 1250
91 63 1246 1247
42 27 1247 1256
34 60 1248 1254
96 15 1249 1263
64 72 1250 1264
88 17 1251 1277
92 65 1252 1257
28 84 1253 1255
41 53 1254 1258
77 12 1255 1259
85 65 1256 1272
21 20 1257 1276
49 63 1258 1267
38 93 1259 1273
36 52 1260 1261
68 15 1261 1269
28 78 1262 1265
11 23 1263 1271
89 37 1264 1281
21 83 1265 1266
74 12 1266 1268
51 18 1267 1286
15 96 1268 1285
79 84 1269 1270
84 23 1270 1291
87 24 1271 1280
27 25 1272 1275
46 11 1273 1274
16 22 1274 1289
15 95 1275 1279
92 50 1276 1278
89 95 1277 1282
48 54 1278 1283
18 25 1279 1288
26 100 1280 1287
80 92 1281 1284
21 73 1282 1292
35 44 1283 1315
47 55 1284 1295
28 37 1285 1301
98 65 1286 1293
61 31 1287 1296
17 20 1288 1302
94 31 1289 1290
26 95 1290 1306
69 79 1291 1298
31 31 1292 1297
62 58 1293 1294
55 51 1294 1322
76 55 1295 1311
37 68 1296 1330
11 99 1297 1299
41 64 1298 1300
29 39 1299 1304
30 49 1300 1328
66 31 1301 1318
57 85 1302 1308
41 33 1303 1305
28 58 1304 1307
43 59 1305 1310
75 90 1306 1320
50 93 1307 1309
29 86 1308 1313
55 13 1309 1321
85 61 1310 1314
18 23 1311 1312
51 47 1312 1319
48 77 1313 1316
97 66 1314 1317
40 89 1315 1331
16 97 1316 1334
20 23 1317 1332
59 72 1318 1333
39 70 1319 1324
46 75 1320 1349
77 78 1321 1325
93 21 1322 1323
26 46 1323 1335
90 88 1324 1326
42 85 1325 1329
17 12 1326 1327
67 78 1327 1357
19 79 1328 1336
50 27 1329 1339
11 18 1330 1341
87 15 1331 1340
79 59 1332 1337
38 48 1333 1342
29 54 1334 1344
52 20 1335 1346
95 38 1336 1338
45 17 1337 1356
52 92 1338 1351
75 46 1339 1348
90 71 1340 1343
31 87 1341 1345
12 18 1342 1354
19 96 1343 1355
19 44 1344 1350
17 73 1345 1353
54 48 1346 1347
59 29 1347 1362
54 92 1348 1352
84 15 1349 1359
99 85 1350 1374
23 49 1351 1358
27 21 1352 1367
86 85 1353 1365
13 91 1354 1375
45 35 1355 1360
84 46 1356 1369
63 88 1357 1366
90 70 1358 1361
70 82 1359 1363
46 24 1360 1368
50 69 1361 1388
96 37 1362 1364
13 89 1363 1370
49 28 1364 1382
77 10 1365 1372
78 60 1366 1373
12 72 1367 1379
75 30 1368 1385
87 74 1369 1397
82 97 1370 1371
58 84 1371 1380
73 19 1372 1384
96 21 1373 1381
90 51 1374 1376
46 64 1375 1378
46 45 1376 1377
13 93 1377 1389
20 80 1378 1396
48 78 1379 1400
27 66 1380 1386
20 71 1381 1393
33 56 1382 1383
97 36 1383 1394
50 90 1384 1406
51 72 1385 1404
97 22 1386 1387
78 89 1387 1390
71 19 1388 1392
35 24 1389 1399
82 82 1390 1391
89 74 1391 1395
46 49 1392 1421
56 61 1393 1417
78 11 1394 1405
19 13 1395 1398
77 69 1396 1407
52 69 1397 1408
97 32 1398 1401
20 94 1399 1402
53 79 1400 1409
93 80 1401 1441
24 83 1402 1403
24 72 1403 1413
30 24 1404 1414
48 65 1405 1424
39 93 1406 1412
86 100 1407 1419
44 10 1408 1410
70 75 1409 1428
21 58 1410 1411
55 13 1411 1420
12 18 1412 1415
64 88 1413 1431
29 13 1414 1416
90 41 1415 1435
37 64 1416 1418
89 47 1417 1433
16 66 1418 1423
94 74 1419 1436
14 11 1420 1429
95 52 1421 1422
79 73 1422 1426
35 45 1423 1453
24 15 1424 1425
78 14 1425 1427
68 22 1426 1430
65 23 1427 1438
41 91 1428 1432
44 26 1429 1448
79 90 1430 1444
84 75 1431 1471
51 53 1432 1434
91 44 1433 1439
89 53 1434 1458
48 53 1435 1440
17 82 1436 1437
42 90 1437 1452
36 90 1438 1454
45 26 1439 1443
26 90 1440 1442
18 34 1441 1455
95 68 1442 1494
42 47 1443 1446
51 43 1444 1445
18 26 1445 1447
67 80 1446 1460
85 58 1447 1449
93 77 1448 1463
29 46 1449 1450
83 37 1450 1451
30 19 1451 1456
71 14 1452 1480
61 55 1453 1457
62 73 1454 1477
85 78 1455 1468
86 88 1456 1459
56 54 1457 1465
16 47 1458 1462
24 68 1459 1461
10 16 1460 1464
28 32 1461 1467
17 97 1462 1472
16 26 1463 1470
80 12 1464 1473
20 71 1465 1466
45 59 1466 1478
63 72 1467 1469
12 39 1468 1490
56 87 1469 1474
57 65 1470 1475
35 97 1471 1479
13 64 1472 1476
69 78 1473 1496
20 90 1474 1483
51 41 1475 1482
30 64 1476 1521
50 40 1477 1481
57 97 1478 1502
94 74 1479 1487
50 11 1480 1486
13 78 1481 1512
50 89 1482 1484
45 61 1483 1491
14 48 1484 1485
79 92 1485 1497
25 25 1486 1488
68 80 1487 1489
65 20 1488 1493
97 86 1489 1501
48 79 1490 1492
23 94 1491 1495
37 19 1492 1503
78 53 1493 1508
80 67 1494 1500
93 18 1495 1499
62 96 1496 1498
73 13 1497 1504
13 12 1498 1505
30 65 1499 1507
62 66 1500 1539
81 12 1501 1515
98 54 1502 1516
38 51 1503 1513
11 68 1504 1506
71 50 1505 1519
82 11 1506 1509
34 43 1507 1523
89 83 1508 1511
52 22 1509 1510
79 96 1510 1514
19 89 1511 1527
14 98 1512 1517
38 63 1513 1538
49 30 1514 1518
78 64 1515 1525
91 31 1516 1529
43 53 1517 1524
50 51 1518 1520
71 50 1519 1530
60 67 1520 1528
51 61 1521 1522
22 88 1522 1526
25 59 1523 1547
77 31 1524 1532
80 76 1525 1540
75 36 1526 1534
46 63 1527 1553
98 78 1528 1535
17 59 1529 1531
25 72 1530 1565
88 84 1531 1533
53 91 1532 1536
77 21 1533 1580
61 73 1534 1572
57 61 1535 1537
31 77 1536 1541
39 51 1537 1544
58 91 1538 1545
51 87 1539 1546
16 19 1540 1542
70 27 1541 1543
28 23 1542 1550
44 100 1543 1568
88 21 1544 1590
52 33 1545 1548
23 26 1546 1554
86 68 1547 1549
91 49 1548 1556
23 90 1549 1551
38 85 1550 1555
96 70 1551 1552
93 90 1552 1557
34 65 1553 1559
57 73 1554 1578
81 83 1555 1562
24 52 1556 1558
13 57 1557 1567
90 34 1558 1561
54 52 1559 1560
28 22 1560 1570
43 52 1561 1571
36 44 1562 1563
17 74 1563 1564
34 20 1564 1566
28 10 1565 1569
23 75 1566 1592
17 23 1567 1576
88 39 1568 1585
84 96 1569 1575
77 44 1570 1573
37 30 1571 1583
66 54 1572 1598
21 23 1573 1574
82 77 1574 1589
80 15 1575 1581
91 21 1576 1577
78 92 1577 1579
12 53 1578 1591
34 16 1579 1600
73 36 1580 1582
86 91 1581 1587
64 66 1582 1588
55 49 1583 1584
72 54 1584 1603
69 42 1585 1586
11 14 1586 1596
48 34 1587 1595
22 87 1588 1593
38 75 1589 1594
16 87 1590 1617
36 68 1591 1605
29 72 1592 1601
93 89 1593 1612
77 86 1594 1599
46 80 1595 1597
63 52 1596 1684
11 29 1597 1608
70 93 1598 1606
93 36 1599 1628
20 19 1600 1604
57 30 1601 1602
75 32 1602 1636
58 23 1603 1611
95 23 1604 1618
40 90 1605 1610
36 31 1606 1607
40 12 1607 1614
58 55 1608 1609
49 73 1609 1624
42 21 1610 1613
62 41 1611 1634
81 69 1612 1625
30 11 1613 1623
39 28 1614 1615
42 76 1615 1616
28 11 1616 1630
81 12 1617 1621
12 75 1618 1619
61 39 1619 1620
34 54 1620 1633
36 88 1621 1622
30 55 1622 1657
65 36 1623 1638
47 87 1624 1626
12 22 1625 1632
88 13 1626 1627
29 54 1627 1629
32 97 1628 1641
97 58 1629 1631
96 55 1630 1637
13 86 1631 1635
15 55 1632 1640
75 51 1633 1645
88 49 1634 1656
61 79 1635 1642
76 19 1636 1639
37 13 1637 1643
77 82 1638 1646
13 83 1639 1647
72 90 1640 1650
78 95 1641 1658
68 86 1642 1644
19 12 1643 1653
100 83 1644 1659
14 28 1645 1654
34 85 1646 1648
53 43 1647 1655
44 10 1648 1649
11 75 1649 1663
91 61 1650 1651
83 57 1651 1652
28 58 1652 1676
83 88 1653 1662
33 45 1654 1668
77 24 1655 1667
76 30 1656 1669
86 40 1657 1661
26 73 1658 1660
23 32 1659 1685
68 79 1660 1674
68 70 1661 1664
94 84 1662 1679
44 89 1663 1666
84 31 1664 1665
65 94 1665 1670
62 66 1666 1672
94 85 1667 1678
78 57 1668 1682
66 29 1669 1680
100 80 1670 1671
96 35 1671 1675
70 82 1672 1673
97 75 1673 1683
29 45 1674 1677
52 52 1675 1681
93 73 1676 1689
24 96 1677 1693
37 96 1678 1696
90 49 1679 1688
59 19 1680 1686
66 63 1681 1691
19 46 1682 1718
74 32 1683 1690
67 99 1684 1687
61 27 1685 1698
94 90 1686 1695
53 38 1687 1699
40 55 1688 1719
79 77 1689 1694
94 72 1690 1692
70 58 1691 1704
67 81 1692 1733
12 30 1693 1707
61 27 1694 1697
20 25 1695 1703
69 85 1696 1700
55 67 1697 1701
32 78 1698 1721
20 63 1699 1702
52 42 1700 1709
17 23 1701 1710
93 63 1702 1705
15 56 1703 1736
60 82 1704 1706
38 42 1705 1708
52 76 1706 1715
35 32 1707 1716
17 47 1708 1749
23 12 1709 1711
37 75 1710 1712
65 83 1711 1713
72 86 1712 1717
87 16 1713 1714
94 18 1714 1727
65 90 1715 1770
21 99 1716 1728
55 80 1717 1720
38 42 1718 1723
94 64 1719 1724
46 27 1720 1722
96 64 1721 1730
61 85 1722 1731
38 78 1723 1726
75 37 1724 1725
73 12 1725 1734
63 14 1726 1737
26 90 1727 1753
55 84 1728 1729
67 14 1729 1742
34 74 1730 1763
71 57 1731 1732
74 70 1732 1740
53 75 1733 1735
49 61 1734 1738
48 46 1735 1743
47 63 1736 1748
24 93 1737 1739
91 68 1738 1751
92 65 1739 1741
27 26 1740 1745
12 28 1741 1746
36 64 1742 1744
72 47 1743 1768
15 82 1744 1759
98 22 1745 1765
85 41 1746 1747
25 10 1747 1752
51 51 1748 1750
21 23 1749 1760
18 15 1750 1766
25 18 1751 1757
19 94 1752 1755
73 94 1753 1754
54 93 1754 1756
62 52 1755 1758
64 28 1756 1773
59 76 1757 1792
97 57 1758 1764
61 81 1759 1761
73 90 1760 1767
32 23 1761 1762
21 21 1762 1776
26 29 1763 1769
94 71 1764 1808
65 45 1765 1771
41 92 1766 1783
94 10 1767 1774
54 67 1768 1772
76 68 1769 1777
69 93 1770 1794
96 23 1771 1780
97 84 1772 1795
36 18 1773 1775
16 94 1774 1782
24 38 1775 1790
86 53 1776 1778
32 15 1777 1779
18 21 1778 1800
91 15 1779 1781
18 68 1780 1784
43 17 1781 1796
41 44 1782 1786
12 75 1783 1785
59 26 1784 1788
41 24 1785 1805
15 87 1786 1787
97 99 1787 1791
86 72 1788 1789
40 17 1789 1793
62 22 1790 1798
37 96 1791 1823
35 54 1792 1806
72 24 1793 1799
14 92 1794 1797
17 99 1795 1807
90 36 1796 1804
32 95 1797 1815
68 18 1798 1802
76 20 1799 1803
86 58 1800 1801
30 90 1801 1810
45 47 1802 1822
87 44 1803 1816
92 67 1804 1813
97 56 1805 1817
63 99 1806 1814
97 48 1807 1809
10 69 1808 1820
88 17 1809 1811
36 24 1810 1833
41 44 1811 1812
76 66 1812 1818
11 34 1813 1830
95 70 1814 1842
71 43 1815 1825
90 64 1816 1836
12 45 1817 1821
72 47 1818 1819
98 89 1819 1828
23 85 1820 1843
80 70 1821 1824
47 28 1822 1831
52 31 1823 1827
39 39 1824 1835
25 56 1825 1826
56 97 1826 1829
81 32 1827 1839
28 81 1828 1844
13 27 1829 1856
22 39 1830 1834
84 77 1831 1832
74 88 1832 1838
96 62 1833 1851
42 10 1834 1848
22 66 1835 1849
84 66 1836 1837
66 10 1837 1850
67 10 1838 1840
29 74 1839 1845
83 79 1840 1841
32 44 1841 1873
70 43 1842 1846
88 62 1843 1854
20 45 1844 1868
77 46 1845 1847
63 28 1846 1853
21 99 1847 1857
37 78 1848 1867
24 80 1849 1861
85 48 1850 1852
29 67 1851 1855
27 68 1852 1858
66 36 1853 1875
27 92 1854 1865
11 68 1855 1864
22 85 1856 1860
98 21 1857 1862
92 100 1858 1859
11 70 1859 1889
53 17 1860 1866
93 71 1861 1893
85 99 1862 1863
23 93 1863 1872
16 28 1864 1874
26 26 1865 1870
96 51 1866 1871
49 37 1867 1880
30 86 1868 1869
14 46 1869 1877
22 51 1870 1878
88 18 1871 1887
47 50 1872 1892
54 26 1873 1882
75 63 1874 1876
19 98 1875 1894
78 11 1876 1901
47 27 1877 1879
47 48 1878 1881
43 65 1879 1883
82 26 1880 1899
88 64 1881 1888
81 79 1882 1895
25 60 1883 1884
62 35 1884 1885
72 69 1885 1886
98 75 1886 1890
94 27 1887 1898
81 75 1888 1906
36 43 1889 1897
67 94 1890 1891
24 53 1891 1900
47 36 1892 1902
49 28 1893 1924
49 51 1894 1896
76 53 1895 1908
34 22 1896 1904
23 84 1897 1931
63 61 1898 1905
24 17 1899 1914
78 42 1900 1903
22 46 1901 1947
18 71 1902 1917
88 52 1903 1910
84 24 1904 1907
12 71 1905 1909
74 54 1906 1928
54 19 1907 1921
36 62 1908 1913
64 44 1909 1915
23 51 1910 1911
46 20 1911 1912
68 61 1912 1918
54 12 1913 1916
95 24 1914 1939
35 21 1915 1927
97 79 1916 1923
67 44 1917 1920
52 84 1918 1919
39 73 1919 1936
45 56 1920 1926
55 41 1921 1922
17 69 1922 1934
80 31 1923 1932
63 62 1924 1925
66 52 1925 1946
12 97 1926 1942
72 50 1927 1933
41 33 1928 1929
30 62 1929 1930
69 34 1930 1937
81 30 1931 1935
17 39 1932 1963
56 70 1933 1958
31 95 1934 1941
39 93 1935 1940
41 68 1936 1938
97 11 1937 1950
20 15 1938 1949
70 44 1939 1955
56 31 1940 1943
42 65 1941 1960
84 82 1942 1944
30 60 1943 1959
93 48 1944 1945
30 32 1945 1961
73 61 1946 1948
21 93 1947 1954
98 25 1948 1952
49 31 1949 1962
77 73 1950 1951
20 28 1951 1953
13 75 1952 1967
84 38 1953 1974
63 84 1954 1956
42 46 1955 1957
68 91 1956 1982
13 28 1957 1977
48 88 1958 1966
94 86 1959 1964
46 30 1960 1968
59 80 1961 1971
54 36 1962 1975
99 29 1963 1965
88 77 1964 1990
16 84 1965 1969
61 54 1966 1991
35 31 1967 1972
11 40 1968 1970
67 52 1969 1981
37 17 1970 1973
16 33 1971 1999
91 99 1972 1976
26 67 1973 1983
23 71 1974 1994
88 81 1975 1978
83 34 1976 1996
49 55 1977 1980
54 75 1978 1979
30 32 1979 1988
32 72 1980 1986
71 96 1981 1984
65 65 1982 2005
47 72 1983 1985
10 17 1984 2013
54 61 1985 1987
63 37 1986 1989
48 47 1987 2001
39 45 1988 1993
57 95 1989 1992
50 62 1990 2027
55 49 1991 2000
67 42 1992 1998
52 70 1993 2010
62 52 1994 1995
21 55 1995 2002
79 75 1996 1997
57 72 1997 2011
94 81 1998 2003
71 57 1999 2009
14 91 2000 2004
45 25 2001 2017
76 42 2002 2015
32 30 2003 2012
29 10 2004 2007
12 24 2005 2006
25 48 2006 2025
42 80 2007 2008
43 76 2008 2022
47 99 2009 2014
77 55 2010 2019
15 70 2011 2018
48 28 2012 2021
24 29 2013 2020
87 88 2014 2044
28 18 2015 2016
45 18 2016 2026
86 19 2017 2033
49 12 2018 2024
54 67 2019 2043
25 20 2020 2036
84 62 2021 2023
24 43 2022 2034
47 38 2023 2051
24 55 2024 2029
30 36 2025 2028
32 72 2026 2030
83 68 2027 2039
40 43 2028 2031
54 98 2029 2032
27 17 2030 2069
60 78 2031 2040
59 96 2032 2035
47 46 2033 2054
72 77 2034 2037
68 77 2035 2038
12 32 2036 2041
52 89 2037 2042
74 57 2038 2049
78 59 2039 2048
93 43 2040 2065
29 88 2041 2047
75 67 2042 2063
25 64 2043 2046
15 94 2044 2045
69 69 2045 2083
61 83 2046 2050
49 31 2047 2058
30 30 2048 2060
13 37 2049 2052
62 82 2050 2055
17 73 2051 2056
79 30 2052 2053
81 75 2053 2057
28 52 2054 2076
80 50 2055 2090
17 24 2056 2066
11 10 2057 2061
98 83 2058 2059
55 100 2059 2070
41 75 2060 2062
96 32 2061 2071
30 77 2062 2064
87 70 2063 2080
60 98 2064 2067
90 46 2065 2074
61 97 2066 2104
83 27 2067 2068
95 93 2068 2073
53 44 2069 2072
64 21 2070 2075
11 99 2071 2098
46 85 2072 2078
40 39 2073 2077
93 16 2074 2079
19 55 2075 2082
97 92 2076 2086
13 13 2077 2081
57 86 2078 2088
26 32 2079 2087
77 30 2080 2084
45 39 2081 2085
42 41 2082 2092
81 96 2083 2093
92 71 2084 2094
13 19 2085 2120
77 39 2086 2089
49 68 2087 2105
71 84 2088 2114
30 87 2089 2091
11 65 2090 2096
73 14 2091 2117
34 88 2092 2101
67 46 2093 2095
17 26 2094 2106
80 54 2095 2100
43 62 2096 2097
31 24 2097 2099
89 14 2098 2102
34 14 2099 2125
65 98 2100 2124
73 59 2101 2103
87 65 2102 2107
25 12 2103 2113
13 72 2104 2108
94 73 2105 2110
74 68 2106 2111
31 81 2107 2109
72 34 2108 2112
91 18 2109 2122
67 23 2110 2131
46 10 2111 2116
25 62 2112 2115
33 37 2113 2123
29 60 2114 2136
98 80 2115 2143
27 66 2116 2118
43 49 2117 2119
48 34 2118 2121
57 13 2119 2126
92 23 2120 2135
15 27 2121 2127
85 89 2122 2128
96 31 2123 2158
95 95 2124 2132
31 100 2125 2138
49 56 2126 2133
26 98 2127 2129
20 41 2128 2142
68 19 2129 2130
87 69 2130 2134
61 82 2131 2141
83 65 2132 2165
12 100 2133 2137
39 33 2134 2184
27 70 2135 2140
98 45 2136 2139
36 19 2137 2153
46 14 2138 2144
38 93 2139 2149
86 99 2140 2151
21 47 2141 2155
87 20 2142 2145
32 53 2143 2146
54 96 2144 2147
79 52 2145 2148
55 41 2146 2188
29 81 2147 2154
23 26 2148 2150
70 49 2149 2159
38 68 2150 2161
11 51 2151 2152
12 76 2152 2157
78 31 2153 2171
80 46 2154 2156
87 95 2155 2179
87 87 2156 2163
53 84 2157 2164
41 32 2158 2160
20 18 2159 2170
83 89 2160 2162
43 48 2161 2172
11 74 2162 2166
23 82 2163 2169
10 80 2164 2167
12 44 2165 2173
83 56 2166 2168
20 92 2167 2174
38 74 2168 2175
71 71 2169 2176
58 34 2170 2200
70 47 2171 2186
28 33 2172 2181
44 84 2173 2196
94 26 2174 2177
62 61 2175 2180
84 83 2176 2178
33 22 2177 2182
62 49 2178 2183
14 34 2179 2193
58 33 2180 2185
65 74 2181 2190
30 66 2182 2191
99 96 2183 2192
25 16 2184 2187
68 99 2185 2202
38 27 2186 2197
81 75 2187 2189
69 92 2188 2209
32 59 2189 2208
71 62 2190 2194
64 87 2191 2211
71 70 2192 2203
72 23 2193 2206
71 13 2194 2195
69 76 2195 2199
99 71 2196 2212
63 57 2197 2198
42 68 2198 2201
17 60 2199 2213
37 100 2200 2214
45 75 2201 2205
40 12 2202 2204
82 67 2203 2218
26 14 2204 2207
61 99 2205 2220
91 54 2206 2215
53 35 2207 2216
55 78 2208 2231
97 45 2209 2210
97 68 2210 2219
15 85 2211 2228
99 23 2212 2224
12 17 2213 2234
15 74 2214 2225
39 40 2215 2217
49 85 2216 2261
91 86 2217 2245
82 91 2218 2222
40 12 2219 2221
100 11 2220 2229
34 79 2221 2223
29 10 2222 2226
78 37 2223 2240
85 48 2224 2230
87 70 2225 2247
35 45 2226 2227
49 80 2227 2235
38 34 2228 2233
50 100 2229 2248
72 12 2230 2232
95 76 2231 2238
90 10 2232 2237
63 52 2233 2241
42 28 2234 2236
46 25 2235 2264
67 54 2236 2239
42 68 2237 2244
54 52 2238 2243
15 59 2239 2255
54 47 2240 2254
30 47 2241 2242
85 87 2242 2280
65 87 2243 2250
16 79 2244 2246
63 25 2245 2256
76 23 2246 2249
25 69 2247 2267
12 55 2248 2258
96 98 2249 2251
64 49 2250 2265
14 39 2251 2252
69 39 2252 2253
32 40 2253 2269
91 68 2254 2263
49 27 2255 2260
54 65 2256 2257
29 11 2257 2259
20 72 2258 2284
28 64 2259 2262
63 78 2260 2273
44 72 2261 2303
85 85 2262 2266
78 37 2263 2275
52 35 2264 2271
69 13 2265 2279
84 63 2266 2268
81 38 2267 2278
16 68 2268 2282
58 43 2269 2270
78 48 2270 2272
22 44 2271 2287
12 36 2272 2288
27 53 2273 2274
82 83 2274 2276
36 80 2275 2306
48 37 2276 2277
19 81 2277 2290
13 30 2278 2281
58 92 2279 2285
13 78 2280 2296
89 56 2281 2291
23 65 2282 2283
41 100 2283 2286
17 83 2284 2300
99 96 2285 2289
74 10 2286 2317
72 63 2287 2294
70 88 2288 2311
96 62 2289 2292
76 64 2290 2295
31 53 2291 2309
59 16 2292 2293
25 19 2293 2307
65 57 2294 2297
60 30 2295 2298
99 46 2296 2302
87 61 2297 2299
33 11 2298 2305
69 62 2299 2301
24 64 2300 2310
89 100 2301 2304
57 74 2302 2308
85 64 2303 2353
31 12 2304 2338
28 81 2305 2328
22 54 2306 2313
67 15 2307 2324
82 78 2308 2314
33 50 2309 2326
16 40 2310 2315
34 98 2311 2312
64 18 2312 2329
10 75 2313 2316
85 34 2314 2319
89 53 2315 2321
15 74 2316 2322
43 35 2317 2318
45 43 2318 2320
66 54 2319 2323
71 85 2320 2336
40 52 2321 2327
49 28 2322 2348
34 100 2323 2344
73 49 2324 2325
54 12 2325 2339
96 51 2326 2362
46 44 2327 2331
63 93 2328 2333
35 50 2329 2330
100 41 2330 2332
47 47 2331 2335
64 50 2332 2334
17 19 2333 2356
68 75 2334 2394
29 40 2335 2337
28 30 2336 2342
61 55 2337 2340
35 67 2338 2343
21 22 2339 2346
76 32 2340 2341
14 15 2341 2352
49 87 2342 2347
68 85 2343 2345
91 18 2344 2350
72 77 2345 2359
99 30 2346 2357
95 42 2347 2349
20 12 2348 2351
96 11 2349 2354
95 98 2350 2390
26 72 2351 2355
51 88 2352 2369
66 83 2353 2379
60 19 2354 2382
66 65 2355 2366
82 82 2356 2358
35 23 2357 2361
80 93 2358 2364
30 90 2359 2360
54 38 2360 2363
45 76 2361 2370
45 47 2362 2365
54 39 2363 2367
98 35 2364 2376
10 56 2365 2371
15 60 2366 2368
24 44 2367 2373
21 48 2368 2374
44 85 2369 2385
62 12 2370 2377
39 62 2371 2372
100 87 2372 2384
97 24 2373 2375
33 16 2374 2381
49 43 2375 2378
96 48 2376 2399
18 84 2377 2387
10 38 2378 2386
36 89 2379 2380
96 89 2380 2396
65 83 2381 2389
28 35 2382 2383
38 35 2383 2391
38 82 2384 2393
17 92 2385 2447
64 26 2386 2397
14 67 2387 2388
57 42 2388 2406
23 26 2389 2413
87 24 2390 2392
19 57 2391 2401
85 45 2392 2395
52 75 2393 2400
88 98 2394 2408
67 72 2395 2405
98 17 2396 2421
43 92 2397 2398
65 80 2398 2403
84 81 2399 2428
25 29 2400 2418
20 96 2401 2402
44 65 2402 2404
74 73 2403 2407
12 64 2404 2409
93 60 2405 2410
45 28 2406 2440
85 71 2407 2411
14 62 2408 2416
51 27 2409 2412
38 40 2410 2417
33 74 2411 2422
35 34 2412 2414
23 45 2413 2426
14 51 2414 2415
31 32 2415 2456
33 17 2416 2419
13 96 2417 2425
92 39 2418 2420
82 72 2419 2429
41 23 2420 2424
94 88 2421 2423
23 62 2422 2430
96 48 2423 2448
75 61 2424 2445
64 51 2425 2427
87 97 2426 2436
28 19 2427 2433
25 14 2428 2432
100 10 2429 2431
37 68 2430 2437
30 51 2431 2443
43 23 2432 2435
96 31 2433 2434
30 15 2434 2438
84 100 2435 2441
63 69 2436 2462
72 95 2437 2446
64 76 2438 2439
80 64 2439 2442
39 23 2440 2465
31 13 2441 2444
44 31 2442 2452
59 29 2443 2459
57 40 2444 2450
27 61 2445 2453
49 13 2446 2449
82 47 2447 2454
57 35 2448 2464
83 26 2449 2451
81 46 2450 2463
64 19 2451 2458
14 28 2452 2457
39 86 2453 2460
59 54 2454 2455
95 45 2455 2469
38 51 2456 2480
24 40 2457 2472
80 15 2458 2461
79 79 2459 2470
35 33 2460 2499
58 46 2461 2468
94 53 2462 2467
28 38 2463 2474
90 77 2464 2466
19 71 2465 2534
43 39 2466 2507
23 90 2467 2477
38 14 2468 2491
98 97 2469 2492
93 94 2470 2471
42 24 2471 2473
78 74 2472 2485
53 52 2473 2476
51 67 2474 2475
55 79 2475 2482
63 24 2476 2478
76 98 2477 2479
31 26 2478 2481
12 77 2479 2489
21 10 2480 2483
48 72 2481 2496
79 19 2482 2484
82 47 2483 2495
36 69 2484 2487
26 88 2485 2486
94 37 2486 2488
10 48 2487 2502
84 68 2488 2490
46 55 2489 2516
90 35 2490 2494
78 41 2491 2497
87 67 2492 2493
84 92 2493 2517
45 58 2494 2501
96 51 2495 2498
12 74 2496 2503
86 62 2497 2509
32 26 2498 2513
32 95 2499 2500
88 89 2500 2506
69 39 2501 2511
21 21 2502 2504
50 29 2503 2515
70 94 2504 2505
59 87 2505 2533
95 58 2506 2508
70 100 2507 2514
90 74 2508 2510
35 33 2509 2525
37 33 2510 2512
97 40 2511 2528
51 86 2512 2541
43 81 2513 2539
24 41 2514 2519
14 11 2515 2529
62 65 2516 2521
35 60 2517 2518
32 25 2518 2520
27 57 2519 2523
28 70 2520 2522
66 24 2521 2540
73 36 2522 2550
77 38 2523 2524
65 47 2524 2526
70 29 2525 2527
61 28 2526 2530
51 68 2527 2532
72 68 2528 2531
53 18 2529 2552
29 53 2530 2535
55 53 2531 2547
88 23 2532 2544
42 86 2533 2536
32 63 2534 2538
22 80 2535 2563
22 29 2536 2537
70 30 2537 2551
40 72 2538 2542
68 28 2539 2548
30 31 2540 2543
79 29 2541 2546
65 65 2542 2549
76 100 2543 2545
44 44 2544 2560
88 62 2545 2553
46 90 2546 2561
88 51 2547 2574
68 11 2548 2562
35 79 2549 2554
39 62 2550 2564
51 65 2551 2556
78 28 2552 2559
99 42 2553 2585
53 95 2554 2555
33 93 2555 2566
28 66 2556 2557
76 95 2557 2558
41 86 2558 2567
62 96 2559 2572
32 93 2560 2568
42 56 2561 2584
75 16 2562 2565
68 17 2563 2577
99 96 2564 2569
87 20 2565 2579
97 75 2566 2573
51 80 2567 2570
37 33 2568 2589
21 95 2569 2578
95 92 2570 2571
89 93 2571 2575
20 73 2572 2581
96 47 2573 2586
94 64 2574 2580
26 75 2575 2576
26 21 2576 2592
22 37 2577 2591
82 74 2578 2582
66 15 2579 2603
18 17 2580 2601
15 13 2581 2590
10 87 2582 2583
87 62 2583 2593
59 72 2584 2587
90 62 2585 2595
83 25 2586 2610
90 81 2587 2588
25 40 2588 2608
92 89 2589 2598
66 78 2590 2596
61 40 2591 2604
66 38 2592 2597
58 95 2593 2594
27 76 2594 2611
100 17 2595 2612
71 55 2596 2599
14 90 2597 2600
46 90 2598 2618
48 31 2599 2605
33 72 2600 2602
31 22 2601 2623
27 11 2602 2606
90 58 2603 2609
44 26 2604 2627
54 77 2605 2613
30 60 2606 2607
41 53 2607 2620
98 81 2608 2633
46 30 2609 2614
90 48 2610 2617
11 33 2611 2626
63 79 2612 2616
36 21 2613 2615
35 27 2614 2629
38 50 2615 2619
78 83 2616 2634
61 82 2617 2646
90 75 2618 2656
97 32 2619 2621
32 69 2620 2622
88 77 2621 2630
44 37 2622 2624
36 79 2623 2625
17 34 2624 2632
56 68 2625 2631
91 39 2626 2628
24 97 2627 2638
90 79 2628 2635
58 79 2629 2650
38 39 2630 2673
100 11 2631 2637
37 96 2632 2636
34 99 2633 2648
51 95 2634 2658
37 55 2635 2640
48 77 2636 2639
32 79 2637 2649
41 71 2638 2689
41 27 2639 2644
92 84 2640 2641
14 62 2641 2642
89 10 2642 2643
42 70 2643 2645
83 41 2644 2652
78 85 2645 2647
18 98 2646 2672
100 20 2647 2651
52 19 2648 2657
23 43 2649 2653
27 52 2650 2667
23 95 2651 2654
97 68 2652 2664
46 20 2653 2668
47 73 2654 2655
84 12 2655 2663
84 54 2656 2661
42 83 2657 2659
42 65 2658 2660
69 30 2659 2662
14 82 2660 2669
28 69 2661 2665
62 44 2662 2666
39 20 2663 2677
41 71 2664 2674
43 73 2665 2685
26 53 2666 2689
52 44 2667 2671
15 66 2668 2670
98 34 2669 2679
27 53 2670 2678
21 86 2671 2676
24 88 2672 2680
30 43 2673 2675
36 38 2674 2684
47 73 2675 2683
38 72 2676 2682
35 77 2677 2686
17 67 2678 2689
94 72 2679 2688
89 30 2680 2681
15 44 2681 2689
18 30 2682 2689
99 20 2683 2689
23 40 2684 2689
36 85 2685 2687
65 44 2686 2689
18 36 2687 2689
88 57 2688 2689
;
%macro SetupData(task_data=, capacity=);
set TASKS;
num capacity=&capacity;
num profit{TASKS}, weight{TASKS}, start{TASKS}, end{TASKS};
read data &task_data into TASKS=[_n_] profit weight start end;
/* the set of start times */
set STARTS = setof{i in TASKS}start[i];
/* the set of tasks i that are active at a given start time s */
set TASKS_START{s in STARTS}
= {i in TASKS: start[i] <= s < end[i]};
%mend SetupData;
%macro ResourceAllocation_Direct(task_data=, capacity=);
proc optmodel;
%SetupData(task_data=&task_data,capacity=&capacity);
/* select task i to come online from period [start to end) */
var x{TASKS} binary;
/* maximize the total profit of running tasks */
max TotalProfit = sum{i in TASKS} profit[i] * x[i];
/* enforce that the shared resource capacity is not exceeded */
con CapacityCon{s in STARTS}:
sum{i in TASKS_START[s]} weight[i] * x[i] <= capacity;
solve;
quit;
%mend ResourceAllocation_Direct;
%ResourceAllocation_Direct(task_data=TaskData, capacity=100);
proc sort data=TaskData;
by start end;
run;
%macro ResourceAllocation_Decomp(task_data=, capacity=, block_size=);
proc optmodel;
%SetupData(task_data=&task_data,capacity=&capacity);
/* split into blocks of size blocks_size */
num block_size = &block_size;
num num_blocks = ceil( card(TASKS) / block_size );
set BLOCKS = 1..num_blocks;
/* the set of starts s for which task i is active */
set STARTS_TASK{i in TASKS} = {s in STARTS: start[i] <= s < end[i]};
/* partition the start times into blocks of size block_size */
set STARTS_BLOCK{BLOCKS} init {};
num block_id init 1;
num block_sz init 0;
for{s in STARTS} do;
STARTS_BLOCK[block_id] = STARTS_BLOCK[block_id] union {s};
block_sz = block_sz + 1;
if(mod(block_sz, block_size) = 0) then
block_id = block_id + 1;
end;
/* blocks in which task i is online */
set BLOCKS_TASK{i in TASKS} =
{b in BLOCKS: card(STARTS_BLOCK[b] inter STARTS_TASK[i]) > 0};
/* minimum block id in which task i is online */
num min_block{i in TASKS} = min{b in BLOCKS_TASK[i]}b;
/* select task i to come online from period [start to end)
in each block */
var x{i in TASKS, b in BLOCKS_TASK[i]} binary;
/* maximize the total profit of running tasks */
max TotalProfit = sum{i in TASKS} profit[i] * x[i,min_block[i]];
/* enforce that task selection is consistent across blocks */
con LinkDupVarsCon{i in TASKS, b in BLOCKS_TASK[i] diff {min_block[i]}}:
x[i,b] = x[i,min_block[i]];
/* enforce that the shared resource capacity is not exceeded */
con CapacityCon{b in BLOCKS, s in STARTS_BLOCK[b]}:
sum{i in TASKS_START[s]} weight[i] * x[i,b] <= capacity;
/* define blocks for decomposition algorithm */
for{b in BLOCKS, s in STARTS_BLOCK[b]} CapacityCon[b,s].block = b;
solve with milp / presolver=basic decomp=();
quit;
%mend ResourceAllocation_Decomp;
%ResourceAllocation_Decomp(task_data=TaskData, capacity=100, block_size=40);
%macro ResourceAllocation_Decomp3(task_data=, capacity=, block_size=);
proc optmodel;
%SetupData(task_data=&task_data,capacity=&capacity);
/* split into blocks of size blocks_size */
num block_size = &block_size;
num num_blocks = ceil( card(TASKS) / block_size );
set BLOCKS = 1..num_blocks;
/* the set of starts s for which task i is active */
set STARTS_TASK{i in TASKS} = {s in STARTS: start[i] <= s < end[i]};
/* partition the start times into blocks of size block_size */
set STARTS_BLOCK{BLOCKS} init {};
num block_id init 1;
num block_sz init 0;
for{s in STARTS} do;
STARTS_BLOCK[block_id] = STARTS_BLOCK[block_id] union {s};
block_sz = block_sz + 1;
if(mod(block_sz, block_size) = 0) then
block_id = block_id + 1;
end;
/* blocks in which task i is online */
set BLOCKS_TASK{i in TASKS} =
{b in BLOCKS: card(STARTS_BLOCK[b] inter STARTS_TASK[i]) > 0};
/* minimum block id in which task i is online */
num min_block{i in TASKS} = min{b in BLOCKS_TASK[i]}b;
/* select task i to come online from period [start to end)
in each block */
var x{i in TASKS, b in BLOCKS_TASK[i]} binary;
/* maximize the total profit of running tasks */
max TotalProfit = sum{i in TASKS} profit[i] * x[i,min_block[i]];
/* enforce that task selection is consistent across blocks */
con LinkDupVarsCon{i in TASKS, b in BLOCKS_TASK[i] diff {min_block[i]}}:
x[i,b] = x[i,min_block[i]];
/* enforce that the shared resource capacity is not exceeded */
con CapacityCon{b in BLOCKS, s in STARTS_BLOCK[b]}:
sum{i in TASKS_START[s]} weight[i] * x[i,b] <= capacity;
/* define blocks for decomposition algorithm */
for{b in BLOCKS, s in STARTS_BLOCK[b]} CapacityCon[b,s].block = b;
solve with milp / relobjgap=0.1;
solve with milp / presolver=basic primalin decomp=();
quit;
%mend ResourceAllocation_Decomp3;
%ResourceAllocation_Decomp3(task_data=TaskData, capacity=100, block_size=40);
%ResourceAllocation_Decomp(task_data=TaskData, capacity=100, block_size=130);