Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Crashes with free(): invalid next size (fast) #687

Open
NaoPross opened this issue Jan 15, 2025 · 2 comments
Open

Crashes with free(): invalid next size (fast) #687

NaoPross opened this issue Jan 15, 2025 · 2 comments

Comments

@NaoPross
Copy link

NaoPross commented Jan 15, 2025 •
edited
Loading

Hello,

@StoneNimRod was working on a python script using the MIP package that calls CBC to solve the Steiner Tree problem. Python fails silently with a segfault, so it seems like the problem is at this level.

Python script STP_lazy.py 
import mip

# Steiner Tree problem Solver, using MIP and lazy constraints

class LazyConstrGenerator(mip.ConstrsGenerator):

    def __init__(self, x, n, T):
        self.x, self.n, self.T = x, n, T

    def generate_constrs(self, model, depth = 0, npass = 0):
        x = model.translate(self.x)

        # generate adjacency list of current graph
        edges = {i: [] for i in range(self.n)}
        for i in range(self.n):
            for j in range(i):
                if x[i][j].x > 0.99:
                    edges[i].append(j)
                    edges[j].append(i)

        # determine connected components
        cut_pool = mip.CutPool()
        visited = {i: False for i in range(self.n)}
        for v in self.T:
            if visited[v]:
                continue
            terminals = 1
            cc = [v, ]
            visited[v] = True
            i = 0
            while i < len(cc):
                for w in edges[cc[i]]:
                    if not visited[w]:
                        cc.append(w)
                        terminals += (w in self.T)
                        visited[w] = True
                i += 1

            # if terminals lie on different components, add cut constraint
            if terminals < len(self.T):
                cstr = mip.xsum(x[i][j] for i in cc for j in range(self.n) if j not in cc) >= 1
                cut_pool.add(cstr)


        # add constraints
        for cut in cut_pool.cuts:
            model += cut

def solve(distmat, T):
    n = len(distmat)

    model = mip.Model()

    # define binary variables x_ij for i > j
    x = {i: {j: model.add_var(f"x_{i},{j}", var_type=mip.BINARY)
             for j in range(i)}
             for i in range(n)}

    # for convenience, add aliases for i < j
    for i in range(n):
        for j in range(i+1,n):
            x[i][j] = x[j][i]

    # set objective
    model.objective = mip.minimize(mip.xsum(
        distmat[i][j] * x[i][j] for i in range(n) for j in range(i)
    ))

    # add degree constraints
    for k in range(n):
        model += mip.xsum(x[k][j] for j in range(n) if k != j) >= 1

    model.lazy_constrs_generator = LazyConstrGenerator(x, n, T)

    # optimize
    model.verbose = 1
    status = model.optimize()
    assert status == mip.OptimizationStatus.OPTIMAL

    return model.objective_value


if __name__ == "__main__":
    mat = [[   0,  613, 2066, 2353, 2136, 2513, 1771, 1500, 2257, 2285, 1743, 1781],
           [ 613,    0, 2121, 2485, 2098, 2645, 1917, 1632, 2220, 2417, 1875, 1743],
           [2066, 2121,    0, 1125,  626, 1241, 1554, 1386,  684, 1230, 1223, 1109],
           [2353, 2485, 1125,    0, 1440,  188,  936, 1014, 1497,  225,  605, 1722],
           [2136, 2098,  626, 1440,    0, 1575, 1758, 1417,  122, 1487, 1484,  750],
           [2513, 2645, 1241,  188, 1575,    0, 1054, 1131, 1552,  309,  723, 1800],
           [1771, 1917, 1554,  936, 1758, 1054,    0,  319, 1740,  779,  198, 1422],
           [1500, 1632, 1386, 1014, 1417, 1131,  319,    0, 1457, 1031,  420, 1102],
           [2257, 2220,  684, 1497,  122, 1552, 1740, 1457,    0, 1542, 1539,  854],
           [2285, 2417, 1230,  225, 1487,  309,  779, 1031, 1542,    0,  546, 1663],
           [1743, 1875, 1223,  605, 1484,  723,  198,  420, 1539,  546,    0, 1372],
           [1781, 1743, 1109, 1722,  750, 1800, 1422, 1102,  854, 1663, 1372,    0]]

    opt = solve(mat, [0,8])
    print(opt)

How to reproduce

python3 -m venv venv
source ./venv/bin/activate
pip install mip
python3 ./STP_lazy.py

Logs and Traces

Console Output on Linux 
$ python3 STP_lazy.py
Welcome to the CBC MILP Solver
Version: Trunk
Build Date: Oct 24 2021

