bug-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Non-optimal MIP solution?


From: Julien
Subject: Non-optimal MIP solution?
Date: Mon, 16 Nov 2020 14:42:42 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0

Hi

I'm experiencing puzzling results when solving a MIP using GLPK v4.65 under Ubuntu. I'm using the bindings from C++ but for the sake of simplicity, I'll share a minimal example generated using `glp_write_lp`.

------------ MIP 1 -------------
Minimize
 obj: - 2578 t0 + t1 + 2578 t2 + 6646084 Y0 + 6646084 Y1 + 6646084 Y2

Subject To
 P0: - delta0 + t1 - t0 >= 0
 P1: - delta1 + t2 - t1 >= 0
 L0: + Y0 + t0 >= 30000
 L1: - 35008 X1_1 - 25200 X1_0 + Y1 + t1 >= 0
 D1: - 37800 X1_1 - 29000 X1_0 - Y1 + t1 <= 0
 D2: - Y2 + t2 <= 34000
 S1: + X1_1 + X1_0 = 1
 Delta0: + delta0 = 1293
 Delta1: + delta1 = 1285

Bounds
 t0 >= 30000
 0 <= X1_0 <= 1
 0 <= X1_1 <= 1

Generals
 X1_0
 X1_1

End
-----------------------------

Running `glpsol --lp` on this one result in an "INTEGER OPTIMAL SOLUTION FOUND" with objective value 1.524614941e+10.

Now when pinning the value of t0 to its lower bound in this problem (using t0 = 30000 in the "Bounds" section), I get a report of an "INTEGER OPTIMAL SOLUTION" with objective value 1.524614799e+10. This does look inconsistent with the supposedly optimal first result, because the objective value is lower while the new solution is also feasible for the first problem.

Is there something I'm missing here in the way I'm using GLPK?

Additional side note: while trying to trim my program to a MWE, I tried the equivalent formulation below (it only rules out the definition of constant variables delta*). In that case I get the expected second solution.

------------ MIP 1 variant -------------
Minimize
 obj: - 2578 t0 + t1 + 2578 t2 + 6646084 Y0 + 6646084 Y1 + 6646084 Y2

Subject To
 P0: + t1 - t0 >= 1293
 P1: + t2 - t1 >= 1285
 L0: + Y0 + t0 >= 30000
 L1: - 35008 X1_1 - 25200 X1_0 + Y1 + t1 >= 0
 D1: - 37800 X1_1 - 29000 X1_0 - Y1 + t1 <= 0
 D2: - Y2 + t2 <= 34000
 S1: + X1_1 + X1_0 = 1

Bounds
 t0 >= 30000
 0 <= X1_0 <= 1
 0 <= X1_1 <= 1

Generals
 X1_0
 X1_1

End
-----------------------------

Thanks for any pointers!

Regards
--
Julien



reply via email to

[Prev in Thread] Current Thread [Next in Thread]