progress.md 4.12 KB
Newer Older
msurl's avatar
msurl committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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. 

msurl's avatar
msurl committed
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# 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 wrote 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.