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

Infinite loop in DIP #82

Open svigerske opened 5 years ago

svigerske commented 5 years ago

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) \

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 commented 5 years ago

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) \

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 commented 5 years ago

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.