Infinite loop in DIP

[svigerske]

Issue created by migration from Trac.

Original creator: @mosu001

Original creation time: 2011-08-15 21:36:36

When I submit a problem to DIP using Dippy (see Python script at end), it enters into an infinite loop after 20 nodes have been processed. I looked into it and as far as I can tell the problem is in OsiClpSolverInterface.cpp lines 994-997

ClpSimplex * model2 = pinfo.presolvedModel(*modelPtr_,1.0e-8);
if (!model2) {
  // problem found to be infeasible - whats best?
  model2 = modelPtr_;

modelPtr gives an infeasible problem (I wrote it to an MPS file and checked it in Gurobi), but the presolver returns a feasible problem...! Thus, this node is flagged incorrectly as feasible and the loop begins. If I don't create subproblems this model solves OK and using doPriceCut it solves OK too. Without the advanced branching it solves OK. Only when the subproblems are present and we are not using doPriceCut and advanced branching is being used does the loop happen.

I'm not allowed to attach files so here is the Python script:

import math

import coinor.pulp as pulp
from pulp import *
from sp import shortestPath
import coinor.dippy as dippy

TOL = 1e-10
NODES = ['S', 1, 2, 3, 4, 'D']
coords = {
'S': (0, 0.5),
1: (1, 1),
2: (1, 0),
3: (2, 1),
4: (2, 0),
'D': (3, 0.5)
}

DIR_ARCS = [('S', 1), ('S', 2), (2, 1),
(1, 3), (2, 4), (4, 3), (3, 'D'), (4, 'D')]
UNDIR_ARCS = [(1, 4)]
ARCS = DIR_ARCS + UNDIR_ARCS + [(n, m) for (m, n) in UNDIR_ARCS]

cost = {
('S', 1): 1,
('S', 2): 2,
(2, 1): 1,
(1, 4): 3,
(1, 3): 3,
(2, 4): 4,
(4, 3): 1,
(3, 'D'): 1,
(4, 'D'): 3,
}

capacity = {
('S', 1): 7,
('S', 2): 12,
(2, 1): 12,
(1, 4): 12,
(1, 3): 7,
(2, 4): 6,
(4, 3): 7,
(3, 'D'): 9,
(4, 'D'): 12,
}

COMMODITIES = ['A', 'B', 'C']

flow = {
'A': 6,
'B': 5,
'C': 3,
}

prob = dippy.DipProblem("Multi-Commodity Flow")

flow_vars = LpVariable.dicts("Flows", [(a, c) for a in ARCS for c in COMMODITIES],
cat=LpBinary)
##Objective function
prob += sum(cost[a]*flow_vars[(a,c)]*flow[c] for a in DIR_ARCS for c in COMMODITIES)
+ sum(cost[m,n]flow[c](flow_vars[((n,m),c)]+flow_vars[((m,n),c)]) for a in UNDIR_ARCS for c in COMMODITIES)

##Constraints

##Source and sink
for c in COMMODITIES:
prob.relaxation[c] += sum(flow_vars[((m,n),c)] for (m,n) in ARCS if m == 'S') == 1
prob.relaxation[c] += sum(flow_vars[((m,n),c)] for (m,n) in ARCS if n == 'D') == 1

##Flow conservation
for i in NODES:
if (i != 'S') and (i != 'D'):
for c in COMMODITIES:
prob.relaxation[c] += sum(flow_vars[((m,n),c)] for (m,n) in ARCS if n == i) == sum(flow_vars[((m,n),c)] for (m,n) in ARCS if m == i)

##Arc capacity constraints
for (m,n) in DIR_ARCS:
prob += sum(flow[c]flow_vars[((m,n),c)] for c in COMMODITIES) <= capacity[(m,n)]
for (m,n) in UNDIR_ARCS:
prob += sum(flow[c](flow_vars[((m,n),c)]+flow_vars[((n,m),c)]) for c in COMMODITIES) <= capacity[(m,n)]

#####################BRANCH#########################################

def adv_branch(prob, sol):
#Nodes are listed in order of nearest to S
for p in NODES:
#Find all arcs from this node
for a in [a for a in ARCS if a[0] == p]:
#Check for fractionality of commodity flow
for c in COMMODITIES:
frac = sol[flow_vars[(a,c)]]
if (frac > TOL) and (frac < 1 - TOL):
#If fractionality is found branch!
down = math.floor(frac)
up = math.ceil(frac)

                down_branch_ub  = [(flow_vars[(a,c)],down)]
                up_branch_lb  = [(flow_vars[(a,c)],up)]

                print "Returning..."
                print down_branch_ub
                print up_branch_lb
                return ([], down_branch_ub, up_branch_lb, [])

prob.branch_method = adv_branch

#####################SOLVE#################################
prob.writeLP('mc_scott.lp')
dippy.Solve(prob,{
'TolZero': '%s' % TOL,

'doPriceCut': 1,

'LogDebugLevel': 5,
'LogDumpLevel': 5,

})

for c in COMMODITIES:
for (m, n) in ARCS:
if flow_vars[((m, n), c)].varValue > 0:
print "Commodity", c, "flows across", (m, n), "=", flow_vars[((m, n), c)].varValue

[svigerske]

Comment by @mosu001 created at 2011-08-16 01:46:20

Here is another file that has a similar error, but without the .relaxation constraints. This hangs in Dippy/DIP, but solves in Gurobi:

import math

import coinor.pulp as pulp
from pulp import *
import coinor.dippy as dippy

NODES = ['O', 'A', 'B', 'C', 'D', 'E', 'T']
coords = {
'O': (0, 1),
'A': (1, 2),
'B': (2, 1),
'C': (1.75, 0),
'D': (4, 1),
'E': (3.75, 0),
'T': (5, 1.5),
}

DIR_ARCS = [
('O', 'A'),
('O', 'B'),
('O', 'C'),
('A', 'B'),
('A', 'D'),
('B', 'C'),
('B', 'D'),
('B', 'E'),
('C', 'E'),
('D', 'T'),
('E', 'D'),
('E', 'T'),
]
UNDIR_ARCS = []
ARCS = DIR_ARCS + UNDIR_ARCS + [(n, m) for (m, n) in UNDIR_ARCS]

cost = {
('O', 'A'):2,
('O', 'B'):5,
('O', 'C'):4,
('A', 'B'):2,
('A', 'D'):7,
('B', 'C'):1,
('B', 'D'):4,
('B', 'E'):3,
('C', 'E'):4,
('D', 'T'):5,
('E', 'D'):1,
('E', 'T'):7,
}

capacity = {
('O', 'A'):5,
('O', 'B'):7,
('O', 'C'):4,
('A', 'B'):1,
('A', 'D'):3,
('B', 'C'):2,
('B', 'D'):5,
('B', 'E'):5,
('C', 'E'):4,
('D', 'T'):9,
('E', 'D'):1,
('E', 'T'):6,
}

COMMODITIES = ['F1', 'F2', 'F3', 'F4', 'F5']

flow = {
'F1': 3,
'F2': 2,
'F3': 2,
'F4': 2,
'F5': 3,
'F6': 2,
}

TOL = 1e-6

prob = dippy.DipProblem("Multi-Commodity Flow")

flow_vars = LpVariable.dicts("Flows", [(a, c) for a in ARCS for c in COMMODITIES],
cat=LpBinary)

prob += lpSum(cost[a] * flow[c] * flow_vars[(a, c)] for a in DIR_ARCS for c in COMMODITIES)
+ lpSum(cost[(m, n)] * flow[c] * (flow_vars[((m, n), c)] + flow_vars[((n, m), c)]) for (m, n) in UNDIR_ARCS for c in COMMODITIES)

for c in COMMODITIES:
prob += lpSum(flow_vars[((m, n), c)] for (m, n) in ARCS if m == 'O') == 1

for c in COMMODITIES:
prob += lpSum(flow_vars[((m, n), c)] for (m, n) in ARCS if n == 'T') == 1

for c in COMMODITIES:
for p in NODES:
if (p != 'O') and (p != 'T'):
prob += lpSum(flow_vars[((m, n), c)] for (m, n) in ARCS if n == p) ==
lpSum(flow_vars[((m, n), c)] for (m, n) in ARCS if m == p)

for a in DIR_ARCS:
prob += lpSum(flow[c] * flow_vars[(a, c)] for c in COMMODITIES) <= capacity[a]

for (m, n) in UNDIR_ARCS:
prob += lpSum(flow[c] * (flow_vars[((m, n), c)] + flow_vars[((n, m), c)]) for c in COMMODITIES) <= capacity[(m, n)]

prob.writeLP('mc4.lp')
dippy.Solve(prob, {
'TolZero': '%s' % TOL,
})

[svigerske]

Comment by @tkralphs created at 2011-08-27 22:15:12

I couldn't replicate this. Could you give more details, such as OS, compiler, etc? Are you using trunk? If so, what revision? You might want to make sure you have updated to the latest revision. If not, then let me know what version of DIP you are using. Thanks.