[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Re: finding multiple integer solutions
|
From: |
Andrew Makhorin |
|
Subject: |
[Help-glpk] Re: finding multiple integer solutions |
|
Date: |
Thu, 20 Nov 2003 09:28:23 +0300 |
>Is it possible to implement the two-phase procedure as follows?
I could suggest you some hacking that requires minimal changes in the
code. I hope you are able to discover all necessary details, so below
here is just an idea.
I took the problem p0033 from miplib whose integer optimum is 3089 (we
may think that it has been obtained on the first phase). Then I replaced
the line 720, file glpmip1.c (routine record_solution):
tree->best = tree->curr->lp_obj;
by the following ones:
tree->best = 3200.0;
print("Z = %g", tree->curr->lp_obj);
where tree->best is the global upper bound (i.e. the incumbent
objective value) used by the solver to prune hopeless branches. Due to
this hacking, if optimal solution of LP relaxation of some subproblem
is better (i.e. less) than 3200, the corresponding branch is not pruned
until it has been solved to the end. The routine record_solution is
called whenever an integer feasible solution, whose objective value
tree->curr->lp_obj is better than tree->best, has been found. Thus, this
allowed me obtaining *all* *distinct* integer feasible solutions with
the objective value in the range [3089, 3200).
Below here is the output from glpsol (note that each line "Z = ..."
corresponds to a distinct integer feasible solution):
------------------------------------------------------------------------
load_mps: reading LP data from `p0033.mps'...
load_mps: name `P0033'
load_mps: 17 rows
load_mps: 33 columns
load_mps: 131 non-zeros
load_mps: 1 right-hand side vector(s)
load_mps: 0 range vector(s)
load_mps: 1 bound vector(s)
load_mps: 152 cards were read
lpx_simplex: original LP has 17 rows, 33 columns, 131 non-zeros
lpx_simplex: presolved LP has 15 rows, 33 columns, 98 non-zeros
lpx_adv_basis: size of triangular part = 15
0: objval = 1.029100000e+03 infeas = 1.000000000e+00 (0)
18: objval = 3.056345789e+03 infeas = 0.000000000e+00 (0)
* 18: objval = 3.056345789e+03 infeas = 0.000000000e+00 (0)
* 29: objval = 2.520571739e+03 infeas = 1.131184267e-17 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
Objective function is integral
+ 29: mip = not found yet; lp = 2.520571739e+03 (1, 0)
Z = 3716
+ 137: mip = 3.200000000e+03; lp = 2.520571739e+03 (31, 56)
Z = 3089
+ 241: mip = 3.200000000e+03; lp = 2.520571739e+03 (30, 141)
Z = 3089
+ 248: mip = 3.200000000e+03; lp = 2.520571739e+03 (30, 145)
Z = 3089
+ 250: mip = 3.200000000e+03; lp = 2.520571739e+03 (27, 148)
Z = 3089
+ 262: mip = 3.200000000e+03; lp = 2.520571739e+03 (30, 159)
Z = 3089
+ 269: mip = 3.200000000e+03; lp = 2.520571739e+03 (30, 163)
Z = 3089
+ 271: mip = 3.200000000e+03; lp = 2.520571739e+03 (27, 166)
Z = 3089
+ 279: mip = 3.200000000e+03; lp = 2.520571739e+03 (29, 172)
Z = 3089
+ 286: mip = 3.200000000e+03; lp = 2.520571739e+03 (29, 176)
Z = 3089
+ 288: mip = 3.200000000e+03; lp = 2.520571739e+03 (26, 179)
Z = 3095
+ 420: mip = 3.200000000e+03; lp = 2.520571739e+03 (42, 255)
Z = 3095
+ 426: mip = 3.200000000e+03; lp = 2.520571739e+03 (42, 261)
Z = 3095
+ 434: mip = 3.200000000e+03; lp = 2.520571739e+03 (40, 269)
Z = 3188
+ 839: mip = 3.200000000e+03; lp = 2.520571739e+03 (89, 514)
Z = 3188
+ 845: mip = 3.200000000e+03; lp = 2.520571739e+03 (89, 518)
Z = 3188
+ 847: mip = 3.200000000e+03; lp = 2.520571739e+03 (85, 522)
Z = 3188
+ 881: mip = 3.200000000e+03; lp = 2.520571739e+03 (96, 549)
Z = 3188
+ 887: mip = 3.200000000e+03; lp = 2.520571739e+03 (96, 553)
Z = 3188
+ 889: mip = 3.200000000e+03; lp = 2.520571739e+03 (91, 558)
Z = 3188
+ 945: mip = 3.200000000e+03; lp = 2.520571739e+03 (96, 603)
Z = 3188
+ 952: mip = 3.200000000e+03; lp = 2.520571739e+03 (95, 608)
Z = 3188
+ 962: mip = 3.200000000e+03; lp = 2.520571739e+03 (99, 618)
Z = 3188
+ 968: mip = 3.200000000e+03; lp = 2.520571739e+03 (99, 622)
Z = 3164
+ 975: mip = 3.200000000e+03; lp = 2.520571739e+03 (99, 630)
Z = 3164
+ 981: mip = 3.200000000e+03; lp = 2.520571739e+03 (99, 634)
Z = 3164
+ 983: mip = 3.200000000e+03; lp = 2.520571739e+03 (96, 637)
Z = 3188
+ 985: mip = 3.200000000e+03; lp = 2.520571739e+03 (92, 641)
Z = 3188
+ 987: mip = 3.200000000e+03; lp = 2.520571739e+03 (90, 643)
Z = 3188
+ 998: mip = 3.200000000e+03; lp = 2.520571739e+03 (95, 654)
Z = 3188
+ 1004: mip = 3.200000000e+03; lp = 2.520571739e+03 (95, 658)
Z = 3164
+ 1012: mip = 3.200000000e+03; lp = 2.520571739e+03 (95, 666)
Z = 3164
+ 1018: mip = 3.200000000e+03; lp = 2.520571739e+03 (95, 670)
Z = 3164
+ 1020: mip = 3.200000000e+03; lp = 2.520571739e+03 (92, 673)
Z = 3188
+ 1022: mip = 3.200000000e+03; lp = 2.520571739e+03 (89, 676)
Z = 3164
+ 1030: mip = 3.200000000e+03; lp = 2.520571739e+03 (91, 682)
Z = 3164
+ 1036: mip = 3.200000000e+03; lp = 2.520571739e+03 (91, 686)
Z = 3164
+ 1038: mip = 3.200000000e+03; lp = 2.520571739e+03 (88, 689)
Z = 3188
+ 1102: mip = 3.200000000e+03; lp = 2.520571739e+03 (86, 749)
Z = 3188
+ 1108: mip = 3.200000000e+03; lp = 2.520571739e+03 (86, 753)
Z = 3188
+ 1110: mip = 3.200000000e+03; lp = 2.520571739e+03 (83, 756)
Z = 3188
+ 1122: mip = 3.200000000e+03; lp = 2.520571739e+03 (86, 767)
Z = 3188
+ 1128: mip = 3.200000000e+03; lp = 2.520571739e+03 (86, 771)
Z = 3188
+ 1130: mip = 3.200000000e+03; lp = 2.520571739e+03 (83, 774)
Z = 3188
+ 1138: mip = 3.200000000e+03; lp = 2.520571739e+03 (85, 780)
Z = 3188
+ 1144: mip = 3.200000000e+03; lp = 2.520571739e+03 (85, 784)
Z = 3188
+ 1146: mip = 3.200000000e+03; lp = 2.520571739e+03 (82, 787)
Z = 3188
+ 1168: mip = 3.200000000e+03; lp = 2.520571739e+03 (92, 807)
Z = 3188
+ 1174: mip = 3.200000000e+03; lp = 2.520571739e+03 (92, 811)
Z = 3188
+ 1177: mip = 3.200000000e+03; lp = 2.520571739e+03 (87, 816)
Z = 3188
+ 1225: mip = 3.200000000e+03; lp = 2.520571739e+03 (99, 862)
Z = 3188
+ 1231: mip = 3.200000000e+03; lp = 2.520571739e+03 (99, 866)
Z = 3188
+ 1233: mip = 3.200000000e+03; lp = 2.520571739e+03 (93, 872)
+ 2796: mip = 3.200000000e+03; lp = tree is empty (0, 2099)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.2 secs
Memory used: 0.2M (185352 bytes)
------------------------------------------------------------------------
Andrew Makhorin