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
programming FAQ.

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.

Q: What do you mean by

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.