Introducton

• State which problem you are working on and which system you are using to solve it.
• Define the problem that you are solving precisely. Say clearly whether your formulation of the problem is exactly the same as either the one in my notes or the one on the original competition web page, and if not what the differences are. Also, if there is something ambiguous in the specifications you were given, say how you resolved it.

Specification

• Give a clear description of your vocabulary (i.e., all the data objects used in your specification: relation symbols, arrays, constant symbols, variables, etc.). Say, for each one, what it is used for (e.g., "hold the set U" or "represents a map from A to B", etc.).
• Give your actual specification.
• Give a description of what each constraint or formula does: What property does it define; how does it do that (if it is not obvious); if defining the property involves a combination of formulas, say how they relate. You can do this in text before or after the specification, or you interleave text and parts of the specification (as it's done in the course notes).

Testing

Empirical Performance Study

How does the run time change as a function of instance size? Notice that this sounds simple: Make instances of different sizes, and plot how runtime changes as a function of size. However, it can be tricky. For one thing, it may be unclear what the best measure of size is. For another, since different instances of the same size can have very different solving times, to see how size affects run-time, you need to try to come with of instances of different sizes that are in some sense ``the same'' except for being of different sizes.
1. Which is the best way to express a constraint? There is often more than one reasonable way to express a particular constraint on the solutions in a particular language, and sometimes these choices can have a very large effect on running time. You can compare performance with different versions of one constraint, or compare two very different specifications.
2. Does adding a redundant constraint help? A constraint C is redundant for a specification S if adding C to S does not change the set of solutions that is defined. Sometimes adding redundant constraints to a specification can have a large effect on solving time. When there is more than one way to express a property in a language, sometimes including constraints that express it both ways gives better performance than either one by itself. Also, sometimes a solutions have some property which follows logically from the problem definition, but not expressed explicitly in a specification. Adding a constraint enforcing such a property can sometimes improve solving times.
3. Which solver is better for this problem? Different solvers may have very different performance on particular collections of instances of problems. If you can write a correct specification for more than one of the systems, you can compare the performance of the different systems.
4. What is the best way to do optimization? The systems can be used to solve an optimization problem by giving the function to optimize, so the system searches for an optimum solution, or by solving the decision problems for several different values of the cost bound, searching yourself for the optimum. The performance could be quite different. Also, as you vary the cost bound K for a particular instance, the running time may change in an interesting way.

1. What question you tried to answer.
2. How you tried to answer it: What instances or specifications did you use, and why. What did you measure?
3. The conditions (which solver, which computer, etc);
4. A representation as a table, plot, etc., of the outcome.

Discussion

Data