122 lines
4.0 KiB
Markdown
122 lines
4.0 KiB
Markdown
# Assignment 1
|
|
|
|
## Part A
|
|
### clingo
|
|
```shell
|
|
clingo tsp.lp
|
|
```
|
|
| size | ans | time |
|
|
| ---- | ------- | ----------------- |
|
|
| 5 | 38 | 0.001 |
|
|
| 10 | 48 | 0.050 |
|
|
| 15 | 29 | 0.351 |
|
|
| 20 | unknown | too long to solve |
|
|
|
|
time grows exponentialy.
|
|
|
|
### swi-prolog
|
|
|
|
| size | ans | time |
|
|
| ---- | ------- | ----------------- |
|
|
| 5 | 38 | very fast |
|
|
| 10 | 48 | 10+s |
|
|
| 15 | unknow | too long to solve |
|
|
| 20 | unknown | too long to solve |
|
|
|
|
I didn't find a way to calculate runtime in swi-prolog. But it is clearly to see that it is way slower than clingo.
|
|
|
|
|
|
### Google OR-Tools
|
|
|
|
1. Local Optimum
|
|
|
|
| size | ans | time |
|
|
| ---- | --- | ------ |
|
|
| 5 | 38 | 0.0077 |
|
|
| 10 | 48 | 0.0085 |
|
|
| 15 | 37 | 0.009 |
|
|
| 20 | 48 | 0.010 |
|
|
|
|
2. Global Optimum
|
|
|
|
| size | ans | time |
|
|
| ---- | --- | ------------------- |
|
|
| 5 | 38 | time limit exceeded |
|
|
| 10 | 48 | time limit exceeded |
|
|
| 15 | 29 | time limit exceeded |
|
|
| 20 | 46 | time limit exceeded |
|
|
|
|
It is great to have two different mode. Though the approximate result is not as good as the exact one. But it is way faster and uses way less resource. We can switch between different mode at different case.
|
|
|
|
### AMPL
|
|
| size | ans | time |
|
|
| ---- | --- | --------- |
|
|
| 5 | 38 | very fast |
|
|
| 10 | 48 | very fast |
|
|
| 15 | 29 | very fast |
|
|
| 20 | 46 | very fast |
|
|
|
|
Very fast.
|
|
|
|
## Part B
|
|
### clingo
|
|
```shell
|
|
clingo task.lp
|
|
```
|
|
|
|
| size | processors | deadline | result | time |
|
|
| ---- | ---------- | -------- | ------- | ----------------- |
|
|
| 10 | 3 | 20 | yes | 0.031 |
|
|
| 20 | 6 | 30 | no | 4.498 |
|
|
| 20 | 8 | 30 | yes | 0.233 |
|
|
| 30 | 6 | 60 | unknown | too long to solve |
|
|
| 30 | 8 | 60 | yes | 2.961 |
|
|
| 30 | 8 | 80 | yes | 6.701 |
|
|
| 30 | 8 | 90 | yes | 9.245 |
|
|
|
|
With either too high or too low constrain, the runtime grows exponentially. If the constrain is too low, it must iterate through all answers to find one correct result. If it is too high, then it may waste too much time fill the first processor.
|
|
|
|
### Google OR-Tools
|
|
| size | processors | deadline | result | time |
|
|
| ---- | ---------- | -------- | ------ | ------ |
|
|
| 10 | 3 | 20 | yes | 0.035 |
|
|
| 20 | 6 | 30 | no | 0.037 |
|
|
| 20 | 8 | 30 | yes | 0.0474 |
|
|
| 30 | 6 | 60 | no | 0.0413 |
|
|
| 30 | 8 | 60 | yes | 0.0469 |
|
|
| 30 | 8 | 80 | yes | 0.0481 |
|
|
| 30 | 8 | 90 | yes | 0.0552 |
|
|
|
|
Unlike clingo, Google OR-Tools is much faster on this question. And too high/low constrain does not increase the run time by a lot.
|
|
|
|
## Part C
|
|
### clingo
|
|
```shell
|
|
clingo cut.lp
|
|
```
|
|
| size | ans | time |
|
|
| ---- | --- | ------ |
|
|
| 5 | 5 | 0.678 |
|
|
| 10 | 9 | 0.866 |
|
|
| 15 | 13 | 1.122 |
|
|
| 20 | 17 | 1.902 |
|
|
| 25 | 21 | 6.379 |
|
|
| 30 | 25 | 34.466 |
|
|
|
|
One important factor of the runtime is the max number of cut to check. If we set max = 10 with size = 30, we get the time of 0.914. However, it is impossible to get the max size before running, I believe this time would be a great representation of the runtime of clingo.
|
|
|
|
### AMPL
|
|
| size | ans | time |
|
|
| ------ | ----- | --------- |
|
|
| 5 | 5 | very fast |
|
|
| 10 | 9 | very fast |
|
|
| 15 | 13 | very fast |
|
|
| 20 | 17 | very fast |
|
|
| 25 | 21 | very fast |
|
|
| 30 | 25 | very fast |
|
|
| 100000 | 80393 | very fast |
|
|
|
|
Very fast.
|
|
|
|
## Conclusion
|
|
AMPL is the fastest implementation in part 1 and 3, much faster than the others. clingo is the clearest and the easiest way to write it but it is not that fastest one. Each language has its own pros and cons so it is hard to create a single language with all the pros but no cons. |