Eine Heuristik zur Lösung ganzzahliger Programme mit quadratischen Nebenbedingungen

A heuristic for the solution of integer programs with quadratic constraints

  • Die Frage nach dem Lösen von ganzzahligen Programmen mit quadratischen Nebenbedingungen spielt beim Aufbau multistatischer Sonar-Netze eine Rolle. Hierbei werden Schall-Sender und -Empfänger in einem Ozeanabschnitt so platziert, dass möglichst jeder Bereich durch mindestens ein Sender-Empfänger-Paar überwacht werden kann. Diskretisiert man den Abschnitt räumlich, so kann die Frage nach der Platzierung durch binäre Entscheidungsvariablen beschrieben werden. Da es auf die paarweise Platzierung ankommt, werden in den Modellen die Binärvariablen multipliziert, was einem logischen „Und“ entspricht. Um die Modelle halbwegs schnell numerisch zu lösen, wurden in der Literatur zahlreiche Linearisierungstechniken entwickelt und erprobt. Trotz allem Fortschritt ist man weit davon entfernt, Instanzen mit deutlich mehr als 100 Diskretisierungspunkten in annehmbarer Zeit zur Optimalität zu lösen. In dieser Bachelorarbeit werden heuristische Lösungsverfahren entwickelt, welche in der Lage sind, innerhalb kürzester Zeit gute (aber nicht beweisbarDie Frage nach dem Lösen von ganzzahligen Programmen mit quadratischen Nebenbedingungen spielt beim Aufbau multistatischer Sonar-Netze eine Rolle. Hierbei werden Schall-Sender und -Empfänger in einem Ozeanabschnitt so platziert, dass möglichst jeder Bereich durch mindestens ein Sender-Empfänger-Paar überwacht werden kann. Diskretisiert man den Abschnitt räumlich, so kann die Frage nach der Platzierung durch binäre Entscheidungsvariablen beschrieben werden. Da es auf die paarweise Platzierung ankommt, werden in den Modellen die Binärvariablen multipliziert, was einem logischen „Und“ entspricht. Um die Modelle halbwegs schnell numerisch zu lösen, wurden in der Literatur zahlreiche Linearisierungstechniken entwickelt und erprobt. Trotz allem Fortschritt ist man weit davon entfernt, Instanzen mit deutlich mehr als 100 Diskretisierungspunkten in annehmbarer Zeit zur Optimalität zu lösen. In dieser Bachelorarbeit werden heuristische Lösungsverfahren entwickelt, welche in der Lage sind, innerhalb kürzester Zeit gute (aber nicht beweisbar optimale) Lösungen zu liefern. Ausgangspunkt war die Grundidee, Sender und Empfänger abwechselnd zu optimieren, bis keine weitere Verbesserung mehr eintritt. Numerische Ergebnisse werden anhand von Testinstanzen präsentiert und mit einem exakten Ansatz verglichen.show moreshow less
  • The question of solving integer programs with quadratic constraints plays a role when setting up multistatic sonar networks. Sound transmitters and receivers are placed in an ocean section in such a way that, if possible, every area can be monitored by at least one transmitter-receiver pair. If the section is discretized spatially, the question of placement can be described by binary decision variables. Since it depends on the placement in pairs, the binary variables are multiplied in the models, which corresponds to a logical "And". In order to numerically solve the models reasonably quickly, numerous linearization techniques have been developed and tested in the literature. Despite all the progress, one is far from solving instances with significantly more than 100 discretization points in a reasonable time to optimality. In this bachelor thesis, heuristic solution methods are developed, which are able to deliver good (but not provable optimal) solutions within a very short time. The starting point was the basic idea of alternatelyThe question of solving integer programs with quadratic constraints plays a role when setting up multistatic sonar networks. Sound transmitters and receivers are placed in an ocean section in such a way that, if possible, every area can be monitored by at least one transmitter-receiver pair. If the section is discretized spatially, the question of placement can be described by binary decision variables. Since it depends on the placement in pairs, the binary variables are multiplied in the models, which corresponds to a logical "And". In order to numerically solve the models reasonably quickly, numerous linearization techniques have been developed and tested in the literature. Despite all the progress, one is far from solving instances with significantly more than 100 discretization points in a reasonable time to optimality. In this bachelor thesis, heuristic solution methods are developed, which are able to deliver good (but not provable optimal) solutions within a very short time. The starting point was the basic idea of alternately optimizing the transmitter and receiver until there was no further improvement. Numerical results are presented using test instances and compared with an exact approach.show moreshow less

Download full text files

Export metadata

Additional Services

Search Google Scholar Stastistics
Metadaten
Author: Tobias Flister
URN:urn:nbn:de:kobv:co1-opus4-56175
DOI:https://doi.org/10.26127/BTUOpen-5617
Series (Serial Number):Cottbus Mathematical Preprints (19, 2021)
Editor: Armin FügenschuhORCiD
Referee / Advisor:Prof. Dr. Armin FügenschuhORCiD, Prof. Dr. Ekkehard Köhler
Document Type:Bachelor thesis
Language:German
Year of Completion:2021
Date of final exam:2021/06/03
Release Date:2021/10/05
Tag:Ganzzahlige Programmierung; Heuristiken; Multistatisches Sonar; Netzplanung; Quadratische Nebenbedingungen
Heuristics; Integer programming; Multi-static sonar; Network planning; Quadratic constraints
GND Keyword:Ganzzahlige Optimierung; Heuristik; Netzplanung
Institutes:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Ingenieurmathematik und Numerik der Optimierung
Licence (German):Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.