Comments (9)
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.
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.
Hi @garfield-xue , this should not happen. Could you provide an easy to run code where I could debug ?
from python-mip.
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.
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.
from python-mip.
But is it correct that there is a variable but its "x" attribute is NoneType?
from python-mip.
from python-mip.
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)
- Issues running the latest versions of Python-MIP on AWS lambda functions HOT 8
- Name 'cbclib' is not defined HOT 12
- Wrong results
- Supporting SCIP
- Improve Example Code Readability HOT 3
- Lazy Callback Question HOT 1
- Incorrect n-Queens Constraints? HOT 1
- Output search tree HOT 1
- Confusing Behaviour with disposing of Gurobi Environment HOT 1
- Incorrect file extension when call write() with CBC solver HOT 1
- Explicitly provide supported versions of Cbc HOT 2
- Passing Solver explicitly causes UnboundLocalError
- [1.15.0] Tests fail: ImportError: cannot import name '__version__' from 'mip._version' (/usr/ports/math/py-mip/work-py39/mip-1.15.0/mip/_version.py) HOT 1
- More verbose errors? HOT 3
- still logging when verbose=0 (on a recent version of CBC)
- Support Python 3.12
- Add py.typed marker HOT 1
- Infeasibility Issue in Python-MIP When Incrementing an Integer Constant HOT 2
- `add_constr` returns broken object when adding constraint without variables HOT 3
- help support mac arm HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
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.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from python-mip.