Advanced Algorithms example questions on empirical evaluation

acknowledgements.md

The following people contributed with answers

• @Kaalamaazoo

Question 1.md

Give a description of the DPL algorithm for SAT as analysed by Hooker and Vinay.

The DPLL algorithms works with the following steps:

1. Monotone variable fixing: This means that all variables which appear only in a positive form (no negated terms) are set to true and all variables which appear only in a negative form are set to false.
2. Unit resolution: In this step all unit clauses (which are clauses with only one remaining literal) are set to true (hence the variable within may be true or false, depending on the negation). Consequently the value of the literal is propagated trough the formula. The formula can then be shortened (if L is true, remove the clause; if L is false, remove L from the clause). A contradiction may appear here if L appears once negated and once positive. This branch is then not satisfiable and terminates
3. If the algorithms was not stopped in step 2 a check is made to verify is S is empty. If yes return "Satisfiable"; otherwise continue with step 4
4. Pick a new literal L and branch either on L or not-L

Question 10.md

Studying algorithm performance on a set of benchmark instances is open to the criticism that these instances may not be representative. How does Hooker propose we respond to this criticism? Explain how this sidesteps the criticism.

The main issue is that algorithms may become "overfitted" to certain problems. This severely limits the applicability of the algorithm.

Hooker proposes to divide the problems into several problem classes, each with an specific characteristic. The instances should then be varied along these paramaters.

Question 11.md

Which three "modes of experimentation" does McGeoch identify?

• Dependency study: In this study the functional relation between paramter settings and performance measurements is analyzed.
• Robustness study: Here one tries to examine the deviation of the average and what the performance range is.
• Probing studies: The simulation problem is opened to inserrt probes and inspect the inner workings of an algorithm.

Question 12.md

At one point in her study of the FFD algorithm, McGeoch proposes “a new hypothesis: Most of the empty space in a packing will be found in bins containing surplus heavy weights, which are packed one-to-a-bin.” How does she test this prediction?

Experiment 1: 25 random trails each at the design points n = 1000, 2000, .. , 128000. Results in graphs of Packing ratio against N and empty space against N.

Hypothesis 1: The experiment results in the question, Why should empty space grow approximately as square-root n. It is hypothesized that the empty space S reflects some random noise due solely to random variation in individual weights.

Experiment 2: If hypothesis 1 were true then variations in observed empty space would not be correlated with variations in say, the total weight of the weights. So to test this, 1000 random trails are done at design point n = 128000. The resulting graph shows that there is a relation between the total weight and the variations in empty space!

Hypothesis 2: Most of the empty space in a packing will be found in bins containing surplus heavy weights, which are packed one-to-a-bin.

Experiment 3: To investigate hypothesis 2 look at the breakdown of empty space by number of weights per bin. Let a gap be the amount of empty space in a single bin. This results in a table which shows how gaps are distributed according to counts of weights per bin in one trail at n = 128000. From this table it shows that hypothesis 2 fails, most empty space is in bins with 2 weights.

Experiment 4: It is obvious that the next step is to focus on how weights get paired. To that end McGeoch makes a plot of every bin and its weight of a trail at n = 1000. This can be used for a new Hypothesis. But isnt.

Question 2.md

Give a description of the GSAT algorithm for SAT as analysed by Gent and Walsh.

GSAT is a random hill climbing algorithms.

1. First give a random truth assignment to the variables
2. For this truth assignment a literal is flipped. The literal which is flipped is chosen such that this will increase the number of satisfied clauses the most. In case of a tie, this is broken arbitrarily.
3. If the score cannot increase any more a "backflip" is done. This literal is chosen such that it unsatisfies the lowest number of previously satisfied clauses.

The algorithms can become stuck in a local optimum and is not complete. Hence it may not find the best solution. If it does not find a solution, it can be restarted such that the values in step 1 are different and a new solution may be possible.

Question 3.md

Give a description of the FFD algorithm for Bin Packing as analyzed by McGeoch.

First the items are sorted in the decreasing order of their sizes (largest first). Then they are fitted in the first bin where they can be placed. If the item does not fit into any bin, it is placed in a new bin.

The algorithms has complexity O(n^2) and an approximation ratio of 5/3

Question 4.md

Give a description of the 2-approximation algorithm for Minimum Vertex Cover as analyzed by Gomes et al.

This algorithm is sometimes referred to as "Greedy".

1. Start with a empty set S
2. While there are edges remaining in the original graph G, pick one arbitrarily. From this edge, put both vertices in the set S.
3. Remove all adjacent edges from those two vertices from graph G.
4. Continue at step 2 if possible
5. Return S

Question 5.md

Describe what an empirical and a mechanistic model look like.

An empirical model is based on observations. It comes doen to observations of the output (or reaction) of a system. These observations lead to a model which can extrapolate on this. The system is therefore considered as a black box. (Use the following example: you can observe ocean tides for over a year and then predict which tide it will be based on these observations. However you do not know anything about the connection of the Earth, Sun and the moon with the tide).

A mechanistic model is bases on subsystems which are small enough to be understood. The relation between these systems can also be understood. Using this knowledge, a matematical model can be derived.

Question 6.md

Which of these two (empirical or mechanistic) is the model Hooker and Vinay use to explain the behavior of Jeroslow and Wang’s branching rule, based on the Satisfaction hypothesis? Explain your answer.

They use the empirical approach. Their explanarions are based on the results they heve obtained in their experiments. The inner working of the algorithm is not considered, but the data drives the conclusions

Question 7.md

Which two "steps in the right direction" (toward an empirical science of algorithm) does Hooker identify?

1. Statistical methods to interpret the results from experimentation. This allows for evaluation of test results to conclude the behaviour of an algorithm.
2. Heuristic use of experimentation

Question 8.md

Explain what it means to make "heuristic use of experimentation", as Hooker describes it.

Suggest hypotheses on the behaviour of algorithms based on experiments which were performed.

Question 9.md

Which of the three studies (1) on branching rules for SAT by Hooker and Vinay, (2) on the FFD algorithm for Bin Packing by McGeoch, and (3) on GSAT by Gent and Walsh does not apply "heuristic use of experimentation", as Hooker describes it in his paper? Explain how the other two studies apply experimentation in this way.

First we look at what "heuristic use of experimentation is". This is defined as suggest hypotheses on the behaviour of algorithms based on experiments which were performed.

We know that this was used extensively in the paper of Hooker and Vinay (Satisfaction hypothesis for example). The Bin Packing paper by McGeoch also uses it, when she formalizes her hypothesis on the bins where space is wasted.

The paper not using this approach is the paper by Gent and Walsh. Although they use experiments, they do not formalize hypotheses based on this experiment.