Starting solution of the Linear programming relaxation problem using Primal Simplex

Coin0506I Presolve 12 (0) rows, 66 (0) columns and 132 (0) elements
Clp1000I sum of infeasibilities 2.0095e-14 - average 1.67459e-15, 60 fixed columns
Coin0506I Presolve 6 (-6) rows, 6 (-60) columns and 12 (-120) elements
Clp0029I End of values pass after 6 iterations
Clp0000I Optimal - objective value 2673.5
Clp0000I Optimal - objective value 2673.5
Coin0511I After Postsolve, objective 2673.5, infeasibilities - dual 0 (0), primal 0 (0)
Clp0014I Perturbing problem by 0.001% of 1.0000013 - largest nonzero change 2.5560987e-05 ( 0.0012780493%) - largest zero change 0
Clp0000I Optimal - objective value 2673.5
Clp0000I Optimal - objective value 2673.5
Clp0000I Optimal - objective value 2673.5
Clp0032I Optimal objective 2673.5 - 0 iterations time 0.002, Idiot 0.00

Starting MIP optimization
Cbc0045I Nauty did not find any useful orbits in time 0
Cbc0013I At root node, 0 cuts changed objective from 2673.5 to 2673.5 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 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 7 (ZeroHalf) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0016I Integer solution of 4784 found by strong branching after 11 iterations and 4 nodes (0.02 seconds)
Cbc0016I Integer solution of 4766 found by strong branching after 16 iterations and 5 nodes (0.03 seconds)
free(): invalid next size (fast)


ERROR while running Cbc. Signal SIGABRT caught. Getting stack trace.
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_Z15CbcCrashHandleri+0x119) [0x7f01ccfc3459]
/lib64/libc.so.6(+0x3dbb0) [0x7f01ce65fbb0]
/lib64/libc.so.6(+0x8e884) [0x7f01ce6b0884]
/lib64/libc.so.6(gsignal+0x1e) [0x7f01ce65fafe]
/lib64/libc.so.6(abort+0xdf) [0x7f01ce64887f]
/lib64/libc.so.6(+0x2760f) [0x7f01ce64960f]
/lib64/libc.so.6(+0x987b5) [0x7f01ce6ba7b5]
/lib64/libc.so.6(+0x9a704) [0x7f01ce6bc704]
/lib64/libc.so.6(__libc_free+0x7e) [0x7f01ce6bf20e]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_ZN18CoinWarmStartBasisD0Ev+0x9) [0x7f01cd4ae889]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_ZN8CbcModel9doOneNodeEPS_RP7CbcNodeS3_+0x391) [0x7f01cd0d9901]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_ZN8CbcModel14branchAndBoundEi+0x5c80) [0x7f01cd0e1fa0]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_Z8CbcMain1iPPKcR8CbcModelPFiPS2_iER19CbcSolverUsefulData+0x15b7f) [0x7f01ccfe5a3f]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(Cbc_solve+0x13a7) [0x7f01ccfbd887]
/lib64/libffi.so.8(+0x7be6) [0x7f01ced6bbe6]
/lib64/libffi.so.8(+0x44bf) [0x7f01ced684bf]
/lib64/libffi.so.8(ffi_call+0x12e) [0x7f01ced6b18e]
/usr/lib64/python3.11/site-packages/_cffi_backend.cpython-311-x86_64-linux-gnu.so(+0x15319) [0x7f01ce503319]
/lib64/libpython3.11.so.1.0(_PyObject_MakeTpCall+0x73) [0x7f01ce9b2173]
/lib64/libpython3.11.so.1.0(_PyEval_EvalFrameDefault+0x7a6) [0x7f01ce9ba996]
/lib64/libpython3.11.so.1.0(+0x1b6bba) [0x7f01ce9b6bba]
/lib64/libpython3.11.so.1.0(PyEval_EvalCode+0xac) [0x7f01cea3b15c]
/lib64/libpython3.11.so.1.0(+0x258413) [0x7f01cea58413]
/lib64/libpython3.11.so.1.0(+0x254a7a) [0x7f01cea54a7a]
/lib64/libpython3.11.so.1.0(+0x26a632) [0x7f01cea6a632]
/lib64/libpython3.11.so.1.0(_PyRun_SimpleFileObject+0x1b8) [0x7f01cea69e18]
/lib64/libpython3.11.so.1.0(_PyRun_AnyFileObject+0x48) [0x7f01cea69aa8]
/lib64/libpython3.11.so.1.0(Py_RunMain+0x2cc) [0x7f01cea638ec]
/lib64/libpython3.11.so.1.0(Py_BytesMain+0x3b) [0x7f01cea2b48b]
/lib64/libc.so.6(+0x27b8a) [0x7f01ce649b8a]
/lib64/libc.so.6(__libc_start_main+0x8b) [0x7f01ce649c4b]
python3(_start+0x25) [0x55eff3f05095]




