[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Re: Feasibility Pump
|
From: |
Louis Wasserman |
|
Subject: |
Re: [Help-glpk] Re: Feasibility Pump |
|
Date: |
Tue, 23 Feb 2010 03:56:26 +0300 |
Successful case:
1.7685s GLPSOL: GLPK LP/MIP Solver, v4.42
1.768574s Parameter(s) specified in the command line:
1.76864s --cpxlp /tmp/esp_lin_prog3357.lpt -o /tmp/esp_solution3357.lpt
--tmlim 90
1.768701s --memlim 600 --fpump --cuts --bestp --pcost --mipgap 0.05
1.768762s Reading problem data from `/tmp/esp_lin_prog3357.lpt #39;...
2.892365s 23120 rows, 62000 columns, 258540 non-zeros
2.892499s 60000 integer variables, all of which are binary
2.892566s 85126 lines were read
3.007392s GLPK Integer Optimizer, v4.42
3.007531s 23120 rows, 62000 columns, 258540 non-zeros
3.007598s 60000 integer variables, all of which are binary
3.007663s Preprocessing...
3.167358s 2160 rows, 25677 columns, 88584 non-zeros
3.167465s 24601 integer variables, all of which are binary
3.167527s Scaling...
3.167585s A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio =
1.000e+00
3.167641s Problem data seem to be well scaled
3.167698s Constructing initial basis...
3.193012s Size of triangular part = 2160
3.193142s Solving LP relaxation...
3.193209s GLPK Simplex Optimizer, v4.42
3.193273s 2160 rows, 25677 columns, 88584 non-zeros
3.21135s * 0: obj = 0.000000000e+00 infeas = 0.000e+00 (0)
3.367328s * 500: obj = 1.068000000e+04 infeas = 0.000e+00 (0)
3.562094s * 1000: obj = 1.337000000e+04 infeas = 0.000e+00 (0)
3.983336s * 1500: obj = 1.397000000e+04 infeas = 0.000e+00 (0)
4.499335s * 2000: obj = 1.397000000e+04 infeas = 0.000e+00 (0)
4.987338s * 2500: obj = 1.403469880e+04 infeas = 8.959e-15 (0)
5.339335s * 3000: obj = 1.427059148e+04 infeas = 2.819e-15 (0)
5.735332s * 3500: obj = 1.447942693e+04 infeas = 2.867e-15 (0)
6.143334s * 4000: obj = 1.460529591e+04 infeas = 4.219e-15 (0)
6.547335s * 4500: obj = 1.468329437e+04 infeas = 3.242e-15 (0)
6.707367s * 4706: obj = 1.470000000e+04 infeas = 3.577e-15 (0)
6.707465s OPTIMAL SOLUTION FOUND
6.707509s Integer optimization begins...
6.707553s Gomory #39;s cuts enabled
6.707598s MIR cuts enabled
6.727336s Cover cuts enabled
6.727434s Clique cuts enabled
6.727482s Creating the conflict graph...
7.271346s The conflict graph is either empty or too big
7.27144s + 4706: mip = not found yet <= +inf
(1; 0)
9.89537s Applying FPUMP heuristic...
9.895468s Pass 1
12.931338s Warning: numerical instability (primal simplex, phase II)
13.007328s Warning: numerical instability (primal simplex, phase II)
13.23133s Warning: numerical instability (primal simplex, phase I)
13.40333s Warning: numerical instability (primal simplex, phase I)
13.555331s Warning: numerical instability (primal simplex, phase I)
13.691331s Warning: numerical instability (primal simplex, phase I)
13.835328s Warning: numerical instability (primal simplex, phase I)
14.111328s Warning: numerical instability (primal simplex, phase I)
14.303329s Warning: numerical instability (primal simplex, phase I)
14.747333s Warning: numerical instability (primal simplex, phase I)
14.899328s Warning: numerical instability (primal simplex, phase II)
15.09533s Warning: numerical instability (primal simplex, phase I)
15.37933s Warning: numerical instability (primal simplex, phase I)
15.575332s Warning: numerical instability (primal simplex, phase I)
15.787329s Warning: numerical instability (primal simplex, phase I)
15.983331s Warning: numerical instability (primal simplex, phase I)
16.391328s Warning: numerical instability (primal simplex, phase I)
...
20.735744s Warning: numerical instability (primal simplex, phase I)
20.935794s Warning: numerical instability (primal simplex, phase I)
21.959824s Warning: numerical instability (primal simplex, phase I)
22.264173s Warning: numerical instability (primal simplex, phase I)
22.399485s Warning: numerical instability (primal simplex, phase I)
23.167345s 17000: obj = 1.137000000e+04 infeas = 8.000e+00 (820)
23.428251s Warning: numerical instability (primal simplex, phase I)
23.430296s 17341: obj = 1.117306998e+04 infeas = 4.600e+01 (803)
23.544755s 17500: obj = 1.115000000e+04 infeas = 1.300e+01 (805)
23.843015s Warning: numerical instability (primal simplex, phase I)
23.845161s 17925: obj = 1.128037522e+04 infeas = 6.345e+01 (822)
23.895195s 18000: obj = 1.129000000e+04 infeas = 8.000e+00 (827)
.....
47.747316s 27000: obj = 1.131000000e+04 infeas = 2.000e+00 (716)
47.763311s * 27014: obj = 1.128000000e+04 infeas = 1.000e+00 (717)
47.763368s Warning: numerical instability (primal simplex, phase II)
47.775319s 27043: obj = 1.131000000e+04 infeas = 4.000e+00 (715)
47.775386s * 27051: obj = 1.125000000e+04 infeas = 1.000e+00 (717)
47.807318s Warning: numerical instability (primal simplex, phase II)
47.816349s 27169: obj = 1.128000000e+04 infeas = 8.000e+00 (712)
47.818356s * 27194: obj = 1.125000000e+04 infeas = 1.000e+00 (711)
47.826246s Warning: numerical instability (primal simplex, phase II)
47.828113s 27217: obj = 1.127000000e+04 infeas = 3.000e+00 (709)
47.830522s * 27220: obj = 1.125000000e+04 infeas = 1.000e+00 (707)
47.832325s Warning: numerical instability (primal simplex, phase II)
47.834127s 27221: obj = 1.126000000e+04 infeas = 2.000e+00 (708)
47.836149s * 27223: obj = 1.125000000e+04 infeas = 1.000e+00 (707)
47.837945s Warning: numerical instability (primal simplex, phase II)
47.839752s 27224: obj = 1.126000000e+04 infeas = 2.000e+00 (708)
47.84222s * 27227: obj = 1.125000000e+04 infeas = 1.000e+00 (707)
47.844965s Warning: numerical instability (primal simplex, phase II)
47.846767s 27231: obj = 1.124000000e+04 infeas = 2.800e+01 (707)
47.852265s * 27244: obj = 1.122000000e+04 infeas = 0.000e+00 (707)
47.857276s * 27252: obj = 1.122000000e+04 infeas = 0.000e+00 (705)
47.861021s Solution found by heuristic: 11220
47.887666s Pass 1
51.14672s Warning: numerical instability (primal simplex, phase II)
51.254547s Warning: numerical instability (primal simplex, phase II)
51.443595s Warning: numerical instability (primal simplex, phase I)
....
67.727952s Warning: numerical instability (primal simplex, phase II)
67.74046s 27566: obj = 1.163000000e+04 infeas = 1.000e+00 (695)
67.740579s * 27567: obj = 1.162000000e+04 infeas = 0.000e+00 (694)
67.740633s * 27576: obj = 1.162000000e+04 infeas = 0.000e+00 (694)
67.740683s Solution found by heuristic: 11620
Unsuccessful case:
9.616589s GLPSOL: GLPK LP/MIP Solver, v4.42
9.616659s Parameter(s) specified in the command line:
9.616728s --cpxlp /tmp/esp_lin_prog4902.lpt -o /tmp/esp_solution4902.lpt
--tmlim 1200
9.616789s --memlim 600 --fpump --cuts --bestp --pcost --mipgap 0.05
9.61686s Reading problem data from `/tmp/esp_lin_prog4902.lpt #39;...
14.705768s 84950 rows, 241516 columns, 1161600 non-zeros
14.736345s 236250 integer variables, all of which are binary
14.736466s 326457 lines were read
15.168325s GLPK Integer Optimizer, v4.42
15.168461s 84950 rows, 241516 columns, 1161600 non-zeros
15.168529s 236250 integer variables, all of which are binary
15.168594s Preprocessing...
16.084342s 5515 rows, 95659 columns, 439873 non-zeros
16.084466s 92435 integer variables, all of which are binary
16.084527s Scaling...
16.132371s A: min|aij| = 1.000e+00 max|aij| = 7.532e+04 ratio =
7.532e+04
16.500318s GM: min|aij| = 2.077e-01 max|aij| = 4.815e+00 ratio =
2.318e+01
16.600311s EQ: min|aij| = 4.313e-02 max|aij| = 1.000e+00 ratio =
2.318e+01
16.668333s 2N: min|aij| = 2.930e-02 max|aij| = 1.614e+00 ratio =
5.510e+01
16.668505s Constructing initial basis...
16.804315s Size of triangular part = 5365
16.824358s Solving LP relaxation...
16.82451s GLPK Simplex Optimizer, v4.42
16.824787s 5515 rows, 95659 columns, 439873 non-zeros
16.86433s * 0: obj = -3.000000000e+01 infeas = 0.000e+00 (150)
17.524316s * 500: obj = 4.257736462e+04 infeas = 4.516e-15 (92)
18.420327s * 1000: obj = 6.068111111e+04 infeas = 5.551e-16 (79)
19.360304s * 1500: obj = 6.739561487e+04 infeas = 8.119e-16 (70)
20.296308s * 2000: obj = 8.859694732e+04 infeas = 8.377e-14 (68)
21.256304s * 2500: obj = 9.162419355e+04 infeas = 1.926e-15 (65)
22.084305s * 3000: obj = 1.001921140e+05 infeas = 8.327e-17 (62)
.........................
402.400317s *130500: obj = 6.278742485e+05 infeas = 2.497e-14 (0)
403.876305s *131000: obj = 6.279185020e+05 infeas = 3.903e-14 (0)
405.120316s *131500: obj = 6.279290912e+05 infeas = 1.901e-14 (0)
406.300313s *132000: obj = 6.279511947e+05 infeas = 1.159e-14 (0)
407.628318s *132500: obj = 6.279906589e+05 infeas = 6.285e-14 (0)
409.212328s *133000: obj = 6.280333833e+05 infeas = 2.288e-14 (0)
410.340314s *133500: obj = 6.280547177e+05 infeas = 3.539e-14 (0)
411.90431s *134000: obj = 6.280896172e+05 infeas = 3.474e-14 (0)
413.248329s *134500: obj = 6.281269362e+05 infeas = 1.622e-14 (0)
414.936368s *135000: obj = 6.281495737e+05 infeas = 1.821e-14 (0)
415.924372s *135375: obj = 6.281588968e+05 infeas = 5.230e-14 (0)
415.924619s OPTIMAL SOLUTION FOUND
415.944364s Integer optimization begins...
415.944498s Gomory #39;s cuts enabled
415.944583s MIR cuts enabled
416.004301s Cover cuts enabled
416.004389s Clique cuts enabled
416.004434s Creating the conflict graph...
419.944311s The conflict graph is either empty or too big
419.944408s +135375: mip = not found yet <= +inf
(1; 0)
430.816306s |137000: obj = 6.281588968e+05 infeas = 1.279e-09 (0)
434.008313s |137500: obj = 6.281588968e+05 infeas = 4.095e-10 (0)
437.104311s |138000: obj = 6.281588968e+05 infeas = 5.192e-10 (0)
439.824312s |138500: obj = 6.281588968e+05 infeas = 4.817e-10 (0)
442.912308s |139000: obj = 6.281588968e+05 infeas = 4.381e-10 (0)
445.824312s |139500: obj = 6.281588968e+05 infeas = 5.841e-10 (0)
448.744309s |140000: obj = 6.281588968e+05 infeas = 3.702e-10 (0)
451.93631s |140500: obj = 6.281588968e+05 infeas = 4.055e-10 (0)
455.31632s |141000: obj = 6.281588968e+05 infeas = 3.728e-10 (0)
458.424312s |141500: obj = 6.281588968e+05 infeas = 3.749e-10 (0)
461.800309s |142000: obj = 6.281588968e+05 infeas = 3.718e-10 (0)
465.060322s |142500: obj = 6.281588968e+05 infeas = 4.039e-10 (0)
468.652321s |143000: obj = 6.281588968e+05 infeas = 3.858e-10 (0)
After this point, it goes an hour without making progress. In particular, it
never outputs "Applying FPUMP heuristic" like the successful case.
My best guess is that there aren #39;t many integer solutions at all...
Louis Wasserman
address@hidden
http://profiles.google.com/wasserman.louis
On Mon, Feb 22, 2010 at 4:08 AM, Andrew Makhorin <address@hidden> wrote:
> I #39;m using glpsol to solve sizable MIP problems (~50,000 binary
> variables after presolving), using the command line options "--tmlim
> 90 --memlim 400 --fpump --cuts --bestp --mipgap 0.05". For problems
> of a certain size, the readout indicates that the "feasibility pump"
> kicks in relatively quickly, after which the problem is solved
> rapidly. For problems above a certain point, however, it does not
> seem to kick in. What can I do to improve matters?
In fpump there is no artifical limit to the number of variables. Thus,
if it cannot find a feasible solution, it may mean that the particular
instance is hard for the fpump heuristic. Could you provide the complete
terminal output for successful and unsuccessful cases? Thanks.
Andrew Makhorin
Successful case:
1.7685s GLPSOL: GLPK LP/MIP Solver, v4.42
1.768574s Parameter(s) specified in the command line:
1.76864s --cpxlp /tmp/esp_lin_prog3357.lpt -o /tmp/esp_solution3357.lpt --tmlim 90
1.768701s --memlim 600 --fpump --cuts --bestp --pcost --mipgap 0.05
1.768762s Reading problem data from `/tmp/esp_lin_prog3357.lpt'...
2.892365s 23120 rows, 62000 columns, 258540 non-zeros
2.892499s 60000 integer variables, all of which are binary
2.892566s 85126 lines were read
3.007392s GLPK Integer Optimizer, v4.42
3.007531s 23120 rows, 62000 columns, 258540 non-zeros
3.007598s 60000 integer variables, all of which are binary
3.007663s Preprocessing...
3.167358s 2160 rows, 25677 columns, 88584 non-zeros
3.167465s 24601 integer variables, all of which are binary
3.167527s Scaling...
3.167585s A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00
3.167641s Problem data seem to be well scaled
3.167698s Constructing initial basis...
3.193012s Size of triangular part = 2160
3.193142s Solving LP relaxation...
3.193209s GLPK Simplex Optimizer, v4.42
3.193273s 2160 rows, 25677 columns, 88584 non-zeros
3.21135s * 0: obj = 0.000000000e+00 infeas = 0.000e+00 (0)
3.367328s * 500: obj = 1.068000000e+04 infeas = 0.000e+00 (0)
3.562094s * 1000: obj = 1.337000000e+04 infeas = 0.000e+00 (0)
3.983336s * 1500: obj = 1.397000000e+04 infeas = 0.000e+00 (0)
4.499335s * 2000: obj = 1.397000000e+04 infeas = 0.000e+00 (0)
4.987338s * 2500: obj = 1.403469880e+04 infeas = 8.959e-15 (0)
5.339335s * 3000: obj = 1.427059148e+04 infeas = 2.819e-15 (0)
5.735332s * 3500: obj = 1.447942693e+04 infeas = 2.867e-15 (0)
6.143334s * 4000: obj = 1.460529591e+04 infeas = 4.219e-15 (0)
6.547335s * 4500: obj = 1.468329437e+04 infeas = 3.242e-15 (0)
6.707367s * 4706: obj = 1.470000000e+04 infeas = 3.577e-15 (0)
6.707465s OPTIMAL SOLUTION FOUND
6.707509s Integer optimization begins...
6.707553s Gomory's cuts enabled
6.707598s MIR cuts enabled
6.727336s Cover cuts enabled
6.727434s Clique cuts enabled
6.727482s Creating the conflict graph...
7.271346s The conflict graph is either empty or too big
7.27144s + 4706: mip = not found yet <= +inf (1; 0)
9.89537s Applying FPUMP heuristic...
9.895468s Pass 1
12.931338s Warning: numerical instability (primal simplex, phase II)
13.007328s Warning: numerical instability (primal simplex, phase II)
13.23133s Warning: numerical instability (primal simplex, phase I)
13.40333s Warning: numerical instability (primal simplex, phase I)
13.555331s Warning: numerical instability (primal simplex, phase I)
13.691331s Warning: numerical instability (primal simplex, phase I)
13.835328s Warning: numerical instability (primal simplex, phase I)
14.111328s Warning: numerical instability (primal simplex, phase I)
14.303329s Warning: numerical instability (primal simplex, phase I)
14.747333s Warning: numerical instability (primal simplex, phase I)
14.899328s Warning: numerical instability (primal simplex, phase II)
15.09533s Warning: numerical instability (primal simplex, phase I)
15.37933s Warning: numerical instability (primal simplex, phase I)
15.575332s Warning: numerical instability (primal simplex, phase I)
15.787329s Warning: numerical instability (primal simplex, phase I)
15.983331s Warning: numerical instability (primal simplex, phase I)
16.391328s Warning: numerical instability (primal simplex, phase I)
...
20.735744s Warning: numerical instability (primal simplex, phase I)
20.935794s Warning: numerical instability (primal simplex, phase I)
21.959824s Warning: numerical instability (primal simplex, phase I)
22.264173s Warning: numerical instability (primal simplex, phase I)
22.399485s Warning: numerical instability (primal simplex, phase I)
23.167345s 17000: obj = 1.137000000e+04 infeas = 8.000e+00 (820)
23.428251s Warning: numerical instability (primal simplex, phase I)
23.430296s 17341: obj = 1.117306998e+04 infeas = 4.600e+01 (803)
23.544755s 17500: obj = 1.115000000e+04 infeas = 1.300e+01 (805)
23.843015s Warning: numerical instability (primal simplex, phase I)
23.845161s 17925: obj = 1.128037522e+04 infeas = 6.345e+01 (822)
23.895195s 18000: obj = 1.129000000e+04 infeas = 8.000e+00 (827)
.....
47.747316s 27000: obj = 1.131000000e+04 infeas = 2.000e+00 (716)
47.763311s * 27014: obj = 1.128000000e+04 infeas = 1.000e+00 (717)
47.763368s Warning: numerical instability (primal simplex, phase II)
47.775319s 27043: obj = 1.131000000e+04 infeas = 4.000e+00 (715)
47.775386s * 27051: obj = 1.125000000e+04 infeas = 1.000e+00 (717)
47.807318s Warning: numerical instability (primal simplex, phase II)
47.816349s 27169: obj = 1.128000000e+04 infeas = 8.000e+00 (712)
47.818356s * 27194: obj = 1.125000000e+04 infeas = 1.000e+00 (711)
47.826246s Warning: numerical instability (primal simplex, phase II)
47.828113s 27217: obj = 1.127000000e+04 infeas = 3.000e+00 (709)
47.830522s * 27220: obj = 1.125000000e+04 infeas = 1.000e+00 (707)
47.832325s Warning: numerical instability (primal simplex, phase II)
47.834127s 27221: obj = 1.126000000e+04 infeas = 2.000e+00 (708)
47.836149s * 27223: obj = 1.125000000e+04 infeas = 1.000e+00 (707)
47.837945s Warning: numerical instability (primal simplex, phase II)
47.839752s 27224: obj = 1.126000000e+04 infeas = 2.000e+00 (708)
47.84222s * 27227: obj = 1.125000000e+04 infeas = 1.000e+00 (707)
47.844965s Warning: numerical instability (primal simplex, phase II)
47.846767s 27231: obj = 1.124000000e+04 infeas = 2.800e+01 (707)
47.852265s * 27244: obj = 1.122000000e+04 infeas = 0.000e+00 (707)
47.857276s * 27252: obj = 1.122000000e+04 infeas = 0.000e+00 (705)
47.861021s Solution found by heuristic: 11220
47.887666s Pass 1
51.14672s Warning: numerical instability (primal simplex, phase II)
51.254547s Warning: numerical instability (primal simplex, phase II)
51.443595s Warning: numerical instability (primal simplex, phase I)
....
67.727952s Warning: numerical instability (primal simplex, phase II)
67.74046s 27566: obj = 1.163000000e+04 infeas = 1.000e+00 (695)
67.740579s * 27567: obj = 1.162000000e+04 infeas = 0.000e+00 (694)
67.740633s * 27576: obj = 1.162000000e+04 infeas = 0.000e+00 (694)
67.740683s Solution found by heuristic: 11620
Unsuccessful case:
9.616589s GLPSOL: GLPK LP/MIP Solver, v4.42
9.616659s Parameter(s) specified in the command line:
9.616728s --cpxlp /tmp/esp_lin_prog4902.lpt -o /tmp/esp_solution4902.lpt --tmlim 1200
9.616789s --memlim 600 --fpump --cuts --bestp --pcost --mipgap 0.05
9.61686s Reading problem data from `/tmp/esp_lin_prog4902.lpt'...
14.705768s 84950 rows, 241516 columns, 1161600 non-zeros
14.736345s 236250 integer variables, all of which are binary
14.736466s 326457 lines were read
15.168325s GLPK Integer Optimizer, v4.42
15.168461s 84950 rows, 241516 columns, 1161600 non-zeros
15.168529s 236250 integer variables, all of which are binary
15.168594s Preprocessing...
16.084342s 5515 rows, 95659 columns, 439873 non-zeros
16.084466s 92435 integer variables, all of which are binary
16.084527s Scaling...
16.132371s A: min|aij| = 1.000e+00 max|aij| = 7.532e+04 ratio = 7.532e+04
16.500318s GM: min|aij| = 2.077e-01 max|aij| = 4.815e+00 ratio = 2.318e+01
16.600311s EQ: min|aij| = 4.313e-02 max|aij| = 1.000e+00 ratio = 2.318e+01
16.668333s 2N: min|aij| = 2.930e-02 max|aij| = 1.614e+00 ratio = 5.510e+01
16.668505s Constructing initial basis...
16.804315s Size of triangular part = 5365
16.824358s Solving LP relaxation...
16.82451s GLPK Simplex Optimizer, v4.42
16.824787s 5515 rows, 95659 columns, 439873 non-zeros
16.86433s * 0: obj = -3.000000000e+01 infeas = 0.000e+00 (150)
17.524316s * 500: obj = 4.257736462e+04 infeas = 4.516e-15 (92)
18.420327s * 1000: obj = 6.068111111e+04 infeas = 5.551e-16 (79)
19.360304s * 1500: obj = 6.739561487e+04 infeas = 8.119e-16 (70)
20.296308s * 2000: obj = 8.859694732e+04 infeas = 8.377e-14 (68)
21.256304s * 2500: obj = 9.162419355e+04 infeas = 1.926e-15 (65)
22.084305s * 3000: obj = 1.001921140e+05 infeas = 8.327e-17 (62)
.........................
402.400317s *130500: obj = 6.278742485e+05 infeas = 2.497e-14 (0)
403.876305s *131000: obj = 6.279185020e+05 infeas = 3.903e-14 (0)
405.120316s *131500: obj = 6.279290912e+05 infeas = 1.901e-14 (0)
406.300313s *132000: obj = 6.279511947e+05 infeas = 1.159e-14 (0)
407.628318s *132500: obj = 6.279906589e+05 infeas = 6.285e-14 (0)
409.212328s *133000: obj = 6.280333833e+05 infeas = 2.288e-14 (0)
410.340314s *133500: obj = 6.280547177e+05 infeas = 3.539e-14 (0)
411.90431s *134000: obj = 6.280896172e+05 infeas = 3.474e-14 (0)
413.248329s *134500: obj = 6.281269362e+05 infeas = 1.622e-14 (0)
414.936368s *135000: obj = 6.281495737e+05 infeas = 1.821e-14 (0)
415.924372s *135375: obj = 6.281588968e+05 infeas = 5.230e-14 (0)
415.924619s OPTIMAL SOLUTION FOUND
415.944364s Integer optimization begins...
415.944498s Gomory's cuts enabled
415.944583s MIR cuts enabled
416.004301s Cover cuts enabled
416.004389s Clique cuts enabled
416.004434s Creating the conflict graph...
419.944311s The conflict graph is either empty or too big
419.944408s +135375: mip = not found yet <= +inf (1; 0)
430.816306s |137000: obj = 6.281588968e+05 infeas = 1.279e-09 (0)
434.008313s |137500: obj = 6.281588968e+05 infeas = 4.095e-10 (0)
437.104311s |138000: obj = 6.281588968e+05 infeas = 5.192e-10 (0)
439.824312s |138500: obj = 6.281588968e+05 infeas = 4.817e-10 (0)
442.912308s |139000: obj = 6.281588968e+05 infeas = 4.381e-10 (0)
445.824312s |139500: obj = 6.281588968e+05 infeas = 5.841e-10 (0)
448.744309s |140000: obj = 6.281588968e+05 infeas = 3.702e-10 (0)
451.93631s |140500: obj = 6.281588968e+05 infeas = 4.055e-10 (0)
455.31632s |141000: obj = 6.281588968e+05 infeas = 3.728e-10 (0)
458.424312s |141500: obj = 6.281588968e+05 infeas = 3.749e-10 (0)
461.800309s |142000: obj = 6.281588968e+05 infeas = 3.718e-10 (0)
465.060322s |142500: obj = 6.281588968e+05 infeas = 4.039e-10 (0)
468.652321s |143000: obj = 6.281588968e+05 infeas = 3.858e-10 (0)
After this point, it goes an hour without making progress. In particular, it never outputs "Applying FPUMP heuristic" like the successful case.
My best guess is that there aren't many integer solutions at all...
Louis Wasserman
address@hidden
http://profiles.google.com/wasserman.louis
On Mon, Feb 22, 2010 at 4:08 AM, Andrew Makhorin
<address@hidden> wrote:
> I'm using glpsol to solve sizable MIP problems (~50,000 binary
> variables after presolving), using the command line options "--tmlim
> 90 --memlim 400 --fpump --cuts --bestp --mipgap 0.05". For problems
> of a certain size, the readout indicates that the "feasibility pump"
> kicks in relatively quickly, after which the problem is solved
> rapidly. For problems above a certain point, however, it does not
> seem to kick in. What can I do to improve matters?
In fpump there is no artifical limit to the number of variables. Thus,
if it cannot find a feasible solution, it may mean that the particular
instance is hard for the fpump heuristic. Could you provide the complete
terminal output for successful and unsuccessful cases? Thanks.
Andrew Makhorin