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

[Dip]

#82: Infinite loop in DIP
--------------------+-------------------------------------------------------
Reporter:  mosu001  |       Type:  defect
  Status:  new      |   Priority:  major 
 Version:  trunk    |   Keywords:        
--------------------+-------------------------------------------------------
 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

-- 
Ticket URL: <https://projects.coin-or.org/Dip/ticket/82>
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.