<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>834</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-02-16</completedDate>
    <publishedDate>2005-02-16</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Rapid Mathematical Programming</title>
    <abstract language="eng">The thesis deals with the implementation and application of out-of-the-box tools in linear and mixed integer programming. It documents the lessons learned and conclusions drawn from five years of implementing, maintaining, extending, and using several computer codes to solve real-life industrial problems. By means of several examples it is demonstrated how to apply algebraic modeling languages to rapidly devise mathematical models of real-world problems. It is shown that today's MIP solvers are capable of solving the resulting mixed integer programs, leading to an approach that delivers results very quickly. Even though, problems are tackled that not long ago required the implementation of specialized branch-and-cut algorithms. In the first part of the thesis the modeling language Zimpl is introduced. Chapter 2 contains a complete description of the language. In the subsequent chapter details of the implementation are described. Both theoretical and practical considerations are discussed. Aspects of software engineering, error prevention, and detection are addressed. In the second part several real-world projects are examined that employed the methodology and the tools developed in the first part. Chapter 4 presents three projects from the telecommunication industry dealing with facility location problems. Chapter 5 characterizes questions that arise in UMTS planning. Problems, models, and solutions are discussed. Special emphasis is put on the dependency of the precision of the input data and the results. Possible reasons for unexpected and undesirable solutions are explained. Finally, the Steiner tree packing problem in graphs, a well-known hard combinatorial problem, is revisited. A formerly known, but not yet used model is applied to combine switchbox wire routing and via minimization. All instances known from the literature are solved by this approach, as are some newly generated bigger problem instances.</abstract>
    <identifier type="serial">04-58</identifier>
    <identifier type="opus3-id">834</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8346</identifier>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>04-58</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Modelling Languages</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Steiner Tree Packing in Graphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Location Planning in Telecommunications</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>UMTS</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68N19">Other programming techniques (object-oriented, sequential, concurrent, automatic, etc.)</collection>
    <collection role="msc" number="90B18">Communication networks [See also 68M10, 94A05]</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/834/ZR-04-58.pdf</file>
  </doc>
  <doc>
    <id>1187</id>
    <completedYear/>
    <publishedYear>2009</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-08-30</completedDate>
    <publishedDate>2009-05-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimal Design of Survivable Multi-layer Telecommunication Networks</title>
    <abstract language="eng">Telecommunication transport networks consist of a stack of technologically different subnetworks, so-called layers, which are strongly interdependent. For example, one layer may correspond to an Internet (IP) backbone network whose links are realized by lightpath connections in an underlying optical fiber layer. To ensure that the network can fulfill its task of routing all communication requests, the inter-layer dependencies have to be taken into account already in the planning phase of the network. This is particularly important with survivability constraints, where connections in one layer have to be protected against cable cuts or equipment failures in another layer. The traditional sequential planning approach where one layer is optimized after the other cannot properly take care of the inter-layer dependencies; this can only be achieved with an integrated planning of several network layers at the same time. This thesis provides mathematical models and algorithmic techniques for the integrated optimization of two network layers with survivability constraints. We describe a multi-layer network design problem which occurs in various technologies, and model it mathematically using mixed-integer programming (MIP) formulations. The presented models cover many important practical side constraints from different technological contexts. In contrast to previous models from the literature, they can be used to design large two-layer networks with survivability requirements. We discuss modeling alternatives for various aspects of a multi-layer network and compare different routing formulations under multi-layer survivability constraints. We solve our models using a branch-and-cut-and-price approach with various problemspecific enhancements. This includes a presolving technique based on linear programming to reduce the problem size, combinatorial and sub-MIP-based primal heuristics to compute feasible network configurations, cutting planes which take the multi-layer survivability constraints into account to improve the lower bound on the optimal network cost, and column generation to generate flow variables dynamically during the algorithm. We develop techniques to speed up computations in a Benders decomposition approach and compare this approach to the standard formulation with a single MIP. We use the developed techniques to design large survivable two-layer networks by means of linear and integer programming methods. On realistic test instances with up to 67 network nodes and survivability constraints, we investigate the algorithmic impact of our techniques and show how to use them to compute good network configurations with quality guarantees. Most of the smaller test instances with up to 17 nodes can be solved to near-optimality. Moreover, we can compute feasible solutions and dual bounds even for large networks with survivability constraints, which has not been possible before.</abstract>
    <identifier type="opus3-id">1250</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11876</identifier>
    <author>Sebastian Orlowski</author>
    <submitter>unknown unknown</submitter>
    <advisor>Fredi Tröltzsch</advisor>
    <advisor>Martin Grötschel</advisor>
    <advisor>Michal Pioro</advisor>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Telekommunikationsnetze</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Multi-layer-Netzen Ausfallsicherheit</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>gemischt-ganzzahlige Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Branch-and-cut-and-price</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>telecommunication networks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>survivable multi-layer network design</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-cut-and-price</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="68M10">Network design and communication [See also 68R10, 90B18]</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C34">Semi-infinite programming</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1187/orlowski_sebastian.pdf</file>
  </doc>
  <doc>
    <id>5448</id>
    <completedYear/>
    <publishedYear>2014</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber>366</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName>Dr. Hut Verlag</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>2014-11-06</thesisDateAccepted>
    <title language="eng">Heuristic algorithms in global MINLP solvers</title>
    <abstract language="eng">In the literature for mixed integer programming, heuristic algorithms (particularly primal heuristics) are often considered as stand-alone procedures; in that context, heuristics are treated as an alternative to solving a problem to proven optimality. This conceals the fact that heuristic algorithms are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP).&#13;
