Publikation:

Exploring Advanced Techniques in Mixed-Integer Linear Programming : A Study of the Branch-and-Cut Framework

Lade...
Vorschaubild

Dateien

Huynh_2-1183d1a6s6x9k8.pdf
Huynh_2-1183d1a6s6x9k8.pdfGröße: 4.59 MBDownloads: 99

Datum

2023

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Link zur Lizenz

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Bachelorarbeit
Publikationsstatus
Published

Erschienen in

Zusammenfassung

In this thesis, we will study the theoretical foundations of the branch-and-cut framework, which is a state-of-the-art paradigm for solving linear optimization problems involving integer variables.

As a hybrid of the branch-and-bound algorithm and the cutting planes method, branch-and-cut contains key ingredients of both strategies. The underlying idea of branch-and-bound is divide-and-conquer. When iteratively dividing into smaller subproblems and solving these subproblems’ relaxations, which do not contain any integrality conditions anymore, three questions arise: How is the solution space partioned to produce new subproblems, in which order does the algorithm explore the subproblems, and how do we prevent exploration of suboptimal regions of the solution space? We will give an overview over various branching rules and node selection methods, which address the first two questions.

The focus will be on the plane separation, which answers the last question: The idea is to introduce inequalities, which are valid for the solution space of the root problem, but not for the current solution of the relaxed subproblem, tightening the relaxation iteratively until, ideally, an integer solution is found. We will introduce and prove both the mixed-integer rounding cut and the Gomory mixed-integer cut. These two cuts are equivalent, for which we will provide a proof as well. Lastly, we will demonstrate this equivalence and visualize the cuts in an example.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
510 Mathematik

Schlagwörter

Mixed-Integer Linear Programming, Branch-and-Cut, Discrete Optimization, Integer Programming

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690HUYNH, Thanh-Van, 2023. Exploring Advanced Techniques in Mixed-Integer Linear Programming : A Study of the Branch-and-Cut Framework [Bachelor thesis]. Konstanz: Universität Konstanz
BibTex
@mastersthesis{Huynh2023-12-21Explo-69233,
  year={2023},
  title={Exploring Advanced Techniques in Mixed-Integer Linear Programming : A Study of the Branch-and-Cut Framework},
  address={Konstanz},
  school={Universität Konstanz},
  author={Huynh, Thanh-Van}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/69233">
    <dc:contributor>Huynh, Thanh-Van</dc:contributor>
    <dc:creator>Huynh, Thanh-Van</dc:creator>
    <dc:rights>Attribution-NonCommercial-ShareAlike 4.0 International</dc:rights>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:abstract>In this thesis, we will study the theoretical foundations of the branch-and-cut framework, which is a state-of-the-art paradigm for solving linear optimization problems involving integer variables.

As a hybrid of the branch-and-bound algorithm and the cutting planes method, branch-and-cut contains key ingredients of both strategies. The underlying idea of branch-and-bound is divide-and-conquer. When iteratively dividing into smaller subproblems and solving these subproblems’ relaxations, which do not contain any integrality conditions anymore, three questions arise: How is the solution space partioned to produce new subproblems, in which order does the algorithm explore the subproblems, and how do we prevent exploration of suboptimal regions of the solution space? We will give an overview over various branching rules and node selection methods, which address the first two questions.

The focus will be on the plane separation, which answers the last question: The idea is to introduce inequalities, which are valid for the solution space of the root problem, but not for the current solution of the relaxed subproblem, tightening the relaxation iteratively until, ideally, an integer solution is found. We will introduce and prove both the mixed-integer rounding cut and the Gomory mixed-integer cut. These two cuts are equivalent, for which we will provide a proof as well. Lastly, we will demonstrate this equivalence and visualize the cuts in an example.</dcterms:abstract>
    <dcterms:title>Exploring Advanced Techniques in Mixed-Integer Linear Programming : A Study of the Branch-and-Cut Framework</dcterms:title>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-02-02T12:23:40Z</dcterms:available>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dcterms:issued>2023-12-21</dcterms:issued>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2024-02-02T12:23:40Z</dc:date>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/69233"/>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-sa/4.0/"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/69233/4/Huynh_2-1183d1a6s6x9k8.pdf"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/69233/4/Huynh_2-1183d1a6s6x9k8.pdf"/>
    <dc:language>eng</dc:language>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Hochschulschriftenvermerk
Konstanz, Universität Konstanz, Bachelorarbeit, 2024
Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen