The output file contains the following five sections that appear in the order shown:
a) Objective Value Section
it is made of a single line that contains the value of the best cut found by the algorithm. In parentheses the indication whether this cut was proven to be optimal or not. In the latter case the percentage of the gap (UPPER BOUND – cut value) over the cut value is given.
b) Bound Section
it is made of a single line containing the UPPER BOUND, i.e., a mathematically proven value that cannot be exceeded by the weight of the optimal cut. The UPPER BOUND is used to provide a certified quality of the cut found by the algorithm.
c) Execution Time Section
it is made of a single line giving the total execution time in seconds in a Pentium IV running at 3.6 GHz with 2Gb memory.
d) Partition Size Section
It is made of a single line where the size of the smaller of the two partitions associated with the best-found cut is given, along with the total number of nodes.
e) Partition Section
It is made of a single line containing the list of the nodes belonging to the partition described in the previous section.