description of the graph bisection program


the program bisect.f finds both a good equipartition of
a given graph and a bound of the optimum value of this partition.

the program consists of two files: bisect.f subs.f

in bisect.f you will find the main program + a bunch of subroutines
that were written by J. Falkner and F. Rendl.
the second file subs.f contains software from third parties that we
use essentially as black boxes. specifically it includes the
BT code plus the necessary subroutines and DNLASO plus the necessary
subroutines. we have slightly modified these codes to allow
some communication between the different subroutines.

we also include a third file trnsform.f which you may find useful.
it takes the adjacency list of a graph (contained in some file) and
transforms it into a format suitable for the bisection routine.

the bisection routine asks for a filename that contains the graph
in the correct format, and then uses an automatic parameter setup
tostart the calculations.

here is a description of the correct format for the input.
first comes:

n nzl nzs

(these are three integers with the following meaning:
n ... number of nodes
nzl ... number of the last row where there is a nonzero entry in the
	upper triangle of the adjacency matrix. this will at the same
	time be the dimension of the following vector icol. so, if you
	set nzl to n-1, you have to fill up the vector icol with 
	sufficiently many zeros.
nzs ... number of nonzeros in the upper triangle of the adjacency matrix
	i.e. number of edges)

next comes an integer vector of size nzl:

icol(1),... icol(nzl)

(icol(j) indicates the number of nonzero entries in row j of the
upper triangle of the adjacency matrix. icol(j)=0 is possible.)

finally comes the list of the actual edges: this is a list of length
nzs, where in each line is of the form

columnindex weight

(the edges are read in a rowwise fashion, only the upper triangle.
the array icol tells us how many edges we will find in the row,
the columnindex tells me in which column the entry must lie. the weight
is arbitrary (double precision).

this may be nonstandard, but it is the most economical way we could think
of storing the graph. tho order in which the nonzeros appear in a fixed row
is not important. so the columnindex need not be sorted within a row.


After successful execution the program just displays the 
value value of the bound and the best bisection found. if you want to
actually store the cut vector, you have to include this in the
program. if you check the code, you will see that we have included a final
write, but it is silenced out.

If you are lazy, and your graph has just weights one (i.e. is unweighted)
then you can just use the routine trnsform.f. it sets the adjacency list
into the right format and writes it onto a file.


now some final comments regarding the performance.
we have set the dimensions as follows:
 

max number of nodes = 5000
max number of edges = 30000

if you need more, you have to hack the code. we indicated the places,
where the parameter changes have to be made. (only in bisect.f, it is 
on 5 or 6 spots.)

max number of bt - iterations = 15 

if you need more set the variable MAXIT in the main program appropriately.

finally the parameter FACTR in the main program plays a crucial role
in setting up the initial parameters for bt. we have set the choice of
FACTR automatic. this should work for a large variety of problems. Here
is some bit of adcice. if your graph is very sparse, FACTR should be very
close to 1, i.e. FACTR = .95 or even .99 setting it to exactly 1 may be
not so good, if the graph is only weakly connected. on the other hand,
if the graph is not supersparse, ie, if the number of edges is say larger
than 5n, FACTR should be chosen smaller, e.g. FACTR = .7.
for dense graphs, (edges > 10n) we would propose to set FACTR less than .5

The output that you see on the screen from the bt code includes the bound
the current best cut, the gap, the last two coluumns are the norm of an
epsilon -subgradient found at the current iteration, and the radius of the
current trust region. 

If your initial subgradient norm is quite large, you probably should 
chose FACTR differently, either smaller or larger, depending on where you
are.

Finally, we give this code away for free, so we do not take any 
liability or other  reponsibility.
If you have comments or problems, let us know.


Waterloo, July 26, 1994			franz rendl