On Fri, 2018-02-02 at 13:30 +0100, Balázs Sziklai wrote: > Dear GLPK Team, > > > I have an mip problem (see attachment) that can be solved in under a > second with glpk 4.58 but loops with glpk 4.64. That is, the gap does > not go below 0.3% no matter how much time I keep running the solver. > Gurobi also finds the solution (the same one that glpk 4.58 obtains). > I would be very grateful for any feedback! > Sincerely, > Balázs Sziklai
Thank you for your report. On solving your instance I found nothing unusual except maybe the solution time; see glpsol output below and solution file attached. Usually the maximal independent set problem (which your instance is, I guess) takes relatively lesser time for small graphs, because clique cuts are very efficient for this problem class (see for example glpk/examples/misp.mod). Probably glpsol takes relatively much time due to a pathological combination of the objective coefficients--if I perturb the coeffs in your instance by .0001 (e.g. 1234 is replaced with 1234.0001), the instance is solved immediately on the root level. As to glpk 4.58, it was just a lucky chance. Andrew Makhorin GLPSOL: GLPK LP/MIP Solver, v4.64 Parameter(s) specified in the command line: --cuts --pcost --lp tsst2.lp --log log -o sol Reading problem data from 'tsst2.lp'... tsst2.lp:1102: warning: missing final end of line 32 rows, 448 columns, 896 non-zeros 448 integer variables, all of which are binary 1102 lines were read GLPK Integer Optimizer, v4.64 32 rows, 448 columns, 896 non-zeros 448 integer variables, all of which are binary Preprocessing... 32 rows, 448 columns, 896 non-zeros 448 integer variables, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part is 32 Solving LP relaxation... GLPK Simplex Optimizer, v4.64 32 rows, 448 columns, 896 non-zeros * 0: obj = 0.000000000e+00 inf = 0.000e+00 (448) * 58: obj = 1.581500000e+03 inf = 0.000e+00 (0) OPTIMAL LP SOLUTION FOUND Integer optimization begins... Long-step dual simplex will be used Gomory's cuts enabled MIR cuts enabled Cover cuts enabled Clique cuts enabled Constructing conflict graph... Conflict graph has 448 + 0 = 448 vertices + 58: mip = not found yet <= +inf (1; 0) Solution found by heuristic: 1544 Cuts on level 0: gmi = 4; clq = 3; Cuts on level 8: gmi = 4; clq = 3; + 113: >>>>> 1.548000000e+03 <= 1.552000000e+03 0.3% (9; 0) + 4142: mip = 1.548000000e+03 <= 1.552000000e+03 0.3% (164; 636) + 8210: mip = 1.548000000e+03 <= 1.552000000e+03 0.3% (249; 1317) [...] +133578: mip = 1.548000000e+03 <= 1.552000000e+03 0.3% (744; 25212) Time used: 180.0 secs. Memory used: 3.6 Mb. +137367: mip = 1.548000000e+03 <= 1.552000000e+03 0.3% (763; 25945) +140782: mip = 1.548000000e+03 <= 1.550000000e+03 0.1% (578; 27355) +144122: mip = 1.548000000e+03 <= 1.549000000e+03 < 0.1% (92; 30724) +144646: mip = 1.548000000e+03 <= tree is empty 0.0% (0; 31937) INTEGER OPTIMAL SOLUTION FOUND Time used: 191.5 secs Memory used: 3.7 Mb (3912501 bytes) Writing MIP solution to 'sol'...
Problem:
Rows: 32
Columns: 448 (448 integer, 448 binary)
Non-zeros: 896
Status: INTEGER OPTIMAL
Objective: obj = 1548 (MAXimum)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 r_1 1 1
2 r_2 1 1
3 r_3 1 1
4 r_4 1 1
5 r_5 1 1
6 r_6 1 1
7 r_7 1 1
8 r_8 1 1
9 r_9 1 1
10 r_10 1 1
11 r_11 1 1
12 r_12 1 1
13 r_13 1 1
14 r_14 1 1
15 r_15 1 1
16 r_16 1 1
17 r_17 1 1
18 r_18 1 1
19 r_19 1 1
20 r_20 1 1
21 r_21 1 1
22 r_22 1 1
23 r_23 1 1
24 r_24 1 1
25 r_25 1 1
26 r_26 1 1
27 r_27 1 1
28 r_28 1 1
29 r_29 1 1
30 r_30 1 1
31 r_31 1 1
32 r_32 1 1
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 x_1 * 0 0 1
2 x_2 * 0 0 1
3 x_3 * 0 0 1
4 x_4 * 0 0 1
5 x_5 * 0 0 1
6 x_6 * 0 0 1
7 x_7 * 0 0 1
8 x_8 * 0 0 1
9 x_9 * 1 0 1
10 x_10 * 0 0 1
11 x_11 * 0 0 1
12 x_12 * 0 0 1
13 x_13 * 0 0 1
14 x_14 * 0 0 1
15 x_15 * 0 0 1
16 x_16 * 0 0 1
17 x_17 * 0 0 1
18 x_18 * 0 0 1
19 x_19 * 0 0 1
20 x_20 * 0 0 1
21 x_21 * 0 0 1
22 x_22 * 0 0 1
23 x_23 * 0 0 1
24 x_24 * 0 0 1
25 x_25 * 0 0 1
26 x_26 * 0 0 1
27 x_27 * 0 0 1
28 x_28 * 0 0 1
29 x_29 * 0 0 1
30 x_30 * 0 0 1
31 x_31 * 0 0 1
32 x_32 * 0 0 1
33 x_33 * 0 0 1
34 x_34 * 0 0 1
35 x_35 * 0 0 1
36 x_36 * 1 0 1
37 x_37 * 0 0 1
38 x_38 * 0 0 1
39 x_39 * 0 0 1
40 x_40 * 0 0 1
41 x_41 * 0 0 1
42 x_42 * 0 0 1
43 x_43 * 0 0 1
44 x_44 * 0 0 1
45 x_45 * 0 0 1
46 x_46 * 0 0 1
47 x_47 * 0 0 1
48 x_48 * 0 0 1
49 x_49 * 0 0 1
50 x_50 * 0 0 1
51 x_51 * 0 0 1
52 x_52 * 0 0 1
53 x_53 * 0 0 1
54 x_54 * 0 0 1
55 x_55 * 0 0 1
56 x_56 * 0 0 1
57 x_57 * 0 0 1
58 x_58 * 0 0 1
59 x_59 * 0 0 1
60 x_60 * 0 0 1
61 x_61 * 0 0 1
62 x_62 * 0 0 1
63 x_63 * 1 0 1
64 x_64 * 0 0 1
65 x_65 * 0 0 1
66 x_66 * 0 0 1
67 x_67 * 0 0 1
68 x_68 * 0 0 1
69 x_69 * 0 0 1
70 x_70 * 0 0 1
71 x_71 * 0 0 1
72 x_72 * 0 0 1
73 x_73 * 0 0 1
74 x_74 * 0 0 1
75 x_75 * 0 0 1
76 x_76 * 0 0 1
77 x_77 * 0 0 1
78 x_78 * 0 0 1
79 x_79 * 0 0 1
80 x_80 * 0 0 1
81 x_81 * 0 0 1
82 x_82 * 0 0 1
83 x_83 * 0 0 1
84 x_84 * 0 0 1
85 x_85 * 0 0 1
86 x_86 * 0 0 1
87 x_87 * 0 0 1
88 x_88 * 0 0 1
89 x_89 * 0 0 1
90 x_90 * 0 0 1
91 x_91 * 0 0 1
92 x_92 * 0 0 1
93 x_93 * 0 0 1
94 x_94 * 0 0 1
95 x_95 * 0 0 1
96 x_96 * 0 0 1
97 x_97 * 0 0 1
98 x_98 * 0 0 1
99 x_99 * 0 0 1
100 x_100 * 0 0 1
101 x_101 * 1 0 1
102 x_102 * 0 0 1
103 x_103 * 0 0 1
104 x_104 * 0 0 1
105 x_105 * 0 0 1
106 x_106 * 0 0 1
107 x_107 * 0 0 1
108 x_108 * 0 0 1
109 x_109 * 0 0 1
110 x_110 * 0 0 1
111 x_111 * 0 0 1
112 x_112 * 1 0 1
113 x_113 * 0 0 1
114 x_114 * 0 0 1
115 x_115 * 0 0 1
116 x_116 * 0 0 1
117 x_117 * 0 0 1
118 x_118 * 0 0 1
119 x_119 * 0 0 1
120 x_120 * 0 0 1
121 x_121 * 0 0 1
122 x_122 * 0 0 1
123 x_123 * 0 0 1
124 x_124 * 0 0 1
125 x_125 * 0 0 1
126 x_126 * 0 0 1
127 x_127 * 0 0 1
128 x_128 * 0 0 1
129 x_129 * 0 0 1
130 x_130 * 0 0 1
131 x_131 * 0 0 1
132 x_132 * 0 0 1
133 x_133 * 0 0 1
134 x_134 * 0 0 1
135 x_135 * 0 0 1
136 x_136 * 0 0 1
137 x_137 * 0 0 1
138 x_138 * 0 0 1
139 x_139 * 0 0 1
140 x_140 * 0 0 1
141 x_141 * 0 0 1
142 x_142 * 0 0 1
143 x_143 * 0 0 1
144 x_144 * 0 0 1
145 x_145 * 0 0 1
146 x_146 * 0 0 1
147 x_147 * 0 0 1
148 x_148 * 0 0 1
149 x_149 * 0 0 1
150 x_150 * 0 0 1
151 x_151 * 0 0 1
152 x_152 * 0 0 1
153 x_153 * 0 0 1
154 x_154 * 0 0 1
155 x_155 * 0 0 1
156 x_156 * 0 0 1
157 x_157 * 0 0 1
158 x_158 * 1 0 1
159 x_159 * 0 0 1
160 x_160 * 0 0 1
161 x_161 * 0 0 1
162 x_162 * 0 0 1
163 x_163 * 0 0 1
164 x_164 * 0 0 1
165 x_165 * 0 0 1
166 x_166 * 0 0 1
167 x_167 * 0 0 1
168 x_168 * 0 0 1
169 x_169 * 0 0 1
170 x_170 * 0 0 1
171 x_171 * 0 0 1
172 x_172 * 0 0 1
173 x_173 * 0 0 1
174 x_174 * 0 0 1
175 x_175 * 0 0 1
176 x_176 * 0 0 1
177 x_177 * 0 0 1
178 x_178 * 0 0 1
179 x_179 * 0 0 1
180 x_180 * 0 0 1
181 x_181 * 0 0 1
182 x_182 * 0 0 1
183 x_183 * 0 0 1
184 x_184 * 0 0 1
185 x_185 * 0 0 1
186 x_186 * 0 0 1
187 x_187 * 0 0 1
188 x_188 * 0 0 1
189 x_189 * 0 0 1
190 x_190 * 1 0 1
191 x_191 * 0 0 1
192 x_192 * 0 0 1
193 x_193 * 0 0 1
194 x_194 * 0 0 1
195 x_195 * 0 0 1
196 x_196 * 0 0 1
197 x_197 * 0 0 1
198 x_198 * 0 0 1
199 x_199 * 0 0 1
200 x_200 * 0 0 1
201 x_201 * 0 0 1
202 x_202 * 0 0 1
203 x_203 * 0 0 1
204 x_204 * 0 0 1
205 x_205 * 0 0 1
206 x_206 * 0 0 1
207 x_207 * 0 0 1
208 x_208 * 1 0 1
209 x_209 * 0 0 1
210 x_210 * 0 0 1
211 x_211 * 0 0 1
212 x_212 * 0 0 1
213 x_213 * 0 0 1
214 x_214 * 0 0 1
215 x_215 * 0 0 1
216 x_216 * 0 0 1
217 x_217 * 0 0 1
218 x_218 * 0 0 1
219 x_219 * 0 0 1
220 x_220 * 0 0 1
221 x_221 * 0 0 1
222 x_222 * 0 0 1
223 x_223 * 0 0 1
224 x_224 * 0 0 1
225 x_225 * 0 0 1
226 x_226 * 0 0 1
227 x_227 * 0 0 1
228 x_228 * 0 0 1
229 x_229 * 0 0 1
230 x_230 * 0 0 1
231 x_231 * 0 0 1
232 x_232 * 1 0 1
233 x_233 * 0 0 1
234 x_234 * 0 0 1
235 x_235 * 0 0 1
236 x_236 * 0 0 1
237 x_237 * 0 0 1
238 x_238 * 0 0 1
239 x_239 * 0 0 1
240 x_240 * 0 0 1
241 x_241 * 0 0 1
242 x_242 * 0 0 1
243 x_243 * 0 0 1
244 x_244 * 0 0 1
245 x_245 * 0 0 1
246 x_246 * 0 0 1
247 x_247 * 0 0 1
248 x_248 * 0 0 1
249 x_249 * 0 0 1
250 x_250 * 0 0 1
251 x_251 * 0 0 1
252 x_252 * 0 0 1
253 x_253 * 0 0 1
254 x_254 * 0 0 1
255 x_255 * 0 0 1
256 x_256 * 0 0 1
257 x_257 * 0 0 1
258 x_258 * 0 0 1
259 x_259 * 0 0 1
260 x_260 * 0 0 1
261 x_261 * 0 0 1
262 x_262 * 0 0 1
263 x_263 * 0 0 1
264 x_264 * 0 0 1
265 x_265 * 0 0 1
266 x_266 * 0 0 1
267 x_267 * 0 0 1
268 x_268 * 0 0 1
269 x_269 * 0 0 1
270 x_270 * 0 0 1
271 x_271 * 0 0 1
272 x_272 * 0 0 1
273 x_273 * 0 0 1
274 x_274 * 0 0 1
275 x_275 * 0 0 1
276 x_276 * 0 0 1
277 x_277 * 0 0 1
278 x_278 * 0 0 1
279 x_279 * 0 0 1
280 x_280 * 0 0 1
281 x_281 * 0 0 1
282 x_282 * 0 0 1
283 x_283 * 0 0 1
284 x_284 * 0 0 1
285 x_285 * 0 0 1
286 x_286 * 0 0 1
287 x_287 * 0 0 1
288 x_288 * 0 0 1
289 x_289 * 0 0 1
290 x_290 * 0 0 1
291 x_291 * 0 0 1
292 x_292 * 0 0 1
293 x_293 * 0 0 1
294 x_294 * 0 0 1
295 x_295 * 0 0 1
296 x_296 * 0 0 1
297 x_297 * 0 0 1
298 x_298 * 0 0 1
299 x_299 * 0 0 1
300 x_300 * 0 0 1
301 x_301 * 0 0 1
302 x_302 * 0 0 1
303 x_303 * 0 0 1
304 x_304 * 0 0 1
305 x_305 * 0 0 1
306 x_306 * 0 0 1
307 x_307 * 0 0 1
308 x_308 * 0 0 1
309 x_309 * 0 0 1
310 x_310 * 0 0 1
311 x_311 * 0 0 1
312 x_312 * 0 0 1
313 x_313 * 0 0 1
314 x_314 * 0 0 1
315 x_315 * 0 0 1
316 x_316 * 0 0 1
317 x_317 * 0 0 1
318 x_318 * 0 0 1
319 x_319 * 0 0 1
320 x_320 * 0 0 1
321 x_321 * 0 0 1
322 x_322 * 0 0 1
323 x_323 * 0 0 1
324 x_324 * 0 0 1
325 x_325 * 0 0 1
326 x_326 * 0 0 1
327 x_327 * 0 0 1
328 x_328 * 0 0 1
329 x_329 * 0 0 1
330 x_330 * 0 0 1
331 x_331 * 0 0 1
332 x_332 * 0 0 1
333 x_333 * 0 0 1
334 x_334 * 0 0 1
335 x_335 * 0 0 1
336 x_336 * 0 0 1
337 x_337 * 0 0 1
338 x_338 * 1 0 1
339 x_339 * 0 0 1
340 x_340 * 0 0 1
341 x_341 * 0 0 1
342 x_342 * 0 0 1
343 x_343 * 0 0 1
344 x_344 * 0 0 1
345 x_345 * 0 0 1
346 x_346 * 0 0 1
347 x_347 * 0 0 1
348 x_348 * 0 0 1
349 x_349 * 0 0 1
350 x_350 * 0 0 1
351 x_351 * 0 0 1
352 x_352 * 0 0 1
353 x_353 * 0 0 1
354 x_354 * 0 0 1
355 x_355 * 0 0 1
356 x_356 * 0 0 1
357 x_357 * 0 0 1
358 x_358 * 0 0 1
359 x_359 * 0 0 1
360 x_360 * 0 0 1
361 x_361 * 0 0 1
362 x_362 * 0 0 1
363 x_363 * 0 0 1
364 x_364 * 0 0 1
365 x_365 * 0 0 1
366 x_366 * 1 0 1
367 x_367 * 0 0 1
368 x_368 * 0 0 1
369 x_369 * 0 0 1
370 x_370 * 0 0 1
371 x_371 * 0 0 1
372 x_372 * 0 0 1
373 x_373 * 0 0 1
374 x_374 * 0 0 1
375 x_375 * 0 0 1
376 x_376 * 0 0 1
377 x_377 * 0 0 1
378 x_378 * 0 0 1
379 x_379 * 0 0 1
380 x_380 * 0 0 1
381 x_381 * 0 0 1
382 x_382 * 0 0 1
383 x_383 * 0 0 1
384 x_384 * 0 0 1
385 x_385 * 1 0 1
386 x_386 * 0 0 1
387 x_387 * 0 0 1
388 x_388 * 0 0 1
389 x_389 * 0 0 1
390 x_390 * 0 0 1
391 x_391 * 0 0 1
392 x_392 * 0 0 1
393 x_393 * 0 0 1
394 x_394 * 0 0 1
395 x_395 * 0 0 1
396 x_396 * 0 0 1
397 x_397 * 0 0 1
398 x_398 * 0 0 1
399 x_399 * 0 0 1
400 x_400 * 0 0 1
401 x_401 * 1 0 1
402 x_402 * 0 0 1
403 x_403 * 0 0 1
404 x_404 * 0 0 1
405 x_405 * 0 0 1
406 x_406 * 0 0 1
407 x_407 * 0 0 1
408 x_408 * 0 0 1
409 x_409 * 0 0 1
410 x_410 * 0 0 1
411 x_411 * 0 0 1
412 x_412 * 0 0 1
413 x_413 * 0 0 1
414 x_414 * 0 0 1
415 x_415 * 0 0 1
416 x_416 * 0 0 1
417 x_417 * 0 0 1
418 x_418 * 0 0 1
419 x_419 * 0 0 1
420 x_420 * 0 0 1
421 x_421 * 0 0 1
422 x_422 * 0 0 1
423 x_423 * 0 0 1
424 x_424 * 0 0 1
425 x_425 * 0 0 1
426 x_426 * 0 0 1
427 x_427 * 1 0 1
428 x_428 * 0 0 1
429 x_429 * 0 0 1
430 x_430 * 0 0 1
431 x_431 * 1 0 1
432 x_432 * 0 0 1
433 x_433 * 0 0 1
434 x_434 * 0 0 1
435 x_435 * 0 0 1
436 x_436 * 0 0 1
437 x_437 * 0 0 1
438 x_438 * 0 0 1
439 x_439 * 0 0 1
440 x_440 * 0 0 1
441 x_441 * 0 0 1
442 x_442 * 0 0 1
443 x_443 * 1 0 1
444 x_444 * 0 0 1
445 x_445 * 0 0 1
446 x_446 * 0 0 1
447 x_447 * 0 0 1
448 x_448 * 0 0 1
Integer feasibility conditions:
KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.PB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
End of output
_______________________________________________ Bug-glpk mailing list Bug-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/bug-glpk
