[Dip-tickets] [Dip] #82: Infinite loop in DIP

[Dip]

#82: Infinite loop in DIP
----------------------+-----------------------------------------------------
  Reporter:  mosu001  |      Owner:       
      Type:  defect   |     Status:  new  
  Priority:  major    |    Version:  trunk
Resolution:           |   Keywords:       
----------------------+-----------------------------------------------------

Comment (by mosu001):

 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,
 })

-- 
Ticket URL: <https://projects.coin-or.org/Dip/ticket/82#comment:1>
Dip <https://projects.coin-or.org/Dip>
An extensible software framework for implementing decompositon-based bounding algorithms for use in solving large-scale discrete optimization problems.