bug-glpk
[Top][All Lists]
Advanced

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

Re: Non-optimal MIP solution?


From: Julien
Subject: Re: Non-optimal MIP solution?
Date: Tue, 17 Nov 2020 10:58:59 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0

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



reply via email to

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