@masterthesis{Flister2021, type = {Bachelor Thesis}, author = {Flister, Tobias}, title = {Eine Heuristik zur L{\"o}sung ganzzahliger Programme mit quadratischen Nebenbedingungen}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-5617}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-56175}, school = {BTU Cottbus - Senftenberg}, year = {2021}, abstract = {Die Frage nach dem L{\"o}sen von ganzzahligen Programmen mit quadratischen Nebenbedingungen spielt beim Aufbau multistatischer Sonar-Netze eine Rolle. Hierbei werden Schall-Sender und -Empf{\"a}nger in einem Ozeanabschnitt so platziert, dass m{\"o}glichst jeder Bereich durch mindestens ein Sender-Empf{\"a}nger-Paar {\"u}berwacht werden kann. Diskretisiert man den Abschnitt r{\"a}umlich, so kann die Frage nach der Platzierung durch bin{\"a}re Entscheidungsvariablen beschrieben werden. Da es auf die paarweise Platzierung ankommt, werden in den Modellen die Bin{\"a}rvariablen multipliziert, was einem logischen „Und" entspricht. Um die Modelle halbwegs schnell numerisch zu l{\"o}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{\"a}t zu l{\"o}sen. In dieser Bachelorarbeit werden heuristische L{\"o}sungsverfahren entwickelt, welche in der Lage sind, innerhalb k{\"u}rzester Zeit gute (aber nicht beweisbar optimale) L{\"o}sungen zu liefern. Ausgangspunkt war die Grundidee, Sender und Empf{\"a}nger abwechselnd zu optimieren, bis keine weitere Verbesserung mehr eintritt. Numerische Ergebnisse werden anhand von Testinstanzen pr{\"a}sentiert und mit einem exakten Ansatz verglichen.}, subject = {Heuristiken; Ganzzahlige Programmierung; Quadratische Nebenbedingungen; Multistatisches Sonar; Netzplanung; Heuristics; Integer programming; Quadratic constraints; Multi-static sonar; Network planning; Ganzzahlige Optimierung; Heuristik; Netzplanung}, language = {de} }