90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
- 2021 (21) (remove)
Document Type
- ZIB-Report (13)
- Master's Thesis (5)
- Bachelor's Thesis (2)
- In Proceedings (1)
Language
- English (21)
Keywords
Learning to Use Local Cuts
(2021)
We propose a machine learning approach to address a specific algorithmic question that arises during the solving process of a mixed-integer linear programming problem, namely, whether to use cutting planes only at the root node or also at internal nodes of the branch-and-bound search tree, or equivalently, whether to run a cut-and-branch or rather a branch-and-cut algorithm. Within a supervised regression framework, we develop three machine learning models, Linear Model, Random Forest and Neural Network, for predicting the relative performance between the two methods, local-cut and no-local-cut. Hence, through an extensive computational study conducted with FICO Xpress over a large test bed of problems, we evaluate the produced strategies, and we show that they are able to provide, upon the existing policies, a significant improvement to the performance of the solver.
In fact, a variant of the random forest suggested in the present work has already been implemented by the development team of Xpress, and released with version 8.13 of the software.
We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems.
At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point roundoff errors present in most state-of-the-art solvers for mixed-integer programs.
The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate.
This acts as a safeguard against programming errors that may be present in complex solver software.
The viability of this approach is tested by applying it to finite cases of Chvátal's conjecture, a long-standing open question in extremal combinatorics.
We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant.
As a result we are able to provide a first machine-assisted proof that
Chvátal's conjecture holds for all downsets whose union of sets contains seven elements or less.
Die Planung vom Zugumläufen ist eine der wichtigsten Aufgaben für Eisenbahnun- ternehmen. Dabei spielt auch die Einhaltung von vorgegebenen Wartungsintervallen eine zentrale Rolle für die Sicherheit und Zuverlässigkeit der Schienenfahrzeuge. Wir zeigen, wie man dieses Umlaufplanungsproblem unter Beachtung von Wartungsbe- dingungen mathematisch formuliert, modelliert und löst — sowohl in der Theorie als auch im Anwendungsfall mit Szenarien der DB Fernverkehr AG, einer Konzern- tochter der Deutschen Bahn für den Schienenpersonenfernverkehr.
Markus Reuther hat sich in seiner Dissertation [11] mit diesem Problem beschäftigt und es mit Hilfe eines passenden Hypergraphen als gemischt-ganzzahliges Programm modelliert. Neben der Modellierung präsentiert Reuther in seiner Arbeit neuartige algorithmische Ideen, darunter den sogenannten Coarse-to-Fine -Ansatz, bei dem zunächst Teile des Problems auf einer weniger detaillierten ( coarse ) Ebene gelöst werden und diese Lösung dann verwendet wird, um auf effiziente Art und Weise eine Lösung für das ursprüngliche Problem zu finden. Zur Wartungsplanung nutzt Reuther einen Fluss im Hypergraphen, der den Ressourcenverbrauch der Fahrzeuge modelliert. In der linearen Relaxierung des Modells führt dies dazu, dass die Zahl der notwendigen Wartungen systematisch unterschätzt wird. Dadurch bleibt in vielen Fällen eine große Lücke zwischen dem Zielfunktionswert einer optimalen Lösung des ganzzahligen Problems und der untere Schranke, die uns die lineare Relaxierung liefert.
Wir nehmen uns in dieser Arbeit dieses Problems an. Wir entwickeln ein auf Pfaden basierendes ganzzahliges Modell für das Umlaufplanungsproblem und zeigen, dass die untere Schranke mindestens so scharf oder schärfer ist als die untere Schranke, die das Modell von Reuther liefert. Um das Modell zu lösen, entwickeln wir einen Algorithmus, der Spaltengenerierung mit dem Coarse-to-Fine-Ansatz von Reuther verbindet. Weiterhin entwickeln wir eine Spaltenauswahlregel zur Beschleunigung des Algorithmus. Das Modell und alle in der Arbeit vorgestellten Algorithmen wur- den im Rahmen der Arbeit implementiert und mit Anwendungsszenarien der DB Fernverkehr AG getestet. Unsere Tests zeigen, dass unser Modell für fast alle Szena- rien deutlich schärfere untere Schranken liefert als das Modell von Reuther. In den getesteten Instanzen konnten wir durch die Verbesserung der unteren Schranke bis zu 99% der Optimalitätslücke schließen. In einem Drittel der Fälle konnten wir durch unseren Ansatz auch für das ganzzahlige Programm verbesserte Zielfunktionswerte erreichen
Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants.
For this thesis we study the Constrained Horizontal Flightplanning Problem (CHFPP) for which one has to find the path of minimum cost between airports s and t in a directed graph that respects a set of boolean constraints. To this end we give a survey of three different multilabel algorithms that all use a domination subroutine. We summarize an approach by Knudsen, Chiarandini and Larsen to define this domination and afterwards present our own method which builds on that approach. We suggest different implementation techniques to speed up the computation time, most notably a Reoptimization for an iterative method to solve the problem. Furthermore we implemented the different versions of the algorithm and present statistics on their computation as well as an overview of statistics on the set of real-world constraints that we were given. Finally we present two alternative approaches that tackle the problem, a heuristic with similarities to a Lagrangian relaxation and an approach that makes use of an algorithm which finds the k shortest path of a graph such as the ones of Epstein or Yen.
Scheduling ist ein wichtiger Forschungsgegenstand im Bereich der diskreten Optimierung. Es geht darum, einen Schedule, d.h. einen Ablaufplan, für gegebene Ereignisse zu finden. Dieser soll optimal hinsichtlich einer Zielfunktion wie zum Beispiel minimaler Dauer oder Kosten sein. Dabei gibt es in der Regel Nebenbedingungen wie Vorrangbeziehungen zwischen den Ereignissen oder zeitliche Einschränkungen, die zu erfüllen sind. Falls die Ereignisse periodisch wiederkehren, spricht man von periodischem Scheduling. Beispiele sind das Erstellen von Zugfahrplänen, die Schaltungvon Ampelsignalen oder die Planung von Produktionsabläufen.
Mathematisch können diese Probleme mit dem Periodic Event Scheduling Problem (PESP) modelliert werden, das als gemischt-ganzzahliges Programm formuliert werden kann. In dieser Bachelorarbeit wird ein Ansatz zur Lösung des PESP mittels Zerlegung und Dualisierung entwickelt. In den Kapiteln 2 und 3 werden zunächst die notwendigen graphentheoretischen Grundlagen und das PESP eingeführt. In Kapitel 4 wird das PESP durch Fixierung der ganzzahligen Variablen in lineare Programme zerlegt. Dieses Unterproblem wird dualisiert und wieder in das PESP eingesetzt. Dafür ist eine weitere Nebenbedingung nötig.
Im fünften Kapitel behandeln wir die Lösung des teildualisierten PESP. Eine Möglichkeit ist es, sich auf eine Teilmenge der Nebenbedingungen zu beschränken. Eine weitere Möglichkeit ist ein Algorithmus, derähnlich wie BendersZerlegung die Nebenbedingungen dynamisch erzeugt. Dieser Algorithmus wird in Kapitel 6 implementiert und an vier Beispielen getestet.
We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic
ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem.
Air freight is usually shipped in standardized unit load devices (ULDs).
The planning process for the consolidation of transit cargo from inbound flights or locally emerging shipments into ULDs for outbound flights is called build-up scheduling.
More specifically, outbound ULDs must be assigned a time and a workstation subject to both workstation capacity constraints and the availability of shipments which in turn depends on break-down decisions for incoming ULDs.
ULDs scheduled for the same outbound flight should be built up in temporal and spatial proximity.
This serves both to minimize overhead in transportation times and to allow workers to move freight between ULDs.
We propose to address this requirement by processing ULDs for the same outbound flight in batches.
For the above build-up scheduling problem, we introduce a multi-commodity network design model.
Outbound flights are modeled as commodities; transit cargo is represented by cargo flow volume and unpack and batch decisions are represented as design variables.
The model is solved with standard MIP solvers on a set of benchmark data.
For instances with a limited number of resource conflicts, near-optimal solutions are found in under two hours for a whole week of operations.