Project Instructions

For the project, you are to study using declarative solving tools to solve instances of some application problem. The goal of the project is to learn something about declartive problem solving in practice by learning about and using the tools. The project has two main parts. For Part I, you are to select a problem and at least two solvers or solving methods, and test correctness these methods. For the second, the focus is on improvement and/or evaluation of the solving methods. The exact nature of this work will depend on the particular problem you choose, and what has already been done or is already known or available about it. The choice of problem and the focus of the second part must be discussed with the instructor.

Part I

  1. Choose a problem to work on. This can be any problem for which there are not good polytime algorithms, and which can be represented in the MiniZinc or IDP specification languages. The problem you choose can be an application problem that is of interest to you, or it can be taken from a number of sources including: If you want to choose a problem of your own, it needs to be a problem that is primarily combinatorial in nature. That means, funding a solution amounts primarily to making a collection of decisions about discrete values or objects. (Problems that are primarily numerical in nature, involving complex real-valued functions, for example, are less appropriate for the tools we are using here.)
  2. Choose a specification-based solver from the following: Spend some time looking at the tutorial or manual of each solver, and some sample problem specifications, to see which one you are most comfortable with.
  3. Choose another solving method. This can be anything you want, including one of the other solvers from the list above, some other solver you find, some method you invent yourself, etc.
  4. Create solutions using both solving methods, and demonstrate their correctness by applying them to a selection of test instances. You should have an absolute minimum of 10 test instances (half satisfiable and half unsatisfiable), but 20 or more would be more reasonable. What is involved in this step will vary greatly depending on your choice of problem and solvers. In some cases, it will be straightforward because specifications and a collection of test instances can already be found online for your problem and solver choices. In other cases, you may have to write two problem specifications and come up with test instances yourself. (The amount of work you are required to do for Part 2 will depend in part on how much work is needed for Part 1.)

Part II

In practice, sometimes the work is done once a correct specification is obtained, because the solver performance with that specification is good enough for the problem instances that need to be solved. In many other cases, there is a desire to solve very hard instances, or many instances that have not been seen yet, and in this case the work has just begun. The challenge then is to try to obtain better solver performance. To obtain better performance, you need to evaluate the performance, and this itself is a difficult problem.

For Part II of the project, you are to explore some aspect of declarative problem solving, related to solver performance and performance evaluation, using your solutions for Part I as a starting point. This means you should consider some idea about the specification and solving process, ask a question about that idea, carry out an investigation, and write a report about it. Some examples include:

  1. When deciding how to represent a problem, there are several options, and the choice may affect both how we go about writing a specification (and how hard it is to do so), and the performance of various solvers. For example, in solving the (traditional) N-Queens problem, we are asked to arrange n queens on an n-by-n chessboard. We could represent the positioning of the queens on the board by a 2-D array. But we could also observe that there must be a queen in every row, and use a 1-D array in which A[i] is the column in which the i-th queen is placed. Dually, we could have A[i] be the row in which the i-th queen is place. We could even include more than one of these. These choices all lead to different specifications.
  2. When writing a specification, for any given property of solutions to your problem, there are many possible ways of representing the property in the language of a given solver. You may explore different choices, giving consideration to how easy they are to get correct, how clear their meaning is, and especially how they might affect solver performance. Also, you can include redudant constraints, that is constraints which correctly describe properties of the solution but which are not necessary for your specification to be correct. For example, we looked at the fact that there are a number of natural properties satisfied by Latin Squares, and various sub-sets of these properties make correct specifications. One can include any superset of these and have a correct specifation.
  3. Instances of the problems we are looking at range widely in solving times, even among instances that are of essentially the same size. It is natural and interesting to try to understand whether various properties of instances affect solver performance in a predictable way. Similarly, if some instances are particularly hard (escpecially if we don't see any reason that they should be), it is interesting to see if a change in specification or solver setting can improve performance.

The default way to think about this part of the project is as follows. You want to find the best solution method you can for problem instances that might not exist yet, or might exist but be too hard to solve. So, you want to develope the most promising method. To do this, you need to evaluate the two methods relative to each other, and also try to make improvements to each method. To evaluate them, you need a set of benchmark instances that plausibly would predict the performance of the solvers on the currently unavailable or currently unsolvable instances of interest.

So, for his part, you need to explore benchmark instances and methods of improving your solving methods. Exactly what you need to do will depend on the problem you are working on, and on how much original work you needed to do to complete Part 1 of the project.

Report and Submission

Write a report with three main sections. The first should be a report of Part 1, stating the problem addressed, giving your solution methods, and describing your test instances and results. The second should describe the work carried out for Part 2. The third should be an appendix, which should contain a list of files (with short descriptions) in the folder you submit (this can be the same text as the Readme file), and possibly other things.

The report on Part 1 should:

The description of the work in Part 2 should include:
  1. What question are you exploring? Typically, this will begin with some observation that you made about your problem's specifications, solver performance, problem instances, or the process of writing and using your specification. It may be a question about what makes a good specification, about different solvers or solving techniques, or about properties of problem instances, among other things.
  2. How did you go about trying to answer the question? If you developed alternate specifications or insteresting families of problems instances, describe how you went about that, and in what way your choices in doing that amount to an attempt to answer the question.
  3. Details of your experiments or other investigation. For example, what is your experimental set-up (instances, solver, specification, etc.) and what are you measuring, etc. This part should be the most detailed.
  4. Data or other observations.
  5. Discussion: Did your exploration actually go some way toward answering your question? Did it help you understand something interesting about declarative problem solving? What might you do next, if you wanted to continue this study in the future?
Your submission to Coursys should be a .zip file of the contents of a directory that contains your final report, all the files used in the work that you are reporting, and a Readme file that gives a list of the files in the directory.