search

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
17 stars 7 forks source link

Compress columns appears to cause infeasibility #84

Open svigerske opened 5 years ago

svigerske commented 5 years ago

Issue created by migration from Trac.

Original creator: @tkralphs

Original creation time: 2011-09-11 23:32:52

Assignee: @mgalati13

Revision 479, Linux with gcc 4.4, CPLEX as LP/IP solver. Solving att48 with the TSP app with these settings

doPriceCut    = 1
LimitRoundCutIters = 0
TailoffPercent = -1
ModelNameCore  = 2MATCH
ModelNameRelax = SUBTOUR

The master LP becomes infeasible after column compression, even though no cuts are being generated. Note the switch from PHASE_PRICE2 back to PHASE_PRICE1 below.

Processing Node   0 algo= PRICE_AND_CUT phase= PHASE_PRICE2 c=    0 p= 2008 LB=   6890.177 UB=  10752.290 nodeLB=  10489.780 gLB=  10489.780 gUB=        INF lpGap=      0.025 ipGap=        INF time=      30.46
Processing Node   0 algo= PRICE_AND_CUT phase= PHASE_PRICE2 c=    0 p= 2009 LB=   9780.191 UB=  10752.179 nodeLB=  10489.780 gLB=  10489.780 gUB=        INF lpGap=      0.025 ipGap=        INF time=      30.47
Processing Node   0 algo= PRICE_AND_CUT phase= PHASE_PRICE1 c=    0 p= 2010 LB=    -30.115 UB=      0.000 nodeLB=    -30.115 gLB=    -30.115 gUB=        INF lpGap=      1.000 ipGap=        INF time=      30.49
Processing Node   0 algo= PRICE_AND_CUT phase= PHASE_PRICE2 c=    0 p= 2011 LB=  -2106.519 UB=  10752.182 nodeLB=  -2106.519 gLB=  -2106.519 gUB=        INF lpGap=      6.104 ipGap=        INF time=      30.51
Processing Node   0 algo= PRICE_AND_CUT phase= PHASE_PRICE2 c=    0 p= 2012 LB=   7390.329 UB=  10752.173 nodeLB=   7390.329 gLB=   7390.329 gUB=        INF lpGap=      0.455 ipGap=        INF time=      30.52