RE: [Fwd: Potential Bug Inquiry of GLPK]

[Meketon, Marc]

I have an old CBC version (build date of 2015).  The output below is confusing – it first says it finds an integer optimal solution with objective 4450.0109 (GLPK has it as 4450.011), and then it says the problem is infeasible.

 

My guess:  The problem is on the borderline between integer feasibility and infeasibility, and different solvers struggle differently.

 

-Marc

---------------------

 

C:\TEMP>\solvers\cbc.exe seed.mps

Welcome to the CBC MILP Solver

Version: 2.9.0

Build Date: Jun  4 2015

 

command line - \solvers\cbc.exe seed.mps (default strategy 1)

At line 2 NAME          seed

At line 3 ROWS

At line 710 COLUMNS

At line 7786 RHS

At line 8492 BOUNDS

At line 8513 ENDATA

Problem seed has 705 rows, 10 columns and 7049 elements

Coin0008I seed read with 0 errors

Continuous objective value is 3897.23 - 0.00 seconds

Cgl0004I processed model has 705 rows, 10 columns (8 integer (0 of which binary)) and 7049 elements

Cbc0031I 6 added rows had average density of 10

Cbc0013I At root node, 6 cuts changed objective from 3897.2348 to 3979.8165 in 8 passes

Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100

Cbc0014I Cut generator 1 (Gomory) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.029 seconds - new frequency is -100

Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100

Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100

Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100

Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100

Cbc0014I Cut generator 6 (TwoMirCuts) - 41 row cuts average 9.4 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1

Cbc0010I After 0 nodes, 1 on tree, 1e+050 best solution, best possible 4059.3344 (0.06 seconds)

Cbc0012I Integer solution of 4450.0109 found by rounding after 368 iterations and 21 nodes (0.22 seconds)

Cbc0001I Search completed - best objective 4450.010890676244, took 505 iterations and 36 nodes (0.28 seconds)

Cbc0032I Strong branching done 210 times (790 iterations), fathomed 16 nodes and fixed 30 variables

Cbc0035I Maximum depth 8, 4 variables fixed on reduced cost

0  Obj 3897.2348 Primal inf 19.174013 (8) Dual inf 1.8334901e+011 (10)

12  Obj 4450.011 Primal inf 4.9303863e-006 (1)

12  Obj 4450.011 Primal inf 4.9303863e-006 (1)

Primal infeasible - objective value 4450.011

Cuts at root node changed objective from 3897.23 to 4059.33

Probing was tried 8 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Gomory was tried 8 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.029 seconds)

Knapsack was tried 8 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Clique was tried 8 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

MixedIntegerRounding2 was tried 8 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

FlowCover was tried 8 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

TwoMirCuts was tried 43 times and created 116 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

 

Result - Problem proven infeasible

 

Objective value:                100000000000000010000000000000000000000000000000000.00000000

Enumerated nodes:               36

Total iterations:               505

Time (CPU seconds):             0.30

Time (Wallclock seconds):       0.30

 

Total time (CPU seconds):       0.30   (Wallclock seconds):       0.30

 

From: bug-glpk-bounces+marc.meketon=oliverwyman.com@gnu.org <bug-glpk-bounces+marc.meketon=oliverwyman.com@gnu.org> On Behalf Of Andrew Makhorin
Sent: Sunday, February 2, 2025 9:13 PM
To: bug-glpk@gnu.org
Subject: [Fwd: Potential Bug Inquiry of GLPK]

 

 

CAUTION: This email originated outside the company. Do not click links or open attachments unless you are expecting them from the sender.

 

-------- Forwarded Message --------

 

Date: Thu, 30 Jan 2025 02:04:36 +0000

Subject: Potential Bug Inquiry of GLPK

To: bug-glpk@gnu.org <bug-glpk@gnu.org>

From: Xintong Zhou <xintong.zhou1@uwaterloo.ca>

Hi,

 

I am using the latest version of GLPK to solve the attached MIP problem (seed.mps), and I am getting the following result:

 

Solver: GLPK_CMD

Status: Optimal

Objective: 4450.011933000001

x0 = 18, x1 = -24, x2 = -37, x3 = 9, x4 = -3, x5 = -48, x6 = 16, x7 = 9, x8 = -13.3293, x9 = 23.8585

 

While all the other solvers I have tried (including CBC, SCIP, HiGHS and Gurobi) return the same result as following:

 

Solver: CBC, SCIP, HiGHS, Gurobi

Status: Optimal

Objective: 4485.181539630002

x0 = 18, x1 = -24, x2 = -37, x3 = 9, x4 = -4, x5 = -48, x6 = 16, x7 = 9, x8 = -13.575019, x9 = 23.694121

 

Is this result expected for GLPK? I'm not sure if this difference of the answer is due to a different algorithm used by GLPK or it’s an implementation issue. Any response or suggestions are appreciated!

 

Thanks for your time!

 

Best wishes,

Xintong Zhou

Cheriton School of Computer Science

University of Waterloo

 

 

---

This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation. For more information on how we use your personal data please see our Privacy Notice.