&#13;
In the present thesis, we focus on this latter aspect; we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are:&#13;
- Shift-and-Propagate, a novel propagation heuristic for MIP that does not require the solution to an LP relaxation,&#13;
- a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP,&#13;
- an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures,&#13;
- RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution,&#13;
- Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP,&#13;
- Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs,&#13;
- Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection.&#13;
&#13;
Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics on six test sets with altogether 983 instances from academic and industrial sources, including our project partners ForNe, SAP, and Siemens. We observe that heuristics improve the solver performance regarding all measures that we used - by different orders of magnitude. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes.&#13;
&#13;
The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have also been re-implemented within several commercial and noncommercial MIP and MINLP software packages, including Bonmin, CBC, Cplex, Gams, Sulum, and Xpress.</abstract>
    <identifier type="isbn">978-3-8439-1931-9</identifier>
    <identifier type="url">http://www.zib.de/berthold/Berthold2014.pdf</identifier>
    <advisor>Martin Grötschel</advisor>
    <author>Timo Berthold</author>
    <submitter>Timo Berthold</submitter>
    <advisor>Thorsten Koch</advisor>
    <advisor>Andrea Lodi</advisor>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer nonlinear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>primal heuristic</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branching rule</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>large neighborhood search</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>solver software</value>
    </subject>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C59">Approximation methods and heuristics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
  </doc>
  <doc>
    <id>1018</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-10-15</completedDate>
    <publishedDate>2007-10-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Constraint Integer Programming</title>
    <abstract language="eng">This thesis introduces the novel paradigm of constraint integer programming (CIP), which integrates constraint programming (CP) and mixed integer programming (MIP) modeling and solving techniques. It is supplemented by the software SCIP, which is a solver and framework for constraint integer programming that also features SAT solving techniques. SCIP is freely available in source code for academic and non-commercial purposes. Our constraint integer programming approach is a generalization of MIP that allows for the inclusion of arbitrary constraints, as long as they turn into linear constraints on the continuous variables after all integer variables have been fixed. The constraints, may they be linear or more complex, are treated by any combination of CP and MIP techniques: the propagation of the domains by constraint specific algorithms, the generation of a linear relaxation and its solving by LP methods, and the strengthening of the LP by cutting plane separation. The current version of SCIP comes with all of the necessary components to solve mixed integer programs. In the thesis, we cover most of these ingredients and present extensive computational results to compare different variants for the individual building blocks of a MIP solver. We focus on the algorithms and their impact on the overall performance of the solver. In addition to mixed integer programming, the thesis deals with chip design verification, which is an important topic of electronic design automation. Chip manufacturers have to make sure that the logic design of a circuit conforms to the specification of the chip. Otherwise, the chip would show an erroneous behavior that may cause failures in the device where it is employed. An important subproblem of chip design verification is the property checking problem, which is to verify whether a circuit satisfies a specified property. We show how this problem can be modeled as constraint integer program and provide a number of problem-specific algorithms that exploit the structure of the individual constraints and the circuit as a whole. Another set of extensive computational benchmarks compares our CIP approach to the current state-of-the-art SAT methodology and documents the success of our method.</abstract>
    <abstract language="deu">Diese Arbeit stellt einen integrierten Ansatz aus Constraint Programming (CP) und Gemischt-Ganzzahliger Programmierung (Mixed Integer Programming, MIP) vor, den wir Constraint Integer Programming (CIP) nennen. Sowohl Modellierungs- als auch Lösungstechniken beider Felder fließen in den neuen integrierten Ansatz ein, um die unterschiedlichen Stärken der beiden Gebiete zu kombinieren. Als weiteren Beitrag stellen wir der wissenschaftlichen Gemeinschaft die Software SCIP zur Verfügung, die ein Framework für Constraint Integer Programming darstellt und zusätzlich Techniken des SAT-Lösens beinhaltet. SCIP ist im Source Code für akademische und nicht-kommerzielle Zwecke frei erhältlich. Unser Ansatz des Constraint Integer Programming ist eine Verallgemeinerung von MIP, die zusätzlich die Verwendung beliebiger Constraints erlaubt, solange sich diese durch lineare Bedingungen ausdrücken lassen falls alle ganzzahligen Variablen auf feste Werte eingestellt sind. Die Constraints werden von einer beliebigen Kombination aus CP- und MIP-Techniken behandelt. Dies beinhaltet insbesondere die Domain Propagation, die Relaxierung der Constraints durch lineare Ungleichungen, sowie die Verstärkung der Relaxierung durch dynamisch generierte Schnittebenen. Die derzeitige Version von SCIP enthält alle Komponenten, die für das effiziente Lösen von Gemischt-Ganzzahligen Programmen benötigt werden. Die vorliegende Arbeit liefert eine ausführliche Beschreibung dieser Komponenten und bewertet verschiedene Varianten in Hinblick auf ihren Einfluß auf das Gesamt-Lösungsverhalten anhand von aufwendigen praktischen Experimenten. Dabei wird besonders auf die algorithmischen Aspekte eingegangen. Der zweite Hauptteil der Arbeit befasst sich mit der Chip-Design-Verifikation, die ein wichtiges Thema innerhalb des Fachgebiets der Electronic Design Automation darstellt. Chip-Hersteller müssen sicherstellen, dass der logische Entwurf einer Schaltung der gegebenen Spezifikation entspricht. Andernfalls würde der Chip fehlerhaftes Verhalten aufweisen, dass zu Fehlfunktionen innerhalb des Gerätes führen kann, in dem der Chip verwendet wird. Ein wichtiges Teilproblem in diesem Feld ist das Eigenschafts-Verifikations-Problem, bei dem geprüft wird, ob der gegebene Schaltkreisentwurf eine gewünschte Eigenschaft aufweist. Wir zeigen, wie dieses Problem als Constraint Integer Program modelliert werden kann und geben eine Reihe von problemspezifischen Algorithmen an, die die Struktur der einzelnen Constraints und der Gesamtschaltung ausnutzen. Testrechnungen auf Industrie-Beispielen vergleichen unseren Ansatz mit den bisher verwendeten SAT-Techniken und belegen den Erfolg unserer Methode.</abstract>
    <identifier type="opus3-id">1038</identifier>
    <identifier type="urn">urn:nbn:de:kobv:83-opus-16117</identifier>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <advisor>Martin Grötschel</advisor>
    <advisor>Robert E. Bixby</advisor>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Constraint Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Chip-Verifikation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chip verification</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="ccs" number="B.8.1">Reliability, Testing, and Fault-Tolerance (NEW)</collection>
    <collection role="ccs" number="G.1.6">Optimization</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="projects" number="VeriCount">VeriCount</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1018/achterberg_tobias.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1018/Achterberg_Constraint_Integer_ProgrammingDissZweite_Vers.pdf</file>
  </doc>
  <doc>
    <id>1112</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-01-28</completedDate>
    <publishedDate>2009-01-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Constraint Integer Programming</title>
    <abstract language="eng">This thesis introduces the novel paradigm of "constraint integer programming" (CIP), which integrates constraint programming (CP) and mixed integer programming (MIP) modeling and solving techniques. It is supplemented by the software SCIP, which is a solver and framework for constraint integer programming that also features SAT solving techniques. SCIP is freely available in source code for academic and non-commercial purposes. Our constraint integer programming approach is a generalization of MIP that allows for the inclusion of arbitrary constraints, as long as they turn into linear constraints on the continuous variables after all integer variables have been fixed. The constraints, may they be linear or more complex, are treated by any combination of CP and MIP techniques: the propagation of the domains by constraint specific algorithms, the generation of a linear relaxation and its solving by LP methods, and the strengthening of the LP by cutting plane separation. The current version of SCIP comes with all of the necessary components to solve mixed integer programs. In the thesis, we cover most of these ingredients and present extensive computational results to compare different variants for the individual building blocks of a MIP solver. We focus on the algorithms and their impact on the overall performance of the solver. In addition to mixed integer programming, the thesis deals with chip design verification, which is an important topic of electronic design automation. Chip manufacturers have to make sure that the logic design of a circuit conforms to the specification of the chip. Otherwise, the chip would show an erroneous behavior that may cause failures in the device where it is employed. An important subproblem of chip design verification is the property checking problem, which is to verify whether a circuit satisfies a specified property. We show how this problem can be modeled as constraint integer program and provide a number of problem-specific algorithms that exploit the structure of the individual constraints and the circuit as a whole. Another set of extensive computational benchmarks compares our CIP approach to the current state-of-the-art SAT methodology and documents the success of our method.</abstract>
    <abstract language="deu">Diese Arbeit stellt einen integrierten Ansatz aus "Constraint Programming" (CP) und Gemischt-Ganzzahliger Programmierung ("Mixed Integer Programming", MIP) vor, den wir "Constraint Integer Programming" (CIP) nennen. Sowohl Modellierungs- als auch Lösungstechniken beider Felder fließen in den neuen integrierten Ansatz ein, um die unterschiedlichen Stärken der beiden Gebiete zu kombinieren. Als weiteren Beitrag stellen wir der wissenschaftlichen Gemeinschaft die Software SCIP zur Verfügung, die ein Framework für Constraint Integer Programming darstellt und zusätzlich Techniken des SAT-Lösens beinhaltet. SCIP ist im Source Code für akademische und nicht-kommerzielle Zwecke frei erhältlich. Unser Ansatz des Constraint Integer Programming ist eine Verallgemeinerung von MIP, die zusätzlich die Verwendung beliebiger Constraints erlaubt, solange sich diese durch lineare Bedingungen ausdrücken lassen falls alle ganzzahligen Variablen auf feste Werte eingestellt sind. Die Constraints werden von einer beliebigen Kombination aus CP- und MIP-Techniken behandelt. Dies beinhaltet insbesondere die "Domain Propagation", die Relaxierung der Constraints durch lineare Ungleichungen, sowie die Verstärkung der Relaxierung durch dynamisch generierte Schnittebenen. Die derzeitige Version von SCIP enthält alle Komponenten, die für das effiziente Lösen von Gemischt-Ganzzahligen Programmen benötigt werden. Die vorliegende Arbeit liefert eine ausführliche Beschreibung dieser Komponenten und bewertet verschiedene Varianten in Hinblick auf ihren Einfluß auf das Gesamt-Lösungsverhalten anhand von aufwendigen praktischen Experimenten. Dabei wird besonders auf die algorithmischen Aspekte eingegangen. Ein weiterer Hauptteil der Arbeit befasst sich mit der Chip-Design-Verifikation, die ein wichtiges Thema innerhalb des Fachgebiets der "Electronic Design Automation" darstellt. Chip-Hersteller müssen sicherstellen, dass der logische Entwurf einer Schaltung der gegebenen Spezifikation entspricht. Andernfalls würde der Chip fehlerhaftes Verhalten aufweisen, dass zu Fehlfunktionen innerhalb des Gerätes führen kann, in dem der Chip verwendet wird. Ein wichtiges Teilproblem in diesem Feld ist das Eigenschafts-Verifikations-Problem, bei dem geprüft wird, ob der gegebene Schaltkreisentwurf eine gewünschte Eigenschaft aufweist. Wir zeigen, wie dieses Problem als Constraint Integer Program modelliert werden kann und geben eine Reihe von problemspezifischen Algorithmen an, die die Struktur der einzelnen Constraints und der Gesamtschaltung ausnutzen. Testrechnungen auf Industrie-Beispielen vergleichen unseren Ansatz mit den bisher verwendeten SAT-Techniken und belegen den Erfolg unserer Methode.</abstract>
    <identifier type="opus3-id">1153</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11129</identifier>
    <enrichment key="SourceTitle">Buchveröffentlichung: Tobias Achterberg: Constraint Integer Programming. Dr. Hut Verl. 2008. ISBN 978-3-89963-892-9</enrichment>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <advisor>Martin Grötschel</advisor>
    <advisor>Robert E. Bixby</advisor>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Constraint Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Chip-Verifikation</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mathematische Programmierung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Constraint Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Chip Verification</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mathematical Programming</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1112/Achterberg_Constraint_Integer_Programming.pdf</file>
  </doc>
</export-example>
