Linear and Integer Programming (ADM II)

TU Berlin/BMS, WS 2007/2008

Programming exercise 2

Here is the exercise again.

Program presentation schedule

Day	Time	Group
Tue	16:00	`lop-107`
	16:30	`lop-109`
	17:00
	17:30

Day	Time	Group
Wed	12:00	`lop-101`
		`lop-117`
	12:30	`lop-115`
		`lop-116`
	13:00	`lop-103`

	13:30	`lop-121`

Day	Time	Group
Wed	16:00	`lop-108`

	16:30

	17:00

	17:30	`lop-113`

Day	Time	Group
Thu	16:00	`lop-119`
		`lop-111`
	16:30	`lop-106`
		`lop-104`
	17:00	`lop-102`
		`lop-114`
	17:30	`lop-120`

Parser for `.nwk` files

The java parser for .nwk files improved, with added methods for displaying: NetworkIO.java ...and the documentation.
Bug reports (still) to awerner@math.tu-berlin.de.

Test files

The test files each describe one network.

First line contains the total number of nodes.
Each further line contains the complete description of one node (plus possibly whitespaces) in the following form:

node data (entries separated by commas):
- number of the node (starting from 0)
- planar coordinates of the node (in parantheses)
- in-flow for the node (positive for in-, negative for out-flow) [optional, 0 if omitted]
one colon
list of out-edges of the node (separated by semicolons), each entry containing (separated by commas):
- number of the target node
- cost of the edge (integer)
- capacity of the edge (integer) [optional, ∞ if omitted]

Here is an example (small.nwk):

File	Nodes	Arcs	Optimum
`small.nwk`	5	8	37014
`beispiel.nwk`	5	8	550
`petersen.nwk`	10	15	-51100
`triangular.nwk`	21	59	336400
`shortestpath.nwk`	21	59	861
`rand50.nwk`	50	137	1124371
`rand150.nwk`	150	424	818507
`randinf.nwk`	150	424	infeasible
`randunb.nwk`	150	424	unbounded
`ger1.nwk`	185	708	90651
`stndrd3.nwk`	200	2000	159442947
`transp9.nwk`	400	10000	158058350
`cap2.nwk`	1000	30000	1032822638
`hu.nwk`	5500	39986	19291319

NOTE: Some of the examples contain antiparallel arcs, i.e. between some nodes edges in both directions are present. This is no problem from a theoretical viewpoint, but in the implementation you should be aware that the tree corresponding to a basic solution uses only one of both arcs and has to know which one!
An elegant way to remedy this problem is to introduce an artificial node on one of the two edges to distinguish between two antiparallel arcs; alternatively one can modify the algorithms and data structures for handling tree solutions.

Linear and Integer Programming (ADM II)

Programming exercise 2

Program presentation schedule

Parser for .nwk files

Test files

Parser for `.nwk` files