ERROR while running Cbc. Signal SIGABRT caught. Getting stack trace.
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_Z15CbcCrashHandleri+0x119) [0x7f01ccfc3459]
/lib64/libc.so.6(+0x3dbb0) [0x7f01ce65fbb0]
/lib64/libc.so.6(+0x8e884) [0x7f01ce6b0884]
/lib64/libc.so.6(gsignal+0x1e) [0x7f01ce65fafe]
/lib64/libc.so.6(abort+0xdf) [0x7f01ce64887f]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(+0x1772d2) [0x7f01ccf772d2]
/lib64/libc.so.6(+0x3dbb0) [0x7f01ce65fbb0]
/lib64/libc.so.6(+0x8e884) [0x7f01ce6b0884]
/lib64/libc.so.6(gsignal+0x1e) [0x7f01ce65fafe]
/lib64/libc.so.6(abort+0xdf) [0x7f01ce64887f]
/lib64/libc.so.6(+0x2760f) [0x7f01ce64960f]
/lib64/libc.so.6(+0x987b5) [0x7f01ce6ba7b5]
/lib64/libc.so.6(+0x9a704) [0x7f01ce6bc704]
/lib64/libc.so.6(__libc_free+0x7e) [0x7f01ce6bf20e]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_ZN18CoinWarmStartBasisD0Ev+0x9) [0x7f01cd4ae889]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_ZN8CbcModel9doOneNodeEPS_RP7CbcNodeS3_+0x391) [0x7f01cd0d9901]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_ZN8CbcModel14branchAndBoundEi+0x5c80) [0x7f01cd0e1fa0]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(_Z8CbcMain1iPPKcR8CbcModelPFiPS2_iER19CbcSolverUsefulData+0x15b7f) [0x7f01ccfe5a3f]
/home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so(Cbc_solve+0x13a7) [0x7f01ccfbd887]
/lib64/libffi.so.8(+0x7be6) [0x7f01ced6bbe6]
/lib64/libffi.so.8(+0x44bf) [0x7f01ced684bf]
/lib64/libffi.so.8(ffi_call+0x12e) [0x7f01ced6b18e]
/usr/lib64/python3.11/site-packages/_cffi_backend.cpython-311-x86_64-linux-gnu.so(+0x15319) [0x7f01ce503319]
/lib64/libpython3.11.so.1.0(_PyObject_MakeTpCall+0x73) [0x7f01ce9b2173]
/lib64/libpython3.11.so.1.0(_PyEval_EvalFrameDefault+0x7a6) [0x7f01ce9ba996]
/lib64/libpython3.11.so.1.0(+0x1b6bba) [0x7f01ce9b6bba]
/lib64/libpython3.11.so.1.0(PyEval_EvalCode+0xac) [0x7f01cea3b15c]
/lib64/libpython3.11.so.1.0(+0x258413) [0x7f01cea58413]
/lib64/libpython3.11.so.1.0(+0x254a7a) [0x7f01cea54a7a]
/lib64/libpython3.11.so.1.0(+0x26a632) [0x7f01cea6a632]
/lib64/libpython3.11.so.1.0(_PyRun_SimpleFileObject+0x1b8) [0x7f01cea69e18]
/lib64/libpython3.11.so.1.0(_PyRun_AnyFileObject+0x48) [0x7f01cea69aa8]
/lib64/libpython3.11.so.1.0(Py_RunMain+0x2cc) [0x7f01cea638ec]
/lib64/libpython3.11.so.1.0(Py_BytesMain+0x3b) [0x7f01cea2b48b]
/lib64/libc.so.6(+0x27b8a) [0x7f01ce649b8a]
/lib64/libc.so.6(__libc_start_main+0x8b) [0x7f01ce649c4b]
python3(_start+0x25) [0x55eff3f05095]

Running it with GDB gives more details, so it may be related to #211

