This file contains tips and answers to frequently asked question concerning the COMP670J project. It will be updated frequently in response to your questions so I suggest that, at least for the first week or so, you check it every few days for additions.
LAST UPDATE: Mon Dec 3 11:15:14 HKT 2001
Another place to look is here
which has links to an object-oriented simplex library. This looks
more complicated to use than the Numerical Recipes code, though.
Yet another place to look is the linear
You can also check out this code. It contains code for a weighted matching solver (it solves for max weighted matching but you can easily use this for min matching by negating the edge costs). I haven't tested it myself but it looks as if it should be useful for you. One warning; you'll have to compile a package.
For this project you should be aware that even though
the algorithm is not difficult the paper is not that easy to read;
it will occasionally skip steps that you have to fill in for yourselves.
If you are doing this project and are having difficulty with the paper
please come and see me and we can work through the bottlenecks.
A: You should send me two things.
(i) for each set of parameters describe how you will generate the random data for the set of parameters.
Please address any issues that you considered when choosing this data generation method, e.g., how
well the data will test the approximation algorithm.
As an example, in Max-Sat the parameters
are m = number of variables and n = number of clauses.
In this case you need to describe how for any given (m,n) you will generate a random instance.
An issue that you need to consider here is how to choose the number of variables in a particular
clause. If, for example, you let every clause have greater than 8 variables then, from the analaysis in the notes, we see that every clause has probability > .99 of being satsified. So, taking instances with clauses of length > 8 will not really test the differences between the random algorithm and best-of-two very well; you need to somehow guarantee many short clauses. In particular, the strategy of letting a variable have 50% probability of appearing in each clause is not a good generation method if the number of variable is > 16 or so. Max-Sat is is just an example, many of the projects have similar considerations.
(ii) After describing how you will generate a random data
set for a particular set of parameters you will need to also specify for
what values of the parameters you will generate the data sets and,
how many times for each set of parameters (I recommend at least 10).
As an example, in Max-Sat you might
decide to let m=3, 6, 9, 12 15, 25, 30 n = 5, 10, 15, 20, 25,30, 35, 40, 45, 50, 55, 60 and, for each,
(m,n) pair, generate 10 random instances.
If, after writing your code you find that
for some reson you want to run it on more datasets, that
would be fine; if you want to not run it on some of the data sets you describe then,in your report, you will need to explain why, e.g., you did not realize in advance the limitations of the LP code that you would be using.