todo.md 5.72 KB
 msurl committed Jun 03, 2020 1 2 3 4 # Week 4 ## Python ### implementation * Refactor code.  Mario Surlemont committed Jun 07, 2020 5  - Fix bug with separators. ✔  Mario Surlemont committed Jun 07, 2020 6  - Add option to cli to select which type of inequalities to be included. ✔  msurl committed Jun 03, 2020 7 * Implement different type of constraints.  Mario Surlemont committed Jun 11, 2020 8  - _Solving the Maximum-Weight Connected Subgraph Problem to Optimality_ ❌ (moved to backlog)  Mario Surlemont committed Jun 07, 2020 9 10  - _Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming_ ✔ - Only one type of constraints which performed best in this paper. Performs bad on our graphs.  msurl committed Jun 03, 2020 11 12  ### runtime  Mario Surlemont committed Jun 10, 2020 13 * Do tests according to test concept and store data in some sort of strucured format(CSV/ XML/ JSON) which could be importet in python or R. ✔  msurl committed Jun 03, 2020 14 15  ## thesis  Mario Surlemont committed Jun 11, 2020 16 * Begin paragraph about results and add preliminary results and observations. ❌ (moved to week 5)  Mario Surlemont committed Jun 11, 2020 17  - Create a concept how to test and which test results you want to include. (✔) (a preliminary concept)  msurl committed Jun 03, 2020 18 19 20  ## literature * Read _Imposing Connectivity Constraints in Forest Planning Models_.  Mario Surlemont committed Jun 11, 2020 21  - Check for different constraints which could strengthen the formulation. ❌ (moved to week 5. But with focus on symmetry breaking)  Mario Surlemont committed Jun 11, 2020 22 * Read _Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming_ ✔  msurl committed Jun 03, 2020 23  - Different constraints to induce connectivity are compared. Try to implement some of them to compare them and see which one is best. You may see if this is related to a charateristic of your graphs. As the literature may states that for some type of graphs some approaches are better.  Mario Surlemont committed Jun 11, 2020 24 * Check _On imposing connectivity constraints in integer programs_ again to see if there is some other literature which you are missing. ❌ (moved to week 5)  msurl committed Jun 03, 2020 25 26   Mario Surlemont committed Jun 11, 2020 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 # Week 5 ## Python ### implementation * Try to implement a symmetry breaker to check if this affects especially the runtime which is needed to close the gap and exclude all unconnected solutions with at most as many nodes as an optimal connected. - May implement My Ky's, even if it is not optimal/ 100% correct. Just to observe if there is a connection between symmetrical unconnected solutions and the runtime and how strong this connection is. (Possible indicators: runtime, number of lazily added constraints) ### runtime * Create random graphs and try to compare runtime between ILP and ASP. - Measure some characteristics of the graphs such as density, |V|, |E|, maximum degree, minimum degree, average degree, (maybe standard derivation of degree or median degree?) - Measure and note gap between |D| of a minimal connected and a minimal unconnected solution. Measure for each |D| number of unconnected solutions which were found(ILP-only) and how many constraints where added in sum. - Measure the time which was needed to find the first (nearly) optimal solution (strong upper bound) and the time needed to close the gap. * Make some more detailed tests and check for the following connections: - To what degree does the number of unconnected k-hop solutions which have at most as many nodes as an optimal connected solution affect the runtime? (Calculate how many of them exist and add this data as a column to a table of test results) - Is there a clear corellation between the number of constraints which were added and the runtime for (possible unconnected) solutions? - Check for graphs where the gap between an optimal connected solution and the smallest unconnected solution is rather big if this approach(our implementation) might be unapplyable. Such that there is too much time wasted to exclude all possible unconnected solutions and increase the lower bound. * Implement a heuristic to start with a stronger lower bound. - Given a symmetrical leaf where the root is centered (at least on the x-axis). There are at least ![width-2*k+height-k-\frac{width}{2}-k](https://render.githubusercontent.com/render/math?math=width-2*k%2Bheight-k-%5Cfrac%7Bwidth%7D%7B2%7D-k) nodes needed to provide a connected dominating set. - To reach both rims in the width and the rim on the top. ## thesis * Begin paragraph about results and add preliminary results and observations. - Refinde the concept how to test and which test results you want to include. ## literature * Read _Imposing Connectivity Constraints in Forest Planning Models_. - Check for different constraints which could strengthen the formulation. (with focus on symmetry breaking) * Read _An Efficient Branch and Cut Algorithm to Find Frequently Mutated Subnetworks in Cancer_ again with focus on symmetry breaking. * Read through _An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets*_ again and check for symmetry breaking or other constraints to tighten up the space of solutions.  msurl committed Jun 03, 2020 54 55 56 57 58  # Backlog ## Python ### Implementation * Remove lp_to_graph from package and instead use some other format to store graphs and use them as input.  Mario Surlemont committed Jun 11, 2020 59 60 61 62 63 64 65 66 67 68 69 70 * Implement different type of constraints. - _Solving the Maximum-Weight Connected Subgraph Problem to Optimality_ * Carefully check the literature i.e. _An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets*_, _An Efficient Branch and Cut Algorithm to Find Frequently Mutated Subnetworks in Cancer_, _Thinning out Steiner trees: a node-based model for uniform edge costs_ to check if they did anything differently according to the sepearating constraints. * Check if something from the algorithmic framework of _Thinning out Steiner trees: a node-based model for uniform edge costs_ can be applied to our case. (Local Branching, Heuristic, etc.) * Implement a heuristic to provide a better upper bound. - The intermediate root constraint could be useful to do so. ### packaging * Add unit tests to the package * Add dependencies to the recipe * Find a place to store the code if the package will be published(Maybe a standard github repo)