English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 DetailsSummary
  Binary Decision Diagrams and Integer Programming

Behle, M. (2007). Binary Decision Diagrams and Integer Programming. PhD Thesis, Universität des Saarlandes, Saarbrücken.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1D75-1 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-B352-4
Genre: Thesis

Files

show Files
hide Files
:
behle_thesis.pdf (Any fulltext), 898KB
 
File Permalink:
-
Name:
behle_thesis.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show
hide
Locator:
http://scidok.sulb.uni-saarland.de/volltexte/2010/3200/ (Any fulltext)
Description:
-
OA-Status:
Green
Locator:
http://scidok.sulb.uni-saarland.de/doku/lic_ohne_pod.php?la=de (Copyright transfer agreement)
Description:
-
OA-Status:
Not specified

Creators

show
hide
 Creators:
Behle, Markus1, 2, Author           
Eisenbrand, Friedrich3, Advisor           
Mehlhorn, Kurt1, Referee           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2International Max Planck Research School, MPI for Informatics, Max Planck Society, ou_1116551              
3Discrete Optimization, MPI for Informatics, Max Planck Society, ou_1116548              

Content

show
hide
Free keywords: -
 Abstract: In this work we show how Binary Decision Diagrams can be used as a powerful tool for 0/1~Integer Programming and related polyhedral problems. We develop an output-sensitive algorithm for building a threshold BDD, which represents the feasible 0/1~solutions of a linear constraint, and give a parallel \emph{and}-operation for threshold BDDs to build the BDD for a 0/1~IP. In addition we construct a 0/1~IP for finding the optimal variable orderand computing the variable ordering spectrum of a threshold BDD. For the investigation of the polyhedral structure of a 0/1~IP we show how BDDs can be applied to count or enumerate all 0/1~vertices of the corresponding 0/1~polytope, enumerate its facets, and find an optimal solution or count or enumerate all optimal solutions to a linear objective function. Furthermore we developed the freely available tool \texttt{azove} which outperforms existing codes for the enumeration of 0/1~points. Branch~\&~Cut is today's state-of-the-art method to solve 0/1~IPs. We present a novel approach to generate valid inequalities for 0/1~IPs which is based on BDDs. We implemented our BDD based separation routine in a Branch~\&~Cut framework. Our computational results show that our approach is well suited to solve small but hard 0/1~IPs.

Details

show
hide
Language(s): eng - English
 Dates: 2007-12-2220072007
 Publication Status: Issued
 Pages: -
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 520603
Other: Local-ID: C1256BDD00205AD6-7D3B023899783B5EC1257359006E567C-Behle2007
 Degree: PhD

Event

show

Legal Case

show

Project information

show

Source

show