[Zurück]

P. Schüller:
"Reconstructing borders of manually torn paper scheets using integer linear programming";
Betreuer/in(nen): G. Raidl, M. Prandtstetter; Institut für Computergraphik und Algorithmen, 2008; Abschlussprüfung: 01/2008.

This thesis discusses the destruction of sheets of paper by manual tearing and evaluates two
approaches for reconstruction of such pages by exact methods based on Integer Linear Programming.
These methods operate solely on the shape of torn pieces of paper and reconstruct
the borders of the paper sheets.
For evaluation and tests within this problem domain, a tearing model of human paper tearing
as well as a C++ library and an XML data interchange format were developed. The tearing
simulation takes into regard shear effects which distort paper in a way that-opposed to
cutting-the shapes of adjacent pieces will not prefectly fit together anymore.
The ILP formulations were evaluated with extensive empirical tests using the CPLEX solver software.
The performance and accuracy of several objective functions was compared, in particular
functions using the CPLEX specific IloAbs absolute value calculation feature and formulations
not using this feature. Further evaluation was performed on the very performance-relevant
CPLEX parameters MIPEmphasis and on the CPLEX specific lazy constraints.
The developed library and tools were very useful for the evaluation in this problem domain and
can be reused for further studies. The ILP models are fast and yield good accuracy results on
single page instance sizes which makes them well suitable for usage in hybrid algorithms.