ideas.txt

Efficiency: For every edge, we want the sum of 1/x where x is the largest path that contains it (if we order the paths by size at the beginning, this is done easily via dfs)
Costly Discard: Can calculate with efficiency and maybe packing so as to force a path to be chosen
Costly Inclusion: We literally do this when calculating the LBs
Packing: Find a large enough set of independent edges (I think we can implement this based on whatever sort and afterwards we can think about how to improve this sorting)
Sum over packing: take the largest path that covers each edge in the packing and then take the largest paths that dont cover any of the edges in the packing, this LB may be INF and give us inviability
Odds per component: Literally number of nodes with odd degree / 2 per component
More bounds based on the fact that we are in a graph??
Model the problem as a max weighted independent set problem
Try to calculate what is the maximum number of edges we can cover with x paths (probably a very low x)

Think about how to integrate hashing with UB propagation
If we do it naively then it doesnt work
I think what we can do is only record the hashing if we update the initial UB, which means we actually found a solution better than the UB
Or maybe check if UB == INF, and if it still INF it means we actually checked for inviability

What makes some instances harder than others? Why the fuck is erdos renyi so freaking hard to solve?????????

Get more types of instances, all3paths seems kind of dumb
Maybe even only do viable instances (start with a cover and then add random paths)

Try other types of branching

Consertar isso: LB = min(LB + search(components[i][4], INF, components[i][0]), INF);

Something I realized: We must allow paths of size 1 for some instances to be solvable, ex: any tree that has a node with two or more leaf vertices and has a parent

We could make a script to run all tests on gurobi and get the result and the time it took and then compare it with our result and time