Code Monkey home page Code Monkey logo

Comments (9)

garfield-xue avatar garfield-xue commented on May 31, 2024 1

I'm playing with node-weighted steiner tree problems. The code below can trigger the error under pypy3.6-v7.3.0 and CPython3.6.5. Python-MIP version is 1.7.2.

from collections import defaultdict
import operator
import sys
from collections import deque
from mip import Model, xsum, minimize, BINARY, ConstrsGenerator, CutPool, OptimizationStatus


tree = """
 8  9  0  9  0 19  1 17  8  5  1  5  0 11
  0  7  8  3  8  8  0 15  0 15  0  7  5 11
 15 19  0  7  0 15 20  9 19  7  8 12  0  3
  6  0 20 11 11  6  0  5  0 18  0  6 10 12
  7 18  1  0  9  0 15 10  1  6  4 20  0 16
  0 10  0 19 16  2 17  0  6  0 11  0  5  3
 10  1 12 16  0 12  0  8  5 14 13  3  3  0
  6  0 14  0  6  9  5  3  0  2  0 19  0 12
  4 18  1  1  1  0 10  0  9 10  6 17  6  9
  1  0 12  0 13 16 12  5  2  0 20  0 19  0
  1 13  4  6  9  0 18  0 15 10 18 13 13  4
  1  0  9  0 10  8  2 14 10  0 10  0  1  0
 13 15 15  9 14  0  2  0 19 15 13 10 10  1

"""

def parse(s):
    print(s)
    ma=[ [int(n) for n in l.split()] for l in s.splitlines() if l]
    nrows = len(ma)
    ncol = len(ma[0])

    w=[w for r in ma for w in r]
    ns = dict([(n+1, w) for n, w in enumerate(w)])

    edges = set()
    dirs = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1)]
    for r in range(nrows):
        for c in range(ncol):
            for dx,dy in dirs:
                ri = r+dx
                ci = c+dy
                if ri < 0 or ci <0 or ri > nrows-1 or ci > ncol-1:
                    continue
                toi = ri*ncol+ci+1
                fri = r*ncol+c+1
                edges.add((fri,toi))
    return ns,edges, nrows, ncol

def border(ns, neighbors, selected, t):
    fifo = deque([t])
    visited = set([t])
    bo = set()
    
    while fifo:
        n = fifo.popleft()
        for ne in neighbors[n]:
            if ne not in selected:
                bo.add(ne)
            elif ne not in visited:
                visited.add(ne)
                fifo.append(ne)
    return bo, visited
                
def seperator(border, vi, uncon, neighbors):
    seps = []
    bo = border
    for k in uncon:
        if not bo:
            break
        sep = set()
        fifo = deque([k])
        visited = set([k])
        
        while fifo:
            n = fifo.popleft()
            for ne in neighbors[n]:
                if ne in visited:
                    continue
                visited.add(ne)
                if ne in bo:
                    sep.add(ne)
                else:
                    fifo.append(ne)
        if sep:
            seps.append(sep)
        break
    return seps
    

def constraint(ns, neighbors, selected, terminals):
    t = next(iter(terminals))
    bo, vi = border(ns, neighbors, selected, t)
    uncon = terminals.difference(vi)
    seps = []
    bos = dict()
    bos[t]=(bo,vi)
    while uncon:
        t = next(iter(uncon))
        bo, vi = border(ns, neighbors, selected, t)
        uncon = uncon.difference(vi)
        bos[t]=(bo,vi)
    kk = set(bos.keys())
    for n, bo in bos.items():
        mm = seperator(*bo, kk.difference(set([n])), neighbors)
        seps.extend(mm)
    sps = sorted(seps, key = len)
    return sps[:3]

