<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>5617</id>
    <completedYear>2021</completedYear>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>bachelorthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-09-14</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>2021-06-03</thesisDateAccepted>
    <title language="deu">Eine Heuristik zur Lösung ganzzahliger Programme mit quadratischen Nebenbedingungen</title>
    <title language="eng">A heuristic for the solution of integer programs with quadratic constraints</title>
    <abstract language="deu">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 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.</abstract>
    <abstract language="eng">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 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.</abstract>
    <identifier type="doi">10.26127/BTUOpen-5617</identifier>
    <identifier type="urn">urn:nbn:de:kobv:co1-opus4-56175</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <licence>Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International</licence>
    <author>Tobias Flister</author>
    <series>
      <title>Cottbus Mathematical Preprints</title>
      <number>19, 2021</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Heuristiken</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Quadratische Nebenbedingungen</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Multistatisches Sonar</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Netzplanung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Heuristics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Quadratic constraints</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multi-static sonar</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Network planning</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Ganzzahlige Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Heuristik</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>swd</type>
      <value>Netzplanung</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="collections" number="">Wiss. Publikationen</collection>
    <collection role="institutes" number="1307">FG Ingenieurmathematik und Numerik der Optimierung</collection>
    <thesisPublisher>BTU  Cottbus - Senftenberg</thesisPublisher>
    <thesisGrantor>BTU Cottbus - Senftenberg</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-btu/files/5617/COMP-19-2021_Flister.pdf</file>
  </doc>
</export-example>
