Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

Das strukturierte Portfolio zur Dokumentation des orientierenden Praktikums für Lehramtsstudierende

Die Kompetenzorientierung der Lehrerbildung bezieht sich nicht nur auf die universitären Ausbildungsabschnitte des Lehramtsstudiums, sondern auch auf die praktischen Phasen. Daher ist es von Interesse, diese praktischen Phasen genauer zu untersuchen. Bisherige Forschungsarbeiten konzentrierten sich dabei vor allem auf die Kompetenzentwicklung (Bach, 2013; Gröschner & Schmitt, 2012; Schubarth et al., 2012) und auf die Betreuung im Schulpraktikum (Bach, 2013; Hascher, 2012; Schubarth et al., 2011). Die Untersuchung dieser Arbeit stellt die Praktikumsdokumentation in den Fokus, da diese ebenfalls zur Kompetenzförderung im Schulpraktikum beitragen kann. Dazu werden zwei Formen von Praktikumsdokumentationen gegenübergestellt. Dies sind einerseits die Praktikumsaufgaben, die als offene Reflexionsaufgaben formuliert werden und andererseits ein strukturiertes Arbeitsheft mit dem Ziel, die Beobachtungskompetenz der Studierenden anzuleiten und die Dokumentation der Beobachtungen zu strukturieren. Diese beiden Formen der Praktikumsdokumentation werden hinsichtlich der Akzeptanz, der Entwicklung der Kompetenzen, der Selbstwirksamkeitserwartung und des pädagogisch-psychologischen Wissens miteinander verglichen. Die Angaben von n = 66 Studierenden, die das Arbeitsheft im Orientierenden Praktikum nutzten, wurden in einem prä-post-follow-up-Design untersucht und zwei Referenzgruppen gegenübergestellt. Die erste Referenzgruppe (n = 64) hatte das Orientierende Schulpraktikum noch nicht absolviert. Die zweite Referenzgruppe (n = 105) hatte dieses beendet und mit den Praktikumsaufgaben gearbeitet. Mit Hilfe von Online-Fragebögen wurden Daten zu Rahmenbedingungen des Schulpraktikums, die selbsteingeschätzte Kompetenz der Studierenden, die Relevanz und Anwendungshäufigkeit der Kompetenzen (adaptierte Skala nach Gröschner, 2009), die allgemeine Selbstwirksamkeitserwartung (Jerusalem & Schwarzer, 1999), das pädagogisch-psychologische Wissen sowie die Akzeptanz erfasst. Die Ergebnisse zeigen keine Unterschiede in der Kompetenz- und Relevanzeinschätzung sowie bei der Selbstwirksamkeitserwartung und dem Wissen zwischen den Gruppen. Signifikant besser schätzten die Studierenden mit dem Arbeitsheft die Anwendungshäufigkeit der Kompetenzen und die Akzeptanz der Praktikumsdokumentation ein. Das neu entwickelte Arbeitsheft und die Praktikumsaufgaben fördern die Kompetenzentwicklung wahrscheinlich in vergleichbarem Maß. Die Studierenden akzeptieren das Arbeitsheft jedoch mehr, was eine wichtige Implementationsbedingung ist. Das Design der Studie sowie die Selbstselektion der Gruppen schränken die Aussagekraft der Studie ein. Zu betonen ist jedoch, dass im Rahmen dieser Studie erstmalig versucht wurde, eine längsschnittliche Interventionsstudie mit Praktikumsdokumentationen umzusetzen sowie die Gelingensbedingungen von Schulpraktika und Kompetenzentwicklung im Lehramtsstudium zu untersuchen.