Publikation: Exploring Advanced Techniques in Mixed-Integer Linear Programming : A Study of the Branch-and-Cut Framework
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
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)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
HUYNH, Thanh-Van, 2023. Exploring Advanced Techniques in Mixed-Integer Linear Programming : A Study of the Branch-and-Cut Framework [Bachelor thesis]. Konstanz: Universität KonstanzBibTex
@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>