class SubTourLazyGenerator(ConstrsGenerator):
    def __init__(self, ns, nsv, neighbors, terminals, nr, nc):
        self.ns = ns
        self.nsv = nsv
        self.neighbors = neighbors
        self.terminals = terminals
        self.nr = nr
        self.nc = nc

    def generate_constrs(self, model: Model):
        nsv = model.translate(self.nsv)
        selected = {n for n, nv in nsv.items() if model.solver.var_get_x(nv) >= 0.99}
        seps = constraint(self.ns, self.neighbors, selected, self.terminals)
        
        if not seps:
            return
        sys.stdout.write('.')
        for sep in seps:
            model += xsum(nsv[s] for s in sep) >= 1

def node_steiner(ns, es, nr, nc):
    model = Model()
    N = len(ns)
    neighbors = defaultdict(set)
    for n1, n2 in es:
        neighbors[n1].add(n2)
        neighbors[n2].add(n1)

    terminals = set([n for n,w in ns.items() if w == 0])
    if len(terminals) == 1:
        print_tree(ns, terminals, nr, nc)
        return

    nsv = dict([(n, model.add_var(var_type=BINARY)) for n in ns])

    for n, w in ns.items():
        if w == 0:
            model += nsv[n] == 1
            model += xsum(nsv[ne] for ne in neighbors[n]) >= 1
            pass
        else:
            model += xsum(nsv[ne] for ne in neighbors[n]) >= 2*nsv[n]
            pass

    model.objective = minimize(xsum([nsv[n]*w for n, w in ns.items() if w != 0]))
    model.lazy_constrs_generator = SubTourLazyGenerator(ns, nsv, neighbors, terminals, nr, nc)
    model.threads = 1
    status = model.optimize()        

node_steiner(*parse(tree))
Using Python-MIP package version 1.7.2
Welcome to the CBC MILP Solver
Version: Trunk
Build Date: Feb 14 2020

Starting solution of the Linear programming relaxation problem using Primal Simplex

Coin0506I Presolve 45 (-183) rows, 117 (-65) columns and 279 (-1201) elements
Clp1000I sum of infeasibilities 1.39593e-07 - average 3.10206e-09, 75 fixed columns
Coin0506I Presolve 36 (-9) rows, 42 (-75) columns and 106 (-173) elements
Clp0029I End of values pass after 42 iterations
Clp0014I Perturbing problem by 0.001% of 1.0000013 - largest nonzero change 2.4432986e-05 ( 0.0012216493%) - largest zero change 2.926242e-05
Clp0000I Optimal - objective value 52.333333
Clp0000I Optimal - objective value 52.333333
Coin0511I After Postsolve, objective 52.333333, infeasibilities - dual 0 (0), primal 0 (0)
Clp0000I Optimal - objective value 52.333333
Clp0000I Optimal - objective value 52.333333
Clp0000I Optimal - objective value 52.333333
Coin0511I After Postsolve, objective 52.333333, infeasibilities - dual 0 (0), primal 0 (0)
Clp0032I Optimal objective 52.33333333 - 0 iterations time 0.002, Presolve 0.00, Idiot 0.00