GDB Output 
$ gdb python3
GNU gdb (GDB) Fedora Linux 13.2-6.fc38
Copyright (C) 2023 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-redhat-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from python3...
Reading symbols from /home/sysmaster/.cache/debuginfod_client/68dbf1c2fdfa0701964120231a7af395fae67499/debuginfo...
(gdb) run STP_lazy.py
Starting program: /usr/bin/python3 STP_lazy.py
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".
Downloading separate debug info for /usr/lib64/python3.11/site-packages/_cffi_backend.cpython-311-x86_64-linux-gnu.so
[Detaching after vfork from child process 2528952]
... many more vfork, cut for brevity ...
[Detaching after vfork from child process 2529226]
[Detaching after vfork from child process 2529227]
[Detaching after vfork from child process 2529230]
Welcome to the CBC MILP Solver
Version: Trunk
Build Date: Oct 24 2021

Starting solution of the Linear programming relaxation problem using Primal Simplex

Coin0506I Presolve 12 (0) rows, 66 (0) columns and 132 (0) elements
Clp1000I sum of infeasibilities 2.0095e-14 - average 1.67459e-15, 60 fixed columns
Coin0506I Presolve 6 (-6) rows, 6 (-60) columns and 12 (-120) elements
Clp0029I End of values pass after 6 iterations
Clp0000I Optimal - objective value 2673.5
Clp0000I Optimal - objective value 2673.5
Coin0511I After Postsolve, objective 2673.5, infeasibilities - dual 0 (0), primal 0 (0)
Clp0014I Perturbing problem by 0.001% of 1.0000013 - largest nonzero change 2.5560987e-05 ( 0.0012780493%) - largest zero change 0
Clp0000I Optimal - objective value 2673.5
Clp0000I Optimal - objective value 2673.5
Clp0000I Optimal - objective value 2673.5
Clp0032I Optimal objective 2673.5 - 0 iterations time 0.002, Idiot 0.00

Starting MIP optimization
Cbc0045I Nauty did not find any useful orbits in time 0.000165
Cbc0013I At root node, 0 cuts changed objective from 2673.5 to 2673.5 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 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 7 (ZeroHalf) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0016I Integer solution of 4784 found by strong branching after 11 iterations and 4 nodes (0.02 seconds)
Cbc0016I Integer solution of 4766 found by strong branching after 16 iterations and 5 nodes (0.03 seconds)
free(): invalid next size (fast)

Program received signal SIGABRT, Aborted.
__pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0) at pthread_kill.c:44
44            return INTERNAL_SYSCALL_ERROR_P (ret) ? INTERNAL_SYSCALL_ERRNO (ret) : 0;
(gdb) bt
#0  __pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0) at pthread_kill.c:44
#1  0x00007ffff78b08f3 in __pthread_kill_internal (signo=6, threadid=<optimized out>) at pthread_kill.c:78
#2  0x00007ffff785fafe in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
#3  0x00007ffff784887f in __GI_abort () at abort.c:79
#4  0x00007ffff784960f in __libc_message (fmt=fmt@entry=0x7ffff79c352f "%s\n") at ../sysdeps/posix/libc_fatal.c:150
#5  0x00007ffff78ba7b5 in malloc_printerr (str=str@entry=0x7ffff79c6298 "free(): invalid next size (fast)") at malloc.c:5658
#6  0x00007ffff78bc704 in _int_free (av=0x7ffff79f6c80 <main_arena>, p=p@entry=0x555555af1fb0, have_lock=have_lock@entry=0) at malloc.c:4515
#7  0x00007ffff78bf20e in __GI___libc_free (mem=0x555555af1fc0) at malloc.c:3367
#8  0x00007ffff64ae889 in CoinWarmStartBasis::~CoinWarmStartBasis() () from /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so
#9  0x00007ffff60d9901 in CbcModel::doOneNode(CbcModel*, CbcNode*&, CbcNode*&) () from /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so
#10 0x00007ffff60e1fa0 in CbcModel::branchAndBound(int) () from /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so
#11 0x00007ffff5fe5a3f in CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) ()
   from /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so
#12 0x00007ffff5fbd887 in Cbc_solve () from /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so
#13 0x00007ffff7f5ebe6 in ffi_call_unix64 () at ../src/x86/unix64.S:104
#14 0x00007ffff7f5b4bf in ffi_call_int (cif=cif@entry=0x7ffff6b7b570, fn=<optimized out>, rvalue=<optimized out>, avalue=<optimized out>, closure=closure@entry=0x0)
    at ../src/x86/ffi64.c:673
#15 0x00007ffff7f5e18e in ffi_call (cif=cif@entry=0x7ffff6b7b570, fn=<optimized out>, rvalue=rvalue@entry=0x7ffff6ac11d8, avalue=avalue@entry=0x7ffff6ac11d0)
    at ../src/x86/ffi64.c:710
