Open garfield-xue opened 4 years ago
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'
Hi @garfield-xue , this should not happen. Could you provide an easy to run code where I could debug ?
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.
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
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.
Hi,
Due to pre-processing, in CBC some variables may not appear in the lazy cut generator callback.
On Wed, 8 Apr 2020 at 06:12, Wit Jakuczun notifications@github.com wrote:
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.
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/coin-or/python-mip/issues/66#issuecomment-610846064, or unsubscribe https://github.com/notifications/unsubscribe-auth/AB4VZOSQGNJZJ3K6DBVP4QLRLQ5YVANCNFSM4K5HYDDA .
Haroldo Gambini Santos Computing Department Universidade Federal de Ouro Preto - UFOP email: haroldo@ufop.edu.br home/research page: www.decom.ufop.br/haroldo
It has long been an axiom of mine that the little things are infinitely the most important. -- Sir Arthur Conan Doyle, "A Case of Identity"
But is it correct that there is a variable but its "x" attribute is NoneType?
Hmm, this seems wrong, could you share an (preferable not very large) example ?
On Wed, 8 Apr 2020 at 10:40, Wit Jakuczun notifications@github.com wrote:
But is it correct that there is a variable but its "x" attribute is NoneType?
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/coin-or/python-mip/issues/66#issuecomment-610966372, or unsubscribe https://github.com/notifications/unsubscribe-auth/AB4VZOXXGGFM7ICG46KSJBDRLR5FJANCNFSM4K5HYDDA .
Haroldo Gambini Santos Computing Department Universidade Federal de Ouro Preto - UFOP email: haroldo@ufop.edu.br home/research page: www.decom.ufop.br/haroldo
It has long been an axiom of mine that the little things are infinitely the most important. -- Sir Arthur Conan Doyle, "A Case of Identity"
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.
After seeing "Reduced cost fixing - 45 rows, 117 columns - restarting search" message, variable access in lazy_constrs_generator callback will fail. All variable names are changed.
I see that both heuristics and preprocess are turned off at the beginning. Why it still triggers mini B&B?
The strangest thing is that, this only happens when using PyPy3.6. The same program ran just fine under CPython3.6. I'm using PyPy because it's about 30% faster than CPython for my program.
Any clue or workaround? The full program with data is a little bit long, but I can provide that upon request.