Re: Is it possible to feed glpsol with a feasible initial solution to a MIP problem?
Alejandro Pascual <[email protected]>
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <CANPvAP09u5BV7bdrPsQ==LkoFKPJWDweDwAJhLOi4Umf2YzQ1Q@mail.gmail.com> |
Dear Andrew, Thanks for your quick reply, I'm still a beginner with GLPK and haven't noticed the -w and --ini options. I've tried the --fpump option with no success (even after waiting for days), and after your suggestion, the --proxy option with 5400 seconds without success either. I attach the model and data files. Setting the binary variables to one, glpsol can find a feasible solution. Now I'am trying the -w, --ini sequence of two consecutive glpsol executions (-w to save the solution obtained with the binary variables set to one, and --ini to feed this solution as a feasible solution to the original MIP problem). After the LP relaxation, the second execution is warning me: basis matrix is ill-conditioned (cond = 3.27e+13). I guess the instance of the problem is just too hard, but I am not sure if the integer optimization stage is actually using the feasible solution I intended to provide. ¿How should I understand the attached log file? Thank you very much for your help. Best regards, Alejandro 2018-04-06 6:13 GMT-03:00 Andrew Makhorin <[email protected]>: > On Thu, 2018-04-05 at 14:40 -0300, Alejandro Pascual wrote: >> Hi, >> >> I am working on a MIP problem for which glpsol can't find a feasible >> solution in a reasonable amount of time. However, fixing the values of >> the integer variables (which are all binary) to one, I can get glpsol >> to find an optimum solution rather quickly. Is it possible to feed >> this solution as initial (suboptimal) solution of the original >> problem? > > Yes. Save the mip solution found with 'glpsol ... -w FILENAME' and then > specify it as initial one 'glpsol ... --ini FILENAME'. > > BTW, did you try using --fpump or --proxy to find a feasible solution? > >> >> I have read in the help-list that this was not possible with MathProg >> in 2007, but maybe now it is. If it is not, what would be the most >> direct way to hack the code in order to do so? >> >> Regards, >> Alejandro Pascual >> >> _______________________________________________ >> Help-glpk mailing list >> [email protected] >> https://lists.gnu.org/mailman/listinfo/help-glpk >> > > _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
localiz.mod
(video/mpeg, 1.9 KB) - not displayed
localiz.dat
(application/octet-stream, 11 KB) - not displayed
localiz1.log
(text/x-log, 13 KB)
GLPSOL: GLPK LP/MIP Solver, v4.61
Parameter(s) specified in the command line:
-m localiz.mod -d localiz.dat -o localiz1.out -y localiz1.dsp -w localiz1.sol
--log localiz1.log --ini localiz0.sol --tmlim 14400 --presol --cuts
Reading model section from localiz.mod...
199 lines were read
Reading data section from localiz.dat...
180 lines were read
Generating costoInstTot...
Generating Def_y_p1...
Generating Def_y_p2...
Generating Dem...
Generating Cap...
Generating BalFluj...
Generating PriProx...
Generating SecProx...
Model has been successfully generated
GLPK Integer Optimizer, v4.61
6870691 rows, 407396 columns, 14547048 non-zeros
78 integer variables, all of which are binary
Preprocessing...
6861842 constraint coefficient(s) were reduced
6870690 rows, 407396 columns, 14546970 non-zeros
78 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 3.000e+00 ratio = 3.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 6870690
Solving LP relaxation...
GLPK Simplex Optimizer, v4.61
6870690 rows, 407396 columns, 14546970 non-zeros
0: obj = 0.000000000e+00 inf = 7.200e+02 (240)
500: obj = 1.900000000e+04 inf = 4.080e+02 (136)
1000: obj = 1.900000000e+04 inf = 4.080e+02 (136)
1500: obj = 1.900000000e+04 inf = 4.080e+02 (136)
2000: obj = 1.900000000e+04 inf = 4.080e+02 (136) 1
2500: obj = 1.900000000e+04 inf = 4.080e+02 (136)
3000: obj = 1.900000000e+04 inf = 4.080e+02 (136) 1
3500: obj = 9.928571429e+04 inf = 1.650e+01 (7) 2
4000: obj = 1.035802469e+05 inf = 1.481e+00 (3) 3
4217: obj = 1.039014845e+05 inf = 1.608e-12 (0) 2
* 4500: obj = 8.103703704e+04 inf = 3.122e-12 (614) 2
* 5000: obj = 6.950000000e+04 inf = 9.209e-15 (429) 3
* 5500: obj = 6.370111732e+04 inf = 1.114e-15 (750) 4
* 6000: obj = 6.070000000e+04 inf = 1.889e-14 (691) 3
* 6500: obj = 5.690458015e+04 inf = 1.446e-14 (862) 3
* 7000: obj = 4.208171206e+04 inf = 2.470e-13 (1288) 3
* 7500: obj = 3.967287449e+04 inf = 3.558e-15 (1221) 3
* 8000: obj = 3.783668419e+04 inf = 0.000e+00 (1316) 4
* 8500: obj = 3.593724490e+04 inf = 4.963e-16 (1281) 4
* 9000: obj = 3.475455483e+04 inf = 1.208e-19 (895) 4
* 9500: obj = 3.386136050e+04 inf = 3.094e-17 (2042) 3
* 10000: obj = 3.327272727e+04 inf = 2.336e-31 (892) 4
* 10500: obj = 3.264640884e+04 inf = 6.371e-17 (1277) 4
* 11000: obj = 3.196825397e+04 inf = 7.806e-15 (665) 3
* 11500: obj = 3.166666667e+04 inf = 5.710e-13 (25) 3
* 12000: obj = 3.140816327e+04 inf = 1.813e-15 (442) 3
* 12500: obj = 3.118867925e+04 inf = 1.493e-12 (587) 4
* 13000: obj = 3.097374179e+04 inf = 4.420e-15 (999) 4
* 13500: obj = 3.092335329e+04 inf = 5.705e-14 (1340) 2
* 14000: obj = 3.069230769e+04 inf = 2.301e-12 (854) 3
* 14500: obj = 3.069230769e+04 inf = 1.880e-13 (648) 3
* 15000: obj = 3.056521739e+04 inf = 1.265e-15 (260) 3
* 15500: obj = 3.040000000e+04 inf = 2.100e-13 (457) 4
* 16000: obj = 3.040000000e+04 inf = 2.352e-13 (72) 3
* 16500: obj = 3.040000000e+04 inf = 1.221e-14 (394) 4
* 17000: obj = 3.033333333e+04 inf = 3.556e-15 (861) 3
* 17500: obj = 3.024800000e+04 inf = 1.055e-14 (638) 4
* 18000: obj = 3.020512821e+04 inf = 6.433e-15 (716) 3
* 18500: obj = 3.012195122e+04 inf = 5.669e-16 (263) 3
* 19000: obj = 3.006329114e+04 inf = 4.827e-15 (534) 3
* 19500: obj = 3.000000000e+04 inf = 6.592e-15 (317) 3
* 20000: obj = 2.985714286e+04 inf = 9.449e-14 (301) 3
* 20500: obj = 2.985714286e+04 inf = 3.841e-14 (78) 4
* 20586: obj = 2.985714286e+04 inf = 6.439e-13 (0) 1
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Gomory's cuts enabled
MIR cuts enabled
Cover cuts enabled
Clique cuts enabled
Constructing conflict graph...
No conflicts found
+ 20586: mip = not found yet >= -inf (1; 0)
+ 20586: mip = not found yet >= 3.000000000e+04 (1; 0)
Time used: 60.5 secs. Memory used: 10467.7 Mb.
# 21000: obj = 3.247368421e+04 inf = 0.000e+00 (9843) 3
# 21500: obj = 3.247368421e+04 inf = 0.000e+00 (24305) 5
# 22000: obj = 3.247368421e+04 inf = 0.000e+00 (21464) 5
# 22500: obj = 3.362500000e+04 inf = 0.000e+00 (19576) 5
# 23000: obj = 3.362500000e+04 inf = 0.000e+00 (19294) 5
# 23500: obj = 3.362500000e+04 inf = 0.000e+00 (19511) 5
# 24000: obj = 3.362500000e+04 inf = 0.000e+00 (19866) 5
# 24500: obj = 3.362500000e+04 inf = 0.000e+00 (4716) 5
# 25000: obj = 3.362500000e+04 inf = 0.000e+00 (15084) 5
# 25500: obj = 3.362500000e+04 inf = 0.000e+00 (5529) 5
# 26000: obj = 3.362500000e+04 inf = 0.000e+00 (9974) 5
# 26136: obj = 3.362500000e+04 inf = 2.137e-10 (0) 1
+ 26136: mip = not found yet >= 3.400000000e+04 (1; 0)
Time used: 1470.1 secs. Memory used: 10998.5 Mb.
# 26500: obj = 3.574193548e+04 inf = 0.000e+00 (121660) 3
# 27000: obj = 3.574193548e+04 inf = 0.000e+00 (143796) 5
# 27500: obj = 3.574193548e+04 inf = 0.000e+00 (19471) 5
# 28000: obj = 3.574193548e+04 inf = 0.000e+00 (24461) 5
# 28500: obj = 3.574193548e+04 inf = 0.000e+00 (21593) 4
# 29000: obj = 3.574193548e+04 inf = 0.000e+00 (15970) 4
# 29500: obj = 3.574193548e+04 inf = 0.000e+00 (76413) 3
# 30000: obj = 3.574193549e+04 inf = 0.000e+00 (138570) 5
# 30500: obj = 3.574193549e+04 inf = 0.000e+00 (16036) 3
# 31000: obj = 3.574193549e+04 inf = 0.000e+00 (20971) 5
# 31500: obj = 3.574193549e+04 inf = 0.000e+00 (16623) 3
# 32000: obj = 3.574193549e+04 inf = 0.000e+00 (16652) 5
# 32500: obj = 3.574193549e+04 inf = 0.000e+00 (17307) 3
# 33000: obj = 3.574193550e+04 inf = 0.000e+00 (88779) 5
# 33500: obj = 3.574193550e+04 inf = 0.000e+00 (14926) 4
# 34000: obj = 3.574193552e+04 inf = 0.000e+00 (15895) 5
# 34500: obj = 3.574193554e+04 inf = 0.000e+00 (20947) 4
# 35000: obj = 3.574193554e+04 inf = 0.000e+00 (20930) 5
# 35500: obj = 3.574193557e+04 inf = 0.000e+00 (20981) 4
# 36000: obj = 3.574193558e+04 inf = 0.000e+00 (20870) 5
# 36500: obj = 3.574193560e+04 inf = 0.000e+00 (20476) 5
# 37000: obj = 3.574193567e+04 inf = 0.000e+00 (19571) 4
# 37500: obj = 3.574193577e+04 inf = 0.000e+00 (181461) 4
# 38000: obj = 3.574193590e+04 inf = 0.000e+00 (20369) 5
# 38500: obj = 3.574193601e+04 inf = 0.000e+00 (143927) 4
# 39000: obj = 3.574193618e+04 inf = 0.000e+00 (24486) 5
# 39500: obj = 3.574193630e+04 inf = 0.000e+00 (19614) 5
# 40000: obj = 3.574193661e+04 inf = 0.000e+00 (19552) 5
# 40500: obj = 3.574193663e+04 inf = 0.000e+00 (20145) 3
# 41000: obj = 3.574193669e+04 inf = 0.000e+00 (20317) 4
# 41500: obj = 3.574193677e+04 inf = 0.000e+00 (20270) 4
# 42000: obj = 3.574193680e+04 inf = 0.000e+00 (20428) 5
# 42500: obj = 3.574193704e+04 inf = 0.000e+00 (25558) 4
# 43000: obj = 3.574193749e+04 inf = 0.000e+00 (160419) 4
# 43500: obj = 3.574193760e+04 inf = 0.000e+00 (29464) 5
# 44000: obj = 3.574193892e+04 inf = 0.000e+00 (25430) 2
# 44500: obj = 3.574193913e+04 inf = 0.000e+00 (22952) 4
# 45000: obj = 3.574193921e+04 inf = 0.000e+00 (18155) 5
# 45500: obj = 3.574193930e+04 inf = 0.000e+00 (164628) 2
# 46000: obj = 3.574193943e+04 inf = 0.000e+00 (161754) 5
# 46500: obj = 3.574193937e+04 inf = 0.000e+00 (26905) 3
# 47000: obj = 3.574193945e+04 inf = 0.000e+00 (27018) 5
# 47500: obj = 3.574193948e+04 inf = 0.000e+00 (27166) 2
# 48000: obj = 3.574193951e+04 inf = 0.000e+00 (25049) 4
# 48500: obj = 3.574193952e+04 inf = 0.000e+00 (156590) 3
# 49000: obj = 3.574193946e+04 inf = 0.000e+00 (38056) 4
# 49500: obj = 3.574193969e+04 inf = 0.000e+00 (25235) 5
# 50000: obj = 3.574194023e+04 inf = 0.000e+00 (24603) 4
# 50500: obj = 3.574194034e+04 inf = 0.000e+00 (30797) 4
# 51000: obj = 3.574194038e+04 inf = 0.000e+00 (29210) 4
# 51500: obj = 3.574194046e+04 inf = 0.000e+00 (26262) 4
# 52000: obj = 3.574194049e+04 inf = 0.000e+00 (24102) 5
# 52500: obj = 3.574194058e+04 inf = 0.000e+00 (23042) 4
# 53000: obj = 3.574194062e+04 inf = 0.000e+00 (22927) 5
# 53500: obj = 3.574194069e+04 inf = 0.000e+00 (22934) 5
# 54000: obj = 3.574194072e+04 inf = 0.000e+00 (22873) 5
# 54500: obj = 3.574194079e+04 inf = 0.000e+00 (22491) 4
# 55000: obj = 3.574194110e+04 inf = 0.000e+00 (22822) 5
# 55500: obj = 3.574194118e+04 inf = 0.000e+00 (22719) 5
# 56000: obj = 3.574194127e+04 inf = 0.000e+00 (22813) 5
# 56500: obj = 3.574194140e+04 inf = 0.000e+00 (22507) 5
# 57000: obj = 3.574194159e+04 inf = 0.000e+00 (17733) 5
# 57500: obj = 3.574194163e+04 inf = 0.000e+00 (17448) 5
# 58000: obj = 3.574194173e+04 inf = 0.000e+00 (16390) 5
# 58500: obj = 3.574194238e+04 inf = 0.000e+00 (16814) 4
# 59000: obj = 3.574194250e+04 inf = 0.000e+00 (12704) 5
# 59500: obj = 3.574194263e+04 inf = 0.000e+00 (12373) 4
# 60000: obj = 3.574194266e+04 inf = 0.000e+00 (12264) 5
# 60500: obj = 3.574194268e+04 inf = 0.000e+00 (12010) 5
# 61000: obj = 3.574194271e+04 inf = 0.000e+00 (11754) 5
# 61500: obj = 3.574194272e+04 inf = 0.000e+00 (11801) 5
# 62000: obj = 3.574194273e+04 inf = 0.000e+00 (11890) 5
# 62500: obj = 3.574194273e+04 inf = 0.000e+00 (11670) 5
# 63000: obj = 3.574194274e+04 inf = 0.000e+00 (11727) 5
# 63500: obj = 3.587500399e+04 inf = 0.000e+00 (112022) 5
# 64000: obj = 3.587500423e+04 inf = 0.000e+00 (111876) 5
# 64500: obj = 3.587500442e+04 inf = 0.000e+00 (111703) 4
# 65000: obj = 3.587500451e+04 inf = 0.000e+00 (112083) 5
Warning: basis matrix is ill-conditioned (cond = 3.69e+13)
Warning: basis matrix is ill-conditioned (cond = 3.64e+13)
# 65500: obj = 3.587500498e+04 inf = 0.000e+00 (236223) 4
Warning: basis matrix is ill-conditioned (cond = 3.62e+13)
Warning: basis matrix is ill-conditioned (cond = 2.64e+13)
Warning: basis matrix is ill-conditioned (cond = 2.83e+13)
Warning: basis matrix is ill-conditioned (cond = 2.84e+13)
Warning: basis matrix is ill-conditioned (cond = 2.84e+13)
# 66000: obj = 3.587500737e+04 inf = 0.000e+00 (256029) 5
Warning: basis matrix is ill-conditioned (cond = 2.85e+13)
Warning: basis matrix is ill-conditioned (cond = 2.89e+13)
Warning: basis matrix is ill-conditioned (cond = 2.82e+13)
# 66500: obj = 3.587500853e+04 inf = 0.000e+00 (256913) 3
Warning: basis matrix is ill-conditioned (cond = 2.96e+13)
Warning: basis matrix is ill-conditioned (cond = 2.19e+13)
# 67000: obj = 3.587501021e+04 inf = 0.000e+00 (317690) 2
Warning: basis matrix is ill-conditioned (cond = 2.2e+13)
Warning: basis matrix is ill-conditioned (cond = 2.21e+13)
Warning: basis matrix is ill-conditioned (cond = 2.86e+13)
# 67500: obj = 3.587501092e+04 inf = 0.000e+00 (301285) 3
Warning: basis matrix is ill-conditioned (cond = 2.86e+13)
Warning: basis matrix is ill-conditioned (cond = 2.85e+13)
Warning: basis matrix is ill-conditioned (cond = 2.85e+13)
Warning: basis matrix is ill-conditioned (cond = 2.87e+13)
# 68000: obj = 3.587501423e+04 inf = 0.000e+00 (302287) 4
Warning: basis matrix is ill-conditioned (cond = 2.88e+13)
Warning: basis matrix is ill-conditioned (cond = 2.91e+13)
# 68500: obj = 3.587501469e+04 inf = 0.000e+00 (241339) 2
Warning: basis matrix is ill-conditioned (cond = 2.7e+13)
Warning: basis matrix is ill-conditioned (cond = 2.74e+13)
Warning: basis matrix is ill-conditioned (cond = 2.68e+13)
Warning: basis matrix is ill-conditioned (cond = 2.37e+13)
# 69000: obj = 3.587501525e+04 inf = 0.000e+00 (332832) 4
Warning: basis matrix is ill-conditioned (cond = 2.64e+13)
Warning: basis matrix is ill-conditioned (cond = 2.81e+13)
# 69500: obj = 3.587501860e+04 inf = 0.000e+00 (323672) 2
Warning: basis matrix is ill-conditioned (cond = 2.36e+13)
Warning: basis matrix is ill-conditioned (cond = 2.52e+13)
# 70000: obj = 3.587501898e+04 inf = 0.000e+00 (316434) 2
Warning: basis matrix is ill-conditioned (cond = 2.52e+13)
# 70500: obj = 3.587501922e+04 inf = 0.000e+00 (316281) 1
Warning: basis matrix is ill-conditioned (cond = 2.63e+13)
Warning: basis matrix is ill-conditioned (cond = 4.82e+13)
Warning: basis matrix is ill-conditioned (cond = 2.58e+13)
# 71000: obj = 3.587502378e+04 inf = 0.000e+00 (332011) 3
Warning: basis matrix is ill-conditioned (cond = 2.92e+13)
Warning: basis matrix is ill-conditioned (cond = 2.94e+13)
# 71500: obj = 3.587503441e+04 inf = 0.000e+00 (394336) 2
Warning: basis matrix is ill-conditioned (cond = 3.27e+13)
Warning: basis matrix is ill-conditioned (cond = 3.22e+13)
Warning: basis matrix is ill-conditioned (cond = 3.05e+13)
Warning: basis matrix is ill-conditioned (cond = 3.59e+13)
# 72000: obj = 3.587503733e+04 inf = 0.000e+00 (394763) 4
Warning: basis matrix is ill-conditioned (cond = 3.22e+13)
Warning: basis matrix is ill-conditioned (cond = 3.81e+13)
Warning: basis matrix is ill-conditioned (cond = 3.52e+13)
# 72500: obj = 3.587503963e+04 inf = 0.000e+00 (395002) 3
Warning: basis matrix is ill-conditioned (cond = 6.65e+13)
# 73000: obj = 3.587504090e+04 inf = 0.000e+00 (397774) 1
Warning: basis matrix is ill-conditioned (cond = 4.04e+13)
# 73500: obj = 3.587504342e+04 inf = 0.000e+00 (396217) 1