#16 0x00007ffff7701319 in cdata_call (cd=<optimized out>, args=<optimized out>, kwds=<optimized out>) at c/_cffi_backend.c:3192
#17 0x00007ffff7bb2173 in _PyObject_MakeTpCall (tstate=0x7ffff7f10538 <_PyRuntime+166328>, callable=0x7ffff6b77540, args=<optimized out>, nargs=1, keywords=<optimized out>)
    at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Objects/call.c:214
#18 0x00007ffff7bba996 in _PyEval_EvalFrameDefault (tstate=<optimized out>, frame=<optimized out>, throwflag=<optimized out>)
    at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Python/ceval.c:4760
#19 0x00007ffff7bb6bba in _PyEval_EvalFrame (throwflag=0, frame=0x7ffff7fb8020, tstate=0x7ffff7f10538 <_PyRuntime+166328>)
    at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Include/internal/pycore_ceval.h:73
#20 _PyEval_Vector (tstate=tstate@entry=0x7ffff7f10538 <_PyRuntime+166328>, func=func@entry=0x7ffff73984a0, locals=locals@entry=0x7ffff73f2880, args=args@entry=0x0,
    argcount=argcount@entry=0, kwnames=kwnames@entry=0x0) at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Python/ceval.c:6425
#21 0x00007ffff7c3b15c in PyEval_EvalCode (co=0x7ffff72241b0, globals=<optimized out>, locals=0x7ffff73f2880)
    at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Python/ceval.c:1140
#22 0x00007ffff7c58413 in run_eval_code_obj (tstate=tstate@entry=0x7ffff7f10538 <_PyRuntime+166328>, co=co@entry=0x7ffff72241b0, globals=globals@entry=0x7ffff73f2880,
    locals=locals@entry=0x7ffff73f2880) at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Python/pythonrun.c:1710
#23 0x00007ffff7c54a7a in run_mod (mod=mod@entry=0x55555561e400, filename=filename@entry=0x7ffff73f7a00, globals=globals@entry=0x7ffff73f2880,
    locals=locals@entry=0x7ffff73f2880, flags=flags@entry=0x7fffffffde88, arena=arena@entry=0x7ffff731b7b0)
    at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Python/pythonrun.c:1731
#24 0x00007ffff7c6a632 in pyrun_file (fp=fp@entry=0x5555555cb070, filename=filename@entry=0x7ffff73f7a00, start=start@entry=257, globals=globals@entry=0x7ffff73f2880,
    locals=locals@entry=0x7ffff73f2880, closeit=closeit@entry=1, flags=0x7fffffffde88) at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Python/pythonrun.c:1626
#25 0x00007ffff7c69e18 in _PyRun_SimpleFileObject (fp=0x5555555cb070, filename=0x7ffff73f7a00, closeit=1, flags=0x7fffffffde88)
    at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Python/pythonrun.c:440
#26 0x00007ffff7c69aa8 in _PyRun_AnyFileObject (fp=0x5555555cb070, filename=0x7ffff73f7a00, closeit=1, flags=0x7fffffffde88)
    at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Python/pythonrun.c:79
#27 0x00007ffff7c638ec in pymain_run_file_obj (skip_source_first_line=0, filename=0x7ffff73f7a00, program_name=0x7ffff73f79b0)
    at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Modules/main.c:360
#28 pymain_run_file (config=0x7ffff7ef6580 <_PyRuntime+59904>) at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Modules/main.c:379
#29 pymain_run_python (exitcode=0x7fffffffde80) at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Modules/main.c:601
#30 Py_RunMain () at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Modules/main.c:680
--Type <RET> for more, q to quit, c to continue without paging--
#31 0x00007ffff7c2b48b in Py_BytesMain (argc=<optimized out>, argv=<optimized out>) at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Modules/main.c:734
#32 0x00007ffff7849b8a in __libc_start_call_main (main=main@entry=0x555555555160 <main>, argc=argc@entry=2, argv=argv@entry=0x7fffffffe0e8)
    at ../sysdeps/nptl/libc_start_call_main.h:58
#33 0x00007ffff7849c4b in __libc_start_main_impl (main=0x555555555160 <main>, argc=2, argv=0x7fffffffe0e8, init=<optimized out>, fini=<optimized out>,
    rtld_fini=<optimized out>, stack_end=0x7fffffffe0d8) at ../csu/libc-start.c:360
