progress.md

Week 1

Python

Implementation

• I implemented an ILP Model to solve K-hop-dominating set using min. vertex separators.
• I refactored the implementation using an object oriented approach

packaging

• I fetched a cookiecutter template to create a conda package
• One can build this package via conda build and install it locally. It contains a cli. So one can use the package as cli-tool inside his/her conda environment and use optional parameters to specify the input and different parameters
• There is still stuff to do to deliver a clean package

runtime

• the first test has shown a horrible runtime. I've sticked to an ILP implementation similar to the proposed in An Efficient Branch and Cut Algorithm to Find Frequently Mutated Subnetworks in Cancer
• the middle leaf.lp needed 7 hours to be solved on my laptop (which is not just a better toaster)
• I tried developed different additional constraints which include the length of the shortest path between the root node and nodes inside the DS. This did not improve the runtime.
• I then added an additional constraint mentioned in Thinning out Steiner trees: a node-based model for uniform edge costs. This did significantly improve the runtime. Middle leaf.pl only needed 45 seconds. BUT unfortunately this constraint can not be applied for our problem and it increases the number of nodes included in a solution.
• I did screenshots from different runs to document the runtime

Literature

• I read parts of the literature added to the repo and tried to figure out if there are other inequalities which define the connectivity which may be applyable to the problem. Or if there are other techniques which can improve the runtime but still use the vertex separators as connectivity defining inequalities.

Week 2

Python

Implementation

• I implemented a callback function to be used if an (unconnected) integer solution is found. Previously I called model.optimize() each time some lazy constraints were added which caused a horrible runtime.
• I implemented different additional constraints to reduce the runtime.

runtime

• After using the callback function it takes ~103s to solve the bigger-leaf graph with parameter k = 2.

• When using the constraint from Thinning out Steiner trees: a node-based model for uniform edge costs it takes ~5 s.

• As this constraint is not applyable I added another constraint which is "inspired" by the previous constraint. After implementing this constraint solving the bigger-leaf with k = 2 took ~80s.

• Then I tried to add vertex separator constraints before starting the optimization process to see in what manner the runtime is affected.

  • Actually the runtime is reduced by this approach in a significant amount. And as more constraints you add the faster the problem is solved.
  • I used constraints where I assumed that they would be added anyway in the iteration process. (separators which separate sets of vertices and the root)
  • One thing which could be observed was that the runtime shows a correlation between the number of constraints which still had to be added in the iteration process and the runtime.
  • But the ASP version was still a lot faster.

• I also implemented another type of inequalities to induce connectivity. Unfortunately this type of inequalites does not induce connectivity on graphs that are not acyclic. So they can not be used without the other inequalities. When used together the runtime is not reduced.

• I documented my observations via screenshots and wrote them into a table.

thesis

• I wrote a paragraph which introduces ILP

literature

• I read following paper where I had taken the indegree inqualities from: On imposing connectivity constraints in integer programs
  • This paper references several other papers which deal with the topic. So I've also read the following An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets. But they also used the vertex-separator constraints and a lazy approach.
  • Their results quite good. So I guess it also makes sense to make some research how the graphs they used "looked like" and what characteristics they had that our graphs not have.

Week 3

Python

runtime

• I found a bug in my implementation where vertex separators between connected subsets and the root where added
  • I added some of the separators redundantly instead of adding different separators
  • So I tried to fix this bug. If too many different separators are added beforehand the runtime increases again.
  • And for whatever reason it seems like adding separators redundantly improves the runtime. I tried a different method where from the same set of separators, those separators where either added redundantly or separately. In the case where they were added redundantly the runtime was significantly better.

thesis

• I wrote two paragraphs.
  • The first about the methods and definitions used in the thesis.
  • The second about the ILP-Models used and the implementation.

literature

• I read through Solving the Maximum-Weight Connected Subgraph Problem to Optimality to understand the connectivity constraints used here.