--- Job seymour Start 08/24/08 07:50:05 GAMS Rev 227 Copyright (C) 1987-2008 GAMS Development. All rights reserved Licensee: Stefan Vigerske G071106/0001CB-LNX Humboldt University Berlin, Numerical Mathematics DC5918 --- Starting compilation --- seymour.gms(106) 2 Mb --- GDXin=/home/stefan/work/gams/models/LINlib/seymour.gdx --- seymour.gms(148) 4 Mb --- Starting execution: elapsed 0:00:00.043 --- seymour.gms(123) 5 Mb --- Generating MIP model m --- seymour.gms(124) 7 Mb --- 4,945 rows 1,373 columns 34,922 non-zeroes --- 1,372 discrete-columns --- seymour.gms(124) 7 Mb --- Executing Cbc: elapsed 0:00:00.146 GAMS/Cbc 2.1 LP/MIP Solver written by J. Forrest Problem statistics: 1372 columns and 4944 rows. 1372 variables have integrality restrictions. Calling CBC main solution routine... Coin Cbc and Clp Solver version 2.20.00, build Aug 23 2008 command line - GAMS/CBC -solve -quit Continuous objective value is 403.846 - 2.18 seconds Optimal - objective value 403.846 0 fixed, 0 tightened bounds, 345 strengthened rows, 0 substitutions 0 fixed, 0 tightened bounds, 345 strengthened rows, 0 substitutions 0 fixed, 0 tightened bounds, 328 strengthened rows, 0 substitutions 0 fixed, 0 tightened bounds, 328 strengthened rows, 0 substitutions 0 fixed, 0 tightened bounds, 328 strengthened rows, 0 substitutions 0 fixed, 0 tightened bounds, 328 strengthened rows, 0 substitutions 0 fixed, 0 tightened bounds, 328 strengthened rows, 0 substitutions 0 fixed, 0 tightened bounds, 328 strengthened rows, 0 substitutions 0 fixed, 0 tightened bounds, 328 strengthened rows, 0 substitutions 0 fixed, 0 tightened bounds, 328 strengthened rows, 0 substitutions processed model has 4779 rows, 1153 columns (1153 integer) and 33007 elements Objective coefficients multiple of 1 Cutoff increment increased from 1e-05 to 0.999 Pass 1: (0.66 seconds) suminf. 58.97084 (221) obj. 425.788 iterations 1542 Pass 2: (0.81 seconds) suminf. 21.50000 (43) obj. 433.5 iterations 483 Pass 3: (0.84 seconds) suminf. 21.50000 (43) obj. 433.5 iterations 111 Pass 4: (0.87 seconds) suminf. 4.00000 (8) obj. 441 iterations 103 Pass 5: (0.88 seconds) suminf. 4.00000 (8) obj. 441 iterations 36 Solution found of 445 Cleaned solution of 445 Before mini branch and bound, 532 integers at bound fixed and 0 continuous of which 5 were internal integer and 0 internal continuous Full problem 4779 rows 1153 columns, reduced to 2715 rows 621 columns - too large Mini branch and bound did not improve solution (1.54 seconds) Round again with cutoff of 440 Pass 6: (2.19 seconds) suminf. 57.00166 (221) obj. 426.149 iterations 1533 Pass 7: (2.30 seconds) suminf. 19.73810 (63) obj. 433.786 iterations 358 Pass 8: (2.36 seconds) suminf. 1.50000 (3) obj. 434.5 iterations 177 Pass 9: (2.43 seconds) suminf. 1.50000 (3) obj. 434.5 iterations 179 Solution found of 436 Cleaned solution of 436 Before mini branch and bound, 531 integers at bound fixed and 0 continuous of which 5 were internal integer and 0 internal continuous Full problem 4779 rows 1153 columns, reduced to 2691 rows 622 columns - too large Mini branch and bound did not improve solution (3.05 seconds) After 3.05 seconds - Feasibility pump exiting with objective of 436 - took 3.04 seconds Integer solution of 436 found by feasibility pump after 0 iterations and 0 nodes (3.46 seconds) Full problem 4779 rows 1153 columns, reduced to 1 rows 3 columns Integer solution of 433 found by combine solutions after 0 iterations and 0 nodes (3.97 seconds) 43 added rows had average density of 299.419 At root node, 43 cuts changed objective from 405.469 to 409.227 in 10 passes Cut generator 0 (Probing) - 61 row cuts, 0 column cuts (36 active) in 0.260 seconds - new frequency is 2 Cut generator 1 (Gomory) - 5488 row cuts, 0 column cuts (7 active) in 1.528 seconds - new frequency is 1 Cut generator 2 (Knapsack) - 0 row cuts, 0 column cuts (0 active) in 0.028 seconds - new frequency is -100 Cut generator 3 (Clique) - 0 row cuts, 0 column cuts (0 active) in 0.040 seconds - new frequency is -100 Cut generator 4 (MixedIntegerRounding2) - 0 row cuts, 0 column cuts (0 active) in 0.180 seconds - new frequency is -100 Cut generator 5 (FlowCover) - 0 row cuts, 0 column cuts (0 active) in 0.228 seconds - new frequency is -100 Cut generator 6 (TwoMirCuts) - 330 row cuts, 0 column cuts (0 active) in 0.848 seconds - new frequency is -100 Optimal - objective value 409.227 Optimal - objective value 409.227 After 0 nodes, 1 on tree, 433 best solution, best possible 409.227 (13.82 seconds) After 100 nodes, 53 on tree, 433 best solution, best possible 410.577 (71.75 seconds) After 200 nodes, 119 on tree, 433 best solution, best possible 410.577 (102.01 seconds) Integer solution of 432 found after 110577 iterations and 258 nodes (107.06 seconds) Full problem 4779 rows 1153 columns, reduced to 316 rows 203 columns Integer solution of 428 found by combine solutions after 111054 iterations and 259 nodes (107.77 seconds) After 300 nodes, 144 on tree, 428 best solution, best possible 410.577 (126.51 seconds) After 400 nodes, 195 on tree, 428 best solution, best possible 410.577 (160.98 seconds) After 500 nodes, 244 on tree, 428 best solution, best possible 410.577 (196.31 seconds) After 600 nodes, 294 on tree, 428 best solution, best possible 410.577 (231.18 seconds) After 700 nodes, 344 on tree, 428 best solution, best possible 410.577 (264.64 seconds) After 800 nodes, 395 on tree, 428 best solution, best possible 410.577 (297.79 seconds) After 900 nodes, 444 on tree, 428 best solution, best possible 410.577 (328.57 seconds) After 1000 nodes, 495 on tree, 428 best solution, best possible 410.577 (360.37 seconds) After 1100 nodes, 544 on tree, 428 best solution, best possible 410.577 (394.22 seconds) After 1200 nodes, 594 on tree, 428 best solution, best possible 410.577 (433.00 seconds) After 1300 nodes, 644 on tree, 428 best solution, best possible 410.577 (466.74 seconds) After 1400 nodes, 694 on tree, 428 best solution, best possible 410.577 (501.61 seconds) After 1500 nodes, 744 on tree, 428 best solution, best possible 410.577 (536.68 seconds) After 1600 nodes, 794 on tree, 428 best solution, best possible 410.577 (571.13 seconds) After 1700 nodes, 845 on tree, 428 best solution, best possible 410.577 (606.54 seconds) After 1800 nodes, 895 on tree, 428 best solution, best possible 410.577 (640.30 seconds) After 1900 nodes, 944 on tree, 428 best solution, best possible 410.757 (673.79 seconds) After 2000 nodes, 994 on tree, 428 best solution, best possible 410.757 (709.02 seconds) After 2100 nodes, 1044 on tree, 428 best solution, best possible 410.757 (741.87 seconds) After 2200 nodes, 1094 on tree, 428 best solution, best possible 410.757 (777.36 seconds) After 2300 nodes, 1144 on tree, 428 best solution, best possible 410.757 (809.83 seconds) After 2400 nodes, 1194 on tree, 428 best solution, best possible 410.757 (842.04 seconds) After 2500 nodes, 1244 on tree, 428 best solution, best possible 410.757 (875.07 seconds) After 2600 nodes, 1294 on tree, 428 best solution, best possible 410.757 (908.44 seconds) After 2700 nodes, 1344 on tree, 428 best solution, best possible 410.757 (942.91 seconds) After 2800 nodes, 1394 on tree, 428 best solution, best possible 410.757 (977.83 seconds) After 2900 nodes, 1444 on tree, 428 best solution, best possible 410.757 (1010.46 seconds) After 3000 nodes, 1494 on tree, 428 best solution, best possible 410.757 (1045.56 seconds) After 3100 nodes, 1544 on tree, 428 best solution, best possible 410.757 (1076.41 seconds) After 3200 nodes, 1594 on tree, 428 best solution, best possible 410.757 (1107.97 seconds) After 3300 nodes, 1644 on tree, 428 best solution, best possible 410.757 (1140.65 seconds) After 3400 nodes, 1694 on tree, 428 best solution, best possible 410.757 (1172.85 seconds) After 3500 nodes, 1744 on tree, 428 best solution, best possible 410.757 (1206.02 seconds) After 3600 nodes, 1794 on tree, 428 best solution, best possible 410.757 (1239.30 seconds) After 3700 nodes, 1844 on tree, 428 best solution, best possible 410.757 (1270.92 seconds) After 3800 nodes, 1894 on tree, 428 best solution, best possible 410.757 (1303.23 seconds) After 3900 nodes, 1944 on tree, 428 best solution, best possible 410.757 (1333.90 seconds) After 4000 nodes, 1994 on tree, 428 best solution, best possible 410.757 (1365.83 seconds) After 4100 nodes, 2044 on tree, 428 best solution, best possible 410.757 (1396.58 seconds) After 4200 nodes, 2094 on tree, 428 best solution, best possible 410.757 (1427.07 seconds) After 4300 nodes, 2144 on tree, 428 best solution, best possible 410.757 (1459.05 seconds) After 4400 nodes, 2194 on tree, 428 best solution, best possible 410.757 (1489.81 seconds) After 4500 nodes, 2244 on tree, 428 best solution, best possible 410.757 (1521.98 seconds) After 4600 nodes, 2294 on tree, 428 best solution, best possible 410.757 (1552.57 seconds) After 4700 nodes, 2344 on tree, 428 best solution, best possible 410.757 (1584.19 seconds) After 4800 nodes, 2394 on tree, 428 best solution, best possible 410.757 (1617.20 seconds) After 4900 nodes, 2444 on tree, 428 best solution, best possible 410.757 (1646.97 seconds) After 5000 nodes, 2494 on tree, 428 best solution, best possible 410.757 (1679.12 seconds) After 5100 nodes, 2544 on tree, 428 best solution, best possible 410.757 (1705.74 seconds) After 5200 nodes, 2594 on tree, 428 best solution, best possible 410.757 (1737.33 seconds) After 5300 nodes, 2644 on tree, 428 best solution, best possible 410.757 (1770.40 seconds) After 5400 nodes, 2694 on tree, 428 best solution, best possible 410.757 (1794.98 seconds) Exiting on maximum time Partial search - best objective 428 (best possible 410.757), took 2724561 iterations and 5412 nodes (1798.46 seconds) Strong branching done 1838 times (17910 iterations), fathomed 0 nodes and fixed 0 variables Maximum depth 100, 300 variables fixed on reduced cost Cuts at root node changed objective from 405.469 to 409.227 Probing was tried 5134 times and created 15755 cuts of which 9323 were active after adding rounds of cuts (76.889 seconds) Gomory was tried 1982 times and created 11135 cuts of which 486 were active after adding rounds of cuts (46.079 seconds) Knapsack was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.028 seconds) Clique was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.040 seconds) MixedIntegerRounding2 was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.180 seconds) FlowCover was tried 10 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.228 seconds) TwoMirCuts was tried 10 times and created 330 cuts of which 0 were active after adding rounds of cuts (0.848 seconds) implication was tried 4684 times and created 0 cuts of which 0 were active after adding rounds of cuts Result - Stopped on time objective 428 after 5412 nodes and 2724561 iterations - took 1800.28 seconds (total time 1802.47) Total time 1802.66 Time limit reached. Have feasible solution. MIP solution: 428 (5412 nodes, 1802.66 seconds) Best possible: 410.7566451 Absolute gap: 17.243 (absolute tolerance optca: 0) Relative gap: 0.041979 (relative tolerance optcr: 0) --- Restarting execution --- seymour.gms(124) 0 Mb --- Reading solution for model m --- seymour.gms(124) 4 Mb *** Status: Normal completion --- Job seymour.gms Stop 08/24/08 08:20:13 elapsed 0:30:07.915