False "Problem infeasible"

coin-or / Dip

DIP is a decomposition-based solver framework for mixed integer linear programs.

https://github.com/coin-or/Dip/wiki

Eclipse Public License 1.0

19 stars 7 forks source link

False "Problem infeasible" #63

Open svigerske opened 5 years ago

svigerske commented 5 years ago

Issue created by migration from Trac.

Original creator: vejlin

Original creation time: 2011-01-13 15:17:55

DIP sometimes falsely concludes a problem is infeasible.

This can be reproduced using the MILPBlock example:

run with atm_5_10_1 instance
use the attached block file (pair notation)

svigerske commented 5 years ago

Attachment atm_5_10_1_KP.block by vejlin created at 2011-01-13 15:18:47

Knapsack reformulation

svigerske commented 5 years ago

Comment by vejlin created at 2011-01-13 15:21:27

The block file puts the 10 embedded disjoint knapsack problems in separate blocks.

The error can be circumvented by artificially bounding all columns in the parameter file: ColumnLB = -1.0e4 ColumnUB = 1.0e4

This is not related to the issue with artificial bounds being needed for unbounded pricing problems, since these knapsack problems are all bounded.

svigerske commented 5 years ago

Comment by vejlin created at 2011-01-13 15:36:48

adding artificial bounds yields the error in ticket #64

svigerske commented 5 years ago

Comment by @mgalati13 created at 2011-01-16 03:05:20

This issue is due to unbounded master-only columns. Given the current design, this can lead to large (infinity) coefficients in the reformulated constraint matrix - which leads to numerical issues.

This can be avoided with ColumnLB/UB option - but as seen in other tickets - this can lead to numerical issues later.

A better treatment of master-only columns is needed. I am working on a redesign which will take care of this. I will let you know when it is complete.