Re: Non-optimal MIP solution?

[Julien]

Hi

Small update to my previous message: while trying to tweek solving 
options, I came across the fact that only the default branching 
heuristic (--drtom) provides the "wrong" solution here. Solving with any 
other branching heuristic (using --first, --last, --mostf or --pcost) 
does provide the expected solution.

I've also read about scaling, but from what I can tell based on the 
`glpsol` output and the definition of a "well scaled" problem[1], it 
does not seem like scaling is at stake here.

Regards

[1] https://en.wikibooks.org/wiki/GLPK/Scaling
--
Julien

On 16/11/2020 14:42, Julien wrote:
> 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