#34 0x0000555555555095 in _start ()

Running valgrind, it is not happy.

Valgrind output 
$ export PYTHONMALLOC=malloc
$ valgrind python3 STP_lazy.py
==2531763== Memcheck, a memory error detector
==2531763== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==2531763== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==2531763== Command: python3 STP_lazy.py
==2531763==
==2531763== Conditional jump or move depends on uninitialised value(s)
==2531763==    at 0x4A5EFE3: UnknownInlinedFun (longobject.c:71)
==2531763==    by 0x4A5EFE3: _PyLong_FromByteArray (longobject.c:922)
==2531763==    by 0x4A5EBB5: UnknownInlinedFun (longobject.c:5946)
==2531763==    by 0x4A5EBB5: int_from_bytes (longobject.c.h:389)
==2531763==    by 0x4A2B3E9: cfunction_vectorcall_FASTCALL_KEYWORDS (methodobject.c:443)
==2531763==    by 0x4A2B356: UnknownInlinedFun (pycore_call.h:92)
==2531763==    by 0x4A2B356: PyObject_Vectorcall (call.c:299)
==2531763==    by 0x4A1D995: _PyEval_EvalFrameDefault (ceval.c:4760)
==2531763==    by 0x4A19BB9: UnknownInlinedFun (pycore_ceval.h:73)
==2531763==    by 0x4A19BB9: _PyEval_Vector (ceval.c:6425)
==2531763==    by 0x4A31675: UnknownInlinedFun (pycore_call.h:92)
==2531763==    by 0x4A31675: object_vacall (call.c:819)
==2531763==    by 0x4A558A3: PyObject_CallMethodObjArgs (call.c:879)
==2531763==    by 0x4A53FA1: UnknownInlinedFun (import.c:1737)
==2531763==    by 0x4A53FA1: PyImport_ImportModuleLevelObject (import.c:1836)
==2531763==    by 0x4A6005B: UnknownInlinedFun (bltinmodule.c:277)
==2531763==    by 0x4A6005B: builtin___import__ (bltinmodule.c.h:78)
==2531763==    by 0x4A2B3E9: cfunction_vectorcall_FASTCALL_KEYWORDS (methodobject.c:443)
==2531763==    by 0x4A12248: UnknownInlinedFun (pycore_call.h:92)
==2531763==    by 0x4A12248: _PyObject_CallFunctionVa (call.c:536)
==2531763==
==2531763== Use of uninitialised value of size 8
==2531763==    at 0x4A5F00B: UnknownInlinedFun (object.h:502)
==2531763==    by 0x4A5F00B: UnknownInlinedFun (longobject.c:62)
==2531763==    by 0x4A5F00B: UnknownInlinedFun (longobject.c:73)
==2531763==    by 0x4A5F00B: _PyLong_FromByteArray (longobject.c:922)
==2531763==    by 0x4A5EBB5: UnknownInlinedFun (longobject.c:5946)
==2531763==    by 0x4A5EBB5: int_from_bytes (longobject.c.h:389)
==2531763==    by 0x4A2B3E9: cfunction_vectorcall_FASTCALL_KEYWORDS (methodobject.c:443)
==2531763==    by 0x4A2B356: UnknownInlinedFun (pycore_call.h:92)
==2531763==    by 0x4A2B356: PyObject_Vectorcall (call.c:299)
==2531763==    by 0x4A1D995: _PyEval_EvalFrameDefault (ceval.c:4760)
==2531763==    by 0x4A19BB9: UnknownInlinedFun (pycore_ceval.h:73)
==2531763==    by 0x4A19BB9: _PyEval_Vector (ceval.c:6425)
==2531763==    by 0x4A31675: UnknownInlinedFun (pycore_call.h:92)
==2531763==    by 0x4A31675: object_vacall (call.c:819)
==2531763==    by 0x4A558A3: PyObject_CallMethodObjArgs (call.c:879)
==2531763==    by 0x4A53FA1: UnknownInlinedFun (import.c:1737)
==2531763==    by 0x4A53FA1: PyImport_ImportModuleLevelObject (import.c:1836)
==2531763==    by 0x4A6005B: UnknownInlinedFun (bltinmodule.c:277)
==2531763==    by 0x4A6005B: builtin___import__ (bltinmodule.c.h:78)
==2531763==    by 0x4A2B3E9: cfunction_vectorcall_FASTCALL_KEYWORDS (methodobject.c:443)
==2531763==    by 0x4A12248: UnknownInlinedFun (pycore_call.h:92)
==2531763==    by 0x4A12248: _PyObject_CallFunctionVa (call.c:536)
==2531763==
Welcome to the CBC MILP Solver
Version: Trunk
Build Date: Oct 24 2021