Starting MIP optimization
Option for preprocess changed from sos to off
Option for heuristicsOnOff changed from on to off
Option for timeMode changed from cpu to elapsed
maxSavedSolutions was changed from 0 to 10
integerTolerance was changed from 1e-06 to 1e-06
Option for mergeCliques changed from off to after
Option for cliqueCuts changed from ifmove to off
Option for bkcliqueCuts changed from off to ifmove
Option for oddholewcCuts changed from off to ifmove
Continuous objective value is 52.3333 - 0.00 seconds
Cgl0015I Clique merge extended 0 cliques, 0 were dominated
Cutoff increment increased from 1e-05 to 0.9999
Cbc0013I At root node, 0 cuts changed objective from 52.333333 to 52.333333 in 1 passes
Cbc0014I Cut generator 0 (LazyConstraints) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Probing) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Gomory) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (BKClique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (OddHoleWC) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 7 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 8 (TwoMirCuts) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 9 (ZeroHalf) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0004I Integer solution of 84 found after 74 iterations and 20 nodes (0.28 seconds)
Cbc0016I Integer solution of 80 found by strong branching after 97 iterations and 26 nodes (0.33 seconds)
Cbc0016I Integer solution of 79 found by strong branching after 108 iterations and 30 nodes (0.35 seconds)
Cbc0038I Full problem 228 rows 182 columns, reduced to 45 rows 117 columns
Cbc0044I Reduced cost fixing - 45 rows, 117 columns - restarting search
Cbc0012I Integer solution of 73 found by Previous solution after 0 iterations and 0 nodes (0.48 seconds)
From cffi callback <function SolverCbc.optimize.<locals>.cbc_cut_callback at 0x7ffff0ed17b8>:
Traceback (most recent call last):
  File "/localworkspaces/pysandbox/lib/python3.6/site-packages/mip/cbc.py", line 763, in cbc_cut_callback
    self.model.lazy_constrs_generator.generate_constrs(osi_model)
  File "/localworkspaces/pysandbox/bug.py", line 120, in generate_constrs
    selected = {n for n, nv in nsv.items() if model.solver.var_get_x(nv) >= 0.99}
  File "/localworkspaces/pysandbox/bug.py", line 120, in <setcomp>
    selected = {n for n, nv in nsv.items() if model.solver.var_get_x(nv) >= 0.99}
  File "/localworkspaces/pysandbox/lib/python3.6/site-packages/mip/cbc.py", line 1833, in var_get_x
    return float(x[var.idx])
AttributeError: 'NoneType' object has no attribute 'idx'
Cbc0031I 1 added rows had average density of 7
Cbc0013I At root node, 1 cuts changed objective from 52.333333 to 55 in 2 passes
Cbc0014I Cut generator 0 (LazyConstraints) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.002 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Probing) - 1 row cuts average 5.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Gomory) - 1 row cuts average 7.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 3 (Knapsack) - 1 row cuts average 5.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 4 (BKClique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 5 (OddHoleWC) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 7 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 8 (TwoMirCuts) - 2 row cuts average 6.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 9 (ZeroHalf) - 2 row cuts average 9.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 10 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0004I Integer solution of 55 found after 2 iterations and 0 nodes (0.48 seconds)
Cbc0001I Search completed - best objective 55, took 2 iterations and 0 nodes (0.48 seconds)
Cbc0035I Maximum depth 0, 1 variables fixed on reduced cost
Cbc0038I LazyConstraints was tried 2 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.002 seconds)
Cbc0038I Probing was tried 2 times and created 1 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0038I Gomory was tried 2 times and created 1 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0038I Knapsack was tried 2 times and created 1 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0038I BKClique was tried 2 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
Cbc0038I OddHoleWC was tried 2 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0038I MixedIntegerRounding2 was tried 2 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0038I FlowCover was tried 2 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0038I TwoMirCuts was tried 2 times and created 2 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0038I ZeroHalf was tried 2 times and created 2 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0038I Clique was tried 2 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cbc0001I Search completed - best objective 79, took 174 iterations and 50 nodes (0.48 seconds)
Cbc0032I Strong branching done 402 times (549 iterations), fathomed 6 nodes and fixed 1 variables
Cbc0035I Maximum depth 13, 1046 variables fixed on reduced cost
Cuts at root node changed objective from 52.3333 to 52.3333
LazyConstraints was tried 226 times and created 897 cuts of which 0 were active after adding rounds of cuts (0.435 seconds)
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
BKClique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
OddHoleWC was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                79.00000000
Enumerated nodes:               50
Total iterations:               174
Time (CPU seconds):             0.48
Time (Wallclock seconds):       0.49

Total time (CPU seconds):       0.48   (Wallclock seconds):       0.49

from python-mip.

garfield-xue avatar garfield-xue commented on May 31, 2024

I just triggered the same error under CPython with a different input.

Starting MIP optimization
Option for heuristicsOnOff changed from on to off
Option for preprocess changed from sos to off
Option for timeMode changed from cpu to elapsed
maxSavedSolutions was changed from 0 to 10
integerTolerance was changed from 1e-06 to 1e-06
Option for mergeCliques changed from off to after
Option for cliqueCuts changed from ifmove to off
Option for bkcliqueCuts changed from off to ifmove
Option for oddholewcCuts changed from off to ifmove
Continuous objective value is 52.3333 - 0.00 seconds
Cgl0015I Clique merge extended 0 cliques, 0 were dominated
Cutoff increment increased from 1e-05 to 0.9999
Cbc0045I MIPStart provided solution with cost 97
Cbc0012I Integer solution of 97 found by Reduced search after 0 iterations and 0 nodes (0.00 seconds)
Cbc0013I At root node, 0 cuts changed objective from 52.333333 to 52.333333 in 1 passes
Cbc0014I Cut generator 0 (LazyConstraints) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Probing) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Gomory) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (BKClique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (OddHoleWC) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 7 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 8 (TwoMirCuts) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 9 (ZeroHalf) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, 97 best solution, best possible 52.333333 (0.02 seconds)
Cbc0016I Integer solution of 92 found by strong branching after 93 iterations and 18 nodes (0.28 seconds)
Cbc0016I Integer solution of 89 found by strong branching after 143 iterations and 28 nodes (0.41 seconds)
Cbc0016I Integer solution of 88 found by strong branching after 253 iterations and 49 nodes (0.61 seconds)
Cbc0038I Full problem 228 rows 182 columns, reduced to 45 rows 117 columns
Cbc0044I Reduced cost fixing - 45 rows, 117 columns - restarting search
Cbc0012I Integer solution of 82 found by Previous solution after 0 iterations and 0 nodes (0.63 seconds)
From cffi callback <function SolverCbc.optimize.<locals>.cbc_cut_callback at 0x7ffff33dcea0>:
Traceback (most recent call last):
  File "/localworkspaces/pysandbox/lib/python3.6/site-packages/mip/cbc.py", line 763, in cbc_cut_callback
    self.model.lazy_constrs_generator.generate_constrs(osi_model)
  File "stp14.py", line 142, in generate_constrs
    selected = [n for n, nv in nsv.items() if nv.x >= 0.99]
  File "stp14.py", line 142, in <listcomp>
    selected = [n for n, nv in nsv.items() if nv.x >= 0.99]
AttributeError: 'NoneType' object has no attribute 'x'

from python-mip.

h-g-s avatar h-g-s commented on May 31, 2024

Hi @garfield-xue , this should not happen. Could you provide an easy to run code where I could debug ?

from python-mip.

fsstol avatar fsstol commented on May 31, 2024

Hi, I just ran into the same issue on CPython 3.7.2 with a large model while doing cut generation with a callback. I tried to no avail to create a simple example that reproduces the behavior.

By printing stats I realized that the model being passed to the callback is considerably smaller than the ones before the error shows up, so there may be an incomplete model being used which causes the problem.

At that point the translate() method can't find the given variables (all the values returned are None), even if I directly call the var_get_index method from SolverCbc, which reinforces the idea of an erroneous processed model.

I will continue trying to come up with a working example.

from python-mip.

WitJakuczun avatar WitJakuczun commented on May 31, 2024

I observe the same error using 1.7.3. Sometimes variables in lazy cut generator are of NoneType or their value (x) is of NoneType.

from python-mip.

h-g-s avatar h-g-s commented on May 31, 2024

from python-mip.

WitJakuczun avatar WitJakuczun commented on May 31, 2024

But is it correct that there is a variable but its "x" attribute is NoneType?

from python-mip.

h-g-s avatar h-g-s commented on May 31, 2024

from python-mip.

sirwhinesalot avatar sirwhinesalot commented on May 31, 2024

I've had this happen to me, the issue was passing something that was not a list of variables to the model.translate() method.
I was passing the .values() of a dict (not the dict itself), which doesn't work.

I suggest changing the code of model.translate() to throw an exception when it cannot do the translation, rather than silently returning the original set of variables.

from python-mip.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.