Starting solution of the Linear programming relaxation problem using Primal Simplex

Coin0506I Presolve 12 (0) rows, 66 (0) columns and 132 (0) elements
Clp1000I sum of infeasibilities 2.0095e-14 - average 1.67459e-15, 60 fixed columns
Coin0506I Presolve 6 (-6) rows, 6 (-60) columns and 12 (-120) elements
Clp0029I End of values pass after 6 iterations
Clp0000I Optimal - objective value 2673.5
Clp0000I Optimal - objective value 2673.5
Coin0511I After Postsolve, objective 2673.5, infeasibilities - dual 0 (0), primal 0 (0)
Clp0014I Perturbing problem by 0.001% of 1.0000013 - largest nonzero change 2.5560987e-05 ( 0.0012780493%) - largest zero change 0
Clp0000I Optimal - objective value 2673.5
Clp0000I Optimal - objective value 2673.5
Clp0000I Optimal - objective value 2673.5
Clp0032I Optimal objective 2673.5 - 0 iterations time 0.832, Idiot 0.64

Starting MIP optimization
Cbc0045I Nauty did not find any useful orbits in time 0.08893
Cbc0013I At root node, 0 cuts changed objective from 2673.5 to 2673.5 in 1 passes
Cbc0014I Cut generator 0 (LazyConstraints) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.022 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 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 7 (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, 1e+50 best solution, best possible 2673.5 (0.86 seconds)
Cbc0010I After 3 nodes, 4 on tree, 1e+50 best solution, best possible 2673.5 (1.73 seconds)
Cbc0016I Integer solution of 4784 found by strong branching after 11 iterations and 4 nodes (1.92 seconds)
Cbc0016I Integer solution of 4766 found by strong branching after 16 iterations and 5 nodes (2.18 seconds)
Cbc0010I After 6 nodes, 3 on tree, 4766 best solution, best possible 2673.5 (2.64 seconds)
Cbc0010I After 13 nodes, 6 on tree, 4766 best solution, best possible 2673.5 (3.56 seconds)
Cbc0010I After 20 nodes, 3 on tree, 4766 best solution, best possible 2673.5 (4.39 seconds)
Cbc0010I After 24 nodes, 4 on tree, 4766 best solution, best possible 2673.5 (5.09 seconds)
==2531763== Invalid write of size 4
==2531763==    at 0x8CB0627: CoinWarmStartBasis::applyDiff(CoinWarmStartDiff const*) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x88FA746: CbcPartialNodeInfo::applyToModel(CbcModel*, CoinWarmStartBasis*&, CbcCountRowCut**, int&) const (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x88BDEE4: CbcModel::addCuts1(CbcNode*, CoinWarmStartBasis*&) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x88C3C9B: CbcModel::addCuts(CbcNode*, CoinWarmStartBasis*&) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x88D96F0: CbcModel::doOneNode(CbcModel*, CbcNode*&, CbcNode*&) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x88E1F9F: CbcModel::branchAndBound(int) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x87E5A3E: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x87BD886: Cbc_solve (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x5FA5BE5: ffi_call_unix64 (unix64.S:104)
==2531763==    by 0x5FA24BE: ffi_call_int.lto_priv.0 (ffi64.c:673)
==2531763==    by 0x5FA518D: ffi_call (ffi64.c:710)
==2531763==    by 0x5F72318: cdata_call (_cffi_backend.c:3192)
==2531763==  Address 0x82e6e48 is 0 bytes after a block of size 24 alloc'd
==2531763==    at 0x4844723: operator new[](unsigned long) (vg_replace_malloc.c:725)
==2531763==    by 0x8CB1790: CoinWarmStartBasis::CoinWarmStartBasis(CoinWarmStartBasis const&) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x8921279: CbcFullNodeInfo::applyToModel(CbcModel*, CoinWarmStartBasis*&, CbcCountRowCut**, int&) const (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x88BDEE4: CbcModel::addCuts1(CbcNode*, CoinWarmStartBasis*&) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x88C3C9B: CbcModel::addCuts(CbcNode*, CoinWarmStartBasis*&) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x88D96F0: CbcModel::doOneNode(CbcModel*, CbcNode*&, CbcNode*&) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x88E1F9F: CbcModel::branchAndBound(int) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x87E5A3E: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x87BD886: Cbc_solve (in /home/sysmaster/.local/lib/python3.11/site-packages/mip/libraries/cbc-c-linux-x86-64.so)
==2531763==    by 0x5FA5BE5: ffi_call_unix64 (unix64.S:104)
==2531763==    by 0x5FA24BE: ffi_call_int.lto_priv.0 (ffi64.c:673)
==2531763==    by 0x5FA518D: ffi_call (ffi64.c:710)
==2531763==
Cbc0010I After 27 nodes, 5 on tree, 4766 best solution, best possible 2673.5 (5.83 seconds)
Cbc0010I After 33 nodes, 1 on tree, 4766 best solution, best possible 4125 (6.83 seconds)
Cbc0010I After 40 nodes, 1 on tree, 4766 best solution, best possible 4719 (7.55 seconds)
Cbc0001I Search completed - best objective 4766, took 152 iterations and 41 nodes (7.61 seconds)
Cbc0032I Strong branching done 172 times (261 iterations), fathomed 4 nodes and fixed 3 variables
Cbc0035I Maximum depth 7, 359 variables fixed on reduced cost
Total time (CPU seconds):       7.68   (Wallclock seconds):       7.76

4766.0
==2531763==
==2531763== HEAP SUMMARY:
==2531763==     in use at exit: 557,653 bytes in 2,888 blocks
==2531763==   total heap usage: 633,326 allocs, 630,438 frees, 145,561,480 bytes allocated
==2531763==
==2531763== LEAK SUMMARY:
==2531763==    definitely lost: 82,368 bytes in 39 blocks
==2531763==    indirectly lost: 0 bytes in 0 blocks
==2531763==      possibly lost: 61,625 bytes in 455 blocks
==2531763==    still reachable: 413,660 bytes in 2,394 blocks
==2531763==         suppressed: 0 bytes in 0 blocks
==2531763== Rerun with --leak-check=full to see details of leaked memory
==2531763==
==2531763== Use --track-origins=yes to see where uninitialised values come from
==2531763== For lists of detected and suppressed errors, rerun with: -s
==2531763== ERROR SUMMARY: 205 errors from 3 contexts (suppressed: 0 from 0)

System Information and Versions

System information 
$ python3 --version
Python 3.11.6
$ python3 -c "import mip; print(mip.__version__)"
1.15.0
$ cat /etc/os-release
NAME="Fedora Linux"
VERSION="38 (Server Edition)"
ID=fedora
VERSION_ID=38
VERSION_CODENAME=""
PLATFORM_ID="platform:f38"
PRETTY_NAME="Fedora Linux 38 (Server Edition)"
ANSI_COLOR="0;38;2;60;110;180"
LOGO=fedora-logo-icon
CPE_NAME="cpe:/o:fedoraproject:fedora:38"
HOME_URL="https://fedoraproject.org/"
DOCUMENTATION_URL="https://docs.fedoraproject.org/en-US/fedora/f38/system-administrators-guide/"
SUPPORT_URL="https://ask.fedoraproject.org/"
BUG_REPORT_URL="https://bugzilla.redhat.com/"
REDHAT_BUGZILLA_PRODUCT="Fedora"
REDHAT_BUGZILLA_PRODUCT_VERSION=38
REDHAT_SUPPORT_PRODUCT="Fedora"
REDHAT_SUPPORT_PRODUCT_VERSION=38
SUPPORT_END=2024-05-14
VARIANT="Server Edition"
VARIANT_ID=server
@NaoPross NaoPross changed the title Crash at CbcModel::currentNode() Crash at CbcModel::currentNode() Jan 15, 2025
@NaoPross NaoPross changed the title Crash at CbcModel::currentNode() Crashes with free(): invalid next size (fast) Jan 15, 2025
@jjhforrest
Copy link
Contributor

Probably a bug in stable dealing with lazy constraints - as they are not much used. It looks as if the code does not quite realize it has added a row so modifies a basis variable just off the status array. I have failed to get a good debug stable version of Cbc into python "mip" - getting undefined synbols which do not seem to be in stable C interface. Using master (which has much more code in its C interface) everything seems to work.

@NaoPross
Copy link
Author

NaoPross commented Jan 16, 2025 •
edited
Loading

That was quick, thanks.

I have failed to get a good debug stable version of Cbc into python "mip" - getting undefined symbols which do not seem to be in stable C interface. Using master (which has much more code in its C interface) everything seems to work.

To clarify, using master of CBC using these instructions or master for the python-mip package? So that I can take a look again later today.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@jjhforrest @NaoPross