2020-10-22T10:34:25Zhttp://edoc.mpg.de/ac_p_oai.ploai:edoc.mpg.de:2018302010-12-0387:936
Bounds on the Chvátal rank of Polytopes in the 0/1 Cube
Eisenbrand, Friedrich
Schulz, Andreas S.
expertsonly
Gomory's and Chvátal's cutting-plane procedure proves recursively
the validity of linear inequalities for the integer hull of a given
polyhedron. The number of rounds needed to obtain all valid
inequalities is known as the Chvátal rank of the polyhedron. It is
well-known that the Chvátal rank can be arbitrarily large, even if
the polyhedron is bounded, if it is of dimension $2$, and if its
integer hull is a $0/1$-polytope.
We prove that the Chvátal rank of polyhedra featured in common
relaxations of many combinatorial optimization problems is rather small;
in fact, the rank of any polytope contained in the $n$-dimensional
$0/1$-cube is at most $3 n^2 \lg n$. This improves upon a recent
result of Bockmayr et al.\ \cite{BEHS99} who obtained an upper bound of
$\text{O}(n^3 \log n)$.
Moreover, we refine this result by showing that the rank of any
polytope in the $0/1$-cube that is defined by inequalities with
small coefficients is $\text{O}(n)$. The latter observation explains
why for most cutting planes derived in polyhedral studies of several
popular combinatorial optimization problems only linear growth has
been observed (see, e.g., \cite{ChvatalCookHartmann89}); the
coefficients of the corresponding inequalities are usually small.
Similar results were only known
for monotone polyhedra before.
Finally, we provide a family of polytopes contained in the
$0/1$-cube the Chvátal rank of which is at least $(1+e) n$
for some $e > 0$; the
best known lower bound was $n$.
2003
Article
http://edoc.mpg.de/201830
urn:ISSN:1439-6912
Combinatorica, v.23, 245-261 (2003)
en
oai:edoc.mpg.de:2018312010-12-0387:936
Primal Separation for 0/1 Polytopes
Eisenbrand, Friedrich
Rinaldi, Giovanni
Ventura, Paolo
expertsonly
\noindent
The 0/1~primal separation problem is: Given an extreme point $\bar{x}$ of a
0/1~polytope $P$ and some point $x^*$, find an inequality which is
tight at $\bar{x}$, violated by $x^*$ and valid for $P$ or assert that
no such inequality exists. It is known
that this separation variant can be reduced to the standard
separation problem for $P$.
\noindent
We show that 0/1~optimization and 0/1~primal separation
are polynomial time equivalent. This implies that the problems
0/1~optimization, 0/1~standard separation, 0/1~augmentation, and
0/1~primal separation are polynomial time equivalent.
\noindent
Then we provide polynomial time primal separation procedures for
matching, stable set, maximum cut, and maximum bipartite graph
problems, giving evidence that these algorithms are conceptually
simpler and easier to implement than their corresponding counterparts
for standard separation. In particular, for perfect matching we
present an algorithm for primal separation that rests only on simple
max-flow computations. In contrast, the known standard separation
method relies on an explicit minimum odd cut algorithm. Consequently,
we obtain a very simple proof that a maximum weight perfect matching
of a graph can be computed in polynomial time.
2003
Article
http://edoc.mpg.de/201831
urn:ISSN:0025-5610
Mathematical Programming / A, v.95, 475-491 (2003)
en
oai:edoc.mpg.de:2018762010-12-0387:936
Isoperimetric Inequalities and the Width parameters of graphs
Chandran, L. Sunil
Telikepalli, Kavitha
Subramanian, C. R.
Warnow, Tandy
Zhu, Binhai
expertsonly
Springer
2003
Conference-Paper
http://edoc.mpg.de/201876
urn:ISBN:3-540-40534-8
Computing and Combinatorics : 9th Annual International Conference, COCOON 2003, Springer, 385-393 (2003)
en
oai:edoc.mpg.de:2018802010-12-0387:936
A compact linear program for testing optimality of perfect matchings
Ventura, Paolo
Eisenbrand, Friedrich
expertsonly
It is a longstanding open problem whether there exists a polynomial size
description of the perfect matching polytope. We give a partial answer to this
question by proving the following result. The polyhedron defined by the
constraints of the perfect matching polytope which are active at a given
perfect matching can be obtained as the projection of a compact polyhedron.
Thus there exists a compact linear program which is unbounded if and only if
the perfect matching is not optimal with respect to a given edge weight. This
result provides a simple reduction of the maximum weight perfect matching
problem to compact linear programming.
2003
Article
http://edoc.mpg.de/201880
urn:ISSN:0167-6377
Operations Research Letters, v.31, 429-434 (2003)
en
oai:edoc.mpg.de:2018932010-12-0387:936
A faster algorithm for two-variable integer programming
Eisenbrand, Friedrich
Laue, Soeren
Ibaraki, Toshihide
Katoh, Naoki
Ono, Hirotaka
expertsonly
We show that a 2-variable integer program, defined by $m$ constraints
involving coefficients with at most $\varphi$ bits can be solved with
$O(m + \varphi)$ arithmetic operations on rational numbers of
size~$O(\varphi)$.
This result closes the gap between the running time of two-variable
integer programming with the sum of the running times of the
Euclidean algorithm on $\varphi$-bit integers and the problem of checking
feasibility of an integer point for $m$~constraints.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201893
urn:ISBN:3-540-20695-7
Algorithms and computation : 14th International Symposium, ISAAC 2003, Springer, 290-299 (2003)
en
oai:edoc.mpg.de:2019202010-12-0387:936
Packing a Trunk
Eisenbrand, Friedrich
Funke, Stefan
Reichel, Joachim
Schömer, Elmar
Di Battista, Giuseppe
Zwick, Uri
expertsonly
We report on a project with a German car manufacturer. The task
is to compute (approximate) solutions to a specific large-scale
packing problem. Given a polyhedral model of a car trunk, the
aim is to pack as many identical boxes of size $4 × 2 × 1$ units
as possible into the interior of the trunk. This measure is
important for car manufacturers, because it is a standard in the
European Union.
First, we prove that a natural formal variant of this problem is
NP-complete. Further, we use a combination of integer linear
programming techniques and heuristics that exploit the geometric
structure to attack this problem. Our experiments show that for
all considered instances, we can get very close to the optimal
solution in reasonable time.
Springer
(c) Springer-Verlag
2003
Conference-Paper
http://edoc.mpg.de/201920
urn:ISBN:3-540-20064-9
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 618-629 (2003)
en
oai:edoc.mpg.de:2019952010-12-0387:936
Fast integer programming in fixed dimension
Eisenbrand, Friedrich
Di Battista, Guiseppe
Zwick, Uri
expertsonly
It is shown that the optimum of an integer program in fixed
dimension, which is defined by a fixed number of constraints, can be
computed with $O(s)$ basic arithmetic operations, where $s$ is
the binary encoding length of the input. This improves on the
quadratic running time of previous algorithms which are based on
Lenstra's algorithm and binary search.
It follows that an integer program in fixed dimension, which is
defined by $m$ constraints, each of binary encoding length at most
$s$, can be solved with an expected number of $O(m + \log(m) \,
s)$ arithmetic operations using Clarkson's random sampling
algorithm.
Springer
Copyright Springer Verlag
2003
Conference-Paper
http://edoc.mpg.de/201995
urn:ISBN:3-540-20064-9
Algorithms - ESA 2003 : 11th Annual European Symposium, Springer, 196-207 (2003)
en
oai:edoc.mpg.de:2020152010-12-0387:936
Diversity-Conscious Retrieval from Generalized Cases: A Branch and Bound Algorithm
Mougouie, Babak
Richter, Michael M.
Bergmann, Ralph
Ashley, Kevin D.
Bridge, Derek G.
expertsonly
Recommendation systems offer the most similar point cases to a target query.
Among those cases similar to the query, some may
be similar and others dissimilar to each other. Offering only the most similar
cases wrt. the query leads to the well known problem
that the customers may have only a few number of choices. To address the
problem of offering a diverse set of cases, several
approaches have been proposed. In a different line of CBR research, the concept
of generalized cases has been systematically
studied, which can be applied to represent parameterizable products. First
approaches to retrieving the most similar point cases
from a case base of generalized cases have been proposed. However, until now no
algorithm is known to retrieve a diverse set of
point cases from a case base of generalized cases. This is the topic of this
paper. We present a new branch and bound method to
build a retrieval set of point cases such that its diversity is sufficient and
each case in the retrieval set is a representative
for a set of similar point cases.
Springer
2003
Conference-Paper
http://edoc.mpg.de/202015
urn:ISBN:3-540-40433-3
Case-based reasoning research and development : 5th International Conference on Case-Based Reasoning, ICCBR 2003, Springer, 319-331 (2003)
en
oai:edoc.mpg.de:2020282010-12-0387:936
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph
Eisenbrand, Friedrich
Funke, Stefan
Garg, Naveen
Könemann, Jochen
expertsonly
We present a combinatorial polynomial time algorithm to compute a
maximum stable set of a $t$-perfect graph. The algorithm rests on an
$e$-approximation algorithm for general set covering and packing
problems and is combinatorial in the sense that it does
not use an explicit linear programming algorithm or
methods from linear algebra or convex geometry. Instead our algorithm is
based on basic arithmetic operations and comparisons of rational
numbers which are of polynomial binary encoding size in the input.
ACM
2003
Conference-Paper
http://edoc.mpg.de/202028
urn:ISBN:0-89871-538-5
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), ACM, 517-522 (2003)
en
oai:edoc.mpg.de:2020352010-12-0387:936
A spectral lower bound for the treewidth of a graph and its consequences
Chandran, L. Sunil
Subramanian, C. R.
expertsonly
2003
Article
http://edoc.mpg.de/202035
urn:ISSN:0020-1090
Information Processing Letters, v.87, 195-200 (2003)
en
oai:edoc.mpg.de:2020362010-12-0387:936
Detecting directed 4-cycles still faster
Eisenbrand, Friedrich
Grandoni, Fabrizio
expertsonly
We present a method to detect simple cycles of length~4 of a
directed graph in~$O(n^{1/\omega} e^{2-2/\omega})$ steps, where
$n$~denotes the number of nodes, $e$ denotes the number of
edges and $\omega$ is the exponent of matrix multiplication. This
improves upon the currently fastest methods for
$\alpha\in (2/(4-\omega),(\omega+1)/2)$, where $e=n^\alpha$.
2003
Article
http://edoc.mpg.de/202036
urn:ISSN:0020-0190
Information Processing Letters, v.87, 13-15 (2003)
en
oai:edoc.mpg.de:2059522010-12-0387:936
Similarity Assessment for Generalizied Cases by Optimization Methods
Mougouie, Babak
Bergmann, Ralph
Craw, Susan
Preece, Alun
expertsonly
Generalized cases are cases that cover a subspace rather than a
point in the problem-solution space. Generalized cases can be
represented by a set of constraints over the case attributes. For
such representations, the similarity assessment between a point
query and generalized cases is a difficult problem that is
addressed in this paper. The task is to find the distance (or the
related similarity) between the point query and the closest point
of the area covered by the generalized cases, with respect to some
given similarity measure. We formulate this problem as a
mathematical optimization problem and we propose a new cutting
plane method which enables us to rank generalized cases according
to their distance to the query.
Springer
This work is subject to copyright. All rights are reserved,
whether the whole or part of the material is concerned,
specifically the rights of translation, reprinting, re-use of
illustrations, recitation, broadcasting, reproduction on
microfilms or in any other way, and storage in data banks.
Duplication of this publication or parts thereof is permitted
only under the provisions of the German Copyright Law of
September 9, 1965, in its current prosecution under the
German Copyright Law.
2002
Conference-Paper
http://edoc.mpg.de/205952
urn:ISBN:3-540-44109-3/0302-9743
Advances in Case-Based Reasoning, 6th European Conference, ECCBR 2002; proceedings, Springer, 249-263 (2002)
en
oai:edoc.mpg.de:2318232010-12-0387:936
On the complexity of fixed parameter clique and dominating set
Eisenbrand, Friedrich
Grandoni, Fabrizio
expertsonly
2004
Article
http://edoc.mpg.de/231823
urn:ISSN:0304-3975
Theoretical Computer Science, v.326, 57-67 (2004)
en
oai:edoc.mpg.de:2318242010-12-0387:936
On the arrangement of cliques in chordal graphs with respect to the cuts
Chandran, L. Sunil
Narayanaswamy, N.S.
Chwa, Kyung-Yong
Munro, J. Ian
expertsonly
Springer
2004
Conference-Paper
http://edoc.mpg.de/231824
urn:ISBN:3-540-22856-X
Computing and combinatorics : 10th Annual International Conference, COCOON 2004, Springer, 151-160 (2004)
en
oai:edoc.mpg.de:2318252010-12-0387:936
Refined memorisation for vertex cover
Chandran, L. Sunil
Grandoni, Fabrizio
Dehne, F.
Downey, R.
Fellows, M.
expertsonly
Springer
2004
Conference-Paper
http://edoc.mpg.de/231825
urn:ISBN:3-540-23071-8
Parameterized and exact computation : First International Workshop, IWPEC 2004, Springer, 61-70 (2004)
en
oai:edoc.mpg.de:2318262010-12-0387:936
Minimum cuts, girth and a spectral threshold
Chandran, L. Sunil
expertsonly
2004
Article
http://edoc.mpg.de/231826
urn:ISSN:0020-1090
Information Processing Letters, v.89, 105-110 (2004)
en
oai:edoc.mpg.de:2318312010-12-0387:936
On the number of minimum cuts in a graph
Chandran, L. Sunil
Shankar Ram, L.
expertsonly
2004
Article
http://edoc.mpg.de/231831
urn:ISSN:0895-4801
SIAM Journal on Discrete Mathematics, v.18, 177-194 (2004)
en
oai:edoc.mpg.de:2318322010-12-0387:936
Bounded Model Checking and Inductive Verification of Hybrid Discrete-continuous Systems
Becker, Bernd
Behle, Markus
Eisenbrand, Friedrich
Fränzle, Martin
Herbstritt, Marc
Herde, Christian
Hoffmann, Jörg
Kröning, Daniel
Nebel, Bernhard
Polian, Ilia
Wimmer, Ralf
Stoffel, Dominik
Kunz, Wolfgang
expertsonly
Shaker
2004
Conference-Paper
http://edoc.mpg.de/231832
urn:ISBN:3-8322-2486-6
Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen : [7. GIT/ITG/GMM-Workshop Modellierung und Verifikation], Shaker, 65-75 (2004)
en
oai:edoc.mpg.de:2320822010-12-0387:936
Point Containment in the Integer Hull of a Polyhedron
Althaus, Ernst
Eisenbrand, Friedrich
Funke, Stefan
Mehlhorn, Kurt
expertsonly
We show that the point containment problem in the integer hull of a
polyhedron, which is defined by $m$ inequalities, with coefficients of at most
$\varphi$ bits can be solved in time $\bigO(m+\varphi)$ in the two-dimensional
case and in expected time $\bigO(m+\varphi^2 \log m)$ in any fixed dimension.
This improves on the algorithm which is based on the equivalence of separation
and optimization and on a direct algorithm (SODA 97) for the two-dimensional
case.
ACM
2004
Conference-Paper
http://edoc.mpg.de/232082
urn:ISBN:0-89871-558-X
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04), ACM, 929-933 (2004)
en
oai:edoc.mpg.de:2415942010-12-0387:936
Point containment in the integer hull of a polyhedron
Althaus, Ernst
Eisenbrand, Friedrich
Funke, Stefan
Mehlhorn, Kurt
expertsonly
We show that the point containment problem in the integer hull of a
polyhedron, which is defined by $m$ inequalities, with
coefficients of at most $\varphi$ bits can be solved in
time $O(m+\varphi)$ in the two-dimensional case and in expected time
$O(m+\varphi^2 \log m)$ in any fixed dimension. This improves on the
algorithm which is based on the equivalence of separation and
optimization in the general case and on a direct algorithm (SODA 97)
for the two-dimensional case.
ACM
2004
Conference-Paper
http://edoc.mpg.de/241594
urn:ISBN:0-89871-558-X
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04), ACM, 929-933 (2004)
en
oai:edoc.mpg.de:5205852010-12-0387:936
Girth and Treewidth
Chandran, L. Sunil
Subramanian, C. R.
expertsonly
2005
Article
http://edoc.mpg.de/520585
urn:ISSN:0095-8956
Journal of Combinatorical Theory, Series B, v.93, 23-32 (2005)
en
oai:edoc.mpg.de:5205862010-12-0387:936
An improved approximation algorithm for virtual private network design
Eisenbrand, Friedrich
Grandoni, Fabrizio
expertsonly
SIAM
2005
Conference-Paper
http://edoc.mpg.de/520586
urn:ISBN:0-89871-585-7
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 05), SIAM, 928-932 (2005)
en
oai:edoc.mpg.de:5205872010-12-0387:936
A linear algorithm for integer programming in the plane
Eisenbrand, Friedrich
Laue, Soeren
expertsonly
2005
Article
http://edoc.mpg.de/520587
urn:ISSN:0025-5610
Mathematical Programming, v.102, 249-259 (2005)
en
oai:edoc.mpg.de:5205882010-12-0387:936
Integer Programming, Lattices and Results in Fixed Dimension
Eisenbrand, Friedrich
Aardal, Karen
expertsonly
Elsevier
2005
InBook
http://edoc.mpg.de/520588
urn:ISBN:0-444-51507-0
Discrete Optimization, 171-244 (2005)
en
oai:edoc.mpg.de:5205892010-12-0387:936
BDDs in a Branch and Cut Framework
Becker, Bernd
Behle, Markus
Eisenbrand, Friedrich
Wimmer, Ralf
expertsonly
Springer
2005
Conference-Paper
http://edoc.mpg.de/520589
urn:ISBN:3-540-25920-1
Nikoletseas, Sotiris: 4th International Workshop on Experimental and Efficient Algorithms (WEA'05), Springer, 452-463 (2005)
en
oai:edoc.mpg.de:5205902010-12-0387:936
Energy-aware stage illumination
Eisenbrand, Friedrich
Funke, Stefan
Karrenbauer, Andreas
Matijevic, Domagoj
expertsonly
ACM
2005
Conference-Paper
http://edoc.mpg.de/520590
urn:ISBN:1-58113-991-8
Proceedings of the Twenty-First Annual Symposium on Computational Geometry (SCG-05), ACM, 336-345 (2005)
en
oai:edoc.mpg.de:5205912010-12-0387:936
Circular ones matrices and the stable set polytope of quasi-line graphs
Eisenbrand, Friedrich
Oriolo, Gianpaolo
Stauffer, Gautier
Ventura, Paolo
expertsonly
Springer
2005
Conference-Paper
http://edoc.mpg.de/520591
urn:ISBN:3-540-26199-0
Jünger, Michael; Kaibel, Volker: Integer programming and combinatorial optimization : 11th International IPCO Conference (IPCO XI), Springer, 291-305 (2005)
en
oai:edoc.mpg.de:5205922010-12-0387:936
Packing a trunk - now with a twist!
Eisenbrand, Friedrich
Funke, Stefan
Karrenbauer, Andreas
Schoemer, Elmar
Reichel, Joachim
expertsonly
ACM
2005
Conference-Paper
http://edoc.mpg.de/520592
urn:ISBN:1-59593-015-9
Spencer, Stephen N.: SPM 2005 : ACM Symposium on Solid and Physical Modeling, ACM, 197-206 (2005)
en
oai:edoc.mpg.de:5205932010-12-0387:936
New approaches for virtual private network designs
Eisenbrand, Friedrich
Grandoni, Fabrizio
Oriolo, Gianpaolo
Skutella, Martin
expertsonly
Springer
2005
Conference-Paper
http://edoc.mpg.de/520593
urn:ISBN:3-540-27580-0
Caires, Luis; Italiano, Giuseppe F.; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti: Automata, languages and programming : 32nd International Colloquim, ICALP 2005, Springer, 1151-1162 (2005)
en
oai:edoc.mpg.de:5205942010-12-0387:936
Provisioning a Virtual Private Network Under the Presence of Non-Communicating Groups
Eisenbrand, Friedrich
Happ, Edda
expertsonly
Virtual private network design in the hose model deals with the
reservation of capacities in a weighted graph such
that the terminals in this network can communicate with one another. Each
terminal is equipped with an upper bound on the
amount of traffic that the terminal can send or receive. The task is
to install capacities at minimum cost and to compute paths for each
unordered terminal pair such that each valid traffic matrix can be
routed along those paths.
\noindent
In this paper we consider a variant of the virtual private
network design problem which generalizes the previously studied
symmetric and asymmetric case. In our model the terminal set is
partitioned into a number of groups, where terminals of each
group do not communicate with each other.
\noindent
Our main result is a 4.74 approximation algorithm for
this problem.
Springer
2006
Conference-Paper
http://edoc.mpg.de/520594
urn:ISBN:978-3-540-34375-2
Calamoneri, Tiziana; Finocchi, Irene; Italiano, Giuseppe F.: Algorithms and complexity : 6th Italian Conference, CIAC 2006, Springer, 105-114 (2006)
en
oai:edoc.mpg.de:5205962010-12-0387:936
Carathéodory bounds for integer cones
Eisenbrand, Friedrich
Shmonin, Gennady
expertsonly
We provide analogues of Carathéodory's theorem for integer cones and apply our
bounds to integer programming and to the cutting stock problem. In particular,
we provide an NP certificate for the latter, whose existence has not been known
so far.
2006
Article
http://edoc.mpg.de/520596
urn:ISSN:0167-6377
Operations Research Letters, v.34, 564-568 (2006)
en
oai:edoc.mpg.de:5205972010-12-0387:936
Multiline Addressing by Network Flow
Eisenbrand, Friedrich
Karrenbauer, Andreas
Skutella, Martin
Xu, Chihao
expertsonly
We consider an optimization problem arising in the design of
controllers for OLED displays. Our objective is to minimize the
current amplitude which has a direct impact on the lifetime of
such a display. Modeling the problem in mathematical terms
yields a class of network flow problems where we group the arcs
and pay in each group only for the arc carrying the maximum
flow. We develop (fully) combinatorial approximation heuristics
suitable for being implemented in the hardware of a control
device that drives an OLED display.
Springer
2006
Conference-Paper
http://edoc.mpg.de/520597
urn:ISBN:978-3-540-38875-3
Azar, Yossi; Erlebach, Thomas: Algorithms - ESA 2006 : 14th Annual European Symposium, Springer, 744-755 (2006)
en
oai:edoc.mpg.de:5205982010-12-0387:936
0/1 vertex and facet enumeration with BDDs
Behle, Markus
Eisenbrand, Friedrich
expertsonly
SIAM
2007
Conference-Paper
http://edoc.mpg.de/520598
urn:ISBN:978-0-898716-28-3
Applegate, David; Brodal, Gerth Stolting; Panario, Daniel; Sedgewick, Robert: Proceedings of the ninth Workshop on Algorithm Engineering and Experiments (ALENEX'07), SIAM, 158-165 (2007)
en
oai:edoc.mpg.de:5205992010-12-0387:936
A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem
Behle, Markus
Jünger, Michael
Liers, Frauke
expertsonly
Springer
2007
Conference-Paper
http://edoc.mpg.de/520599
urn:ISBN:978-3-540-72844-3
Demetrescu, Camil: 6th Workshop on Experimental Algorithms (WEA'07), Springer, 379-392 (2007)
en
oai:edoc.mpg.de:5206002010-12-0387:936
Algorithms for longer OLED Lifetime
Eisenbrand, Friedrich
Karrenbauer, Andreas
Xu, Chihao
expertsonly
Springer
2007
Conference-Paper
http://edoc.mpg.de/520600
Camil Demetrescu: WEA 2007, Springer, 338-351 (2007)
en
oai:edoc.mpg.de:5206012010-12-0387:936
On Threshold BDDs and the Optimal Variable Ordering Problem
Behle, Markus
expertsonly
Springer
2007
Conference-Paper
http://edoc.mpg.de/520601
urn:ISBN:978-3-540-73555-7
Dress, Andreas; Xu, Yinfeng; Zhu, Binhai: First International Conference on Combinatorial Optimization and Applications (COCOA'07), Springer, 124-135 (2007)
en
oai:edoc.mpg.de:5206022010-12-0387:936
A {N}ew {A}ddressing {S}cheme for {PM} {OLED} {D}isplay
Xu, Chihao
Karrenbauer, Andreas
Soh, Kian Min
Wahl, Jürgen
expertsonly
Society for Information Display
2007
Conference-Paper
http://edoc.mpg.de/520602
urn:ISSN:0097-966X
Morreale, Jay: SID 2007 International Symposium Digest of Technical Papers, Society for Information Display, 97-100 (2007)
en
oai:edoc.mpg.de:5206042010-12-0387:936
On threshold BDDs and the optimal variable ordering problem
Behle, Markus
expertsonly
2008
Article
http://edoc.mpg.de/520604
urn:ISSN:1382-6905
info:doi/10.1007/s10878-007-9123-z
Journal of Combinatorial Optimization, v.16, 107-118 (2008)
en
oai:edoc.mpg.de:5206052010-12-0387:936
Packing a Trunk - Now with a Twist!
Eisenbrand, Friedrich
Funke, Stefan
Karrenbauer, Andreas
Reichel, Joachim
Schömer, Elmar
expertsonly
In an industry project with a German car manufacturer we
are faced with the challenge of placing a maximum number of
uniform rigid rectangular boxes in the interior of a car
trunk. The problem is of practical importance due to a
European industry norm which requires car manufacturers
to state the trunk volume according to this measure.
No really satisfactory automated solution for this problem has been
known in the past. In spite of its NP hardness, combinatorial
optimization techniques, which consider only grid-aligned placements,
produce solutions which are very close to the one achievable by a
human expert in several hours of tedious work. The remaining gap is
mostly due to the constraints imposed by the chosen grid.
In this paper we present a new approach which combines the grid-based
combinatorial method with \emph{Simulated Annealing} on a continuous
model. This allows us to explore arbitrary orientations and placements
of boxes, hence closing the gap even further, and -- in some cases --
even surpass the manual expert solution.
The implemented software system allows our industrial partner to
incorporate the trunk volume in a very early stage of the car design
process without relying on a repeated and cumbersome manual evaluation
of the volume.
2007
Article
http://edoc.mpg.de/520605
info:doi/10.1142/S021819590700246X
International Journal of Computational Geometry and Applications, v.17, 505-527 (2007)
en
oai:edoc.mpg.de:5206182010-12-0387:936
Similarity Assessment for Generalizied Cases by Optimization Methods
Mougouie, Babak
Bergmann, Ralph
expertsonly
Generalized cases are cases that cover a subspace rather than a
point in the problem-solution space. Generalized cases can be
represented by a set of constraints over the case attributes. For
such representations, the similarity assessment between a point
query and generalized cases is a difficult problem that is
addressed in this paper. The task is to find the distance (or the
related similarity) between the point query and the closest point
of the area covered by the generalized cases, with respect to some
given similarity measure. We formulate this problem as a
mathematical optimization problem and we propose a new cutting
plane method which enables us to rank generalized cases according
to their distance to the query.
Springer
This work is subject to copyright. All rights are reserved,
whether the whole or part of the material is concerned,
specifically the rights of translation, reprinting, re-use of
illustrations, recitation, broadcasting, reproduction on
microfilms or in any other way, and storage in data banks.
Duplication of this publication or parts thereof is permitted
only under the provisions of the German Copyright Law of
September 9, 1965, in its current prosecution under the
German Copyright Law.
2002
Conference-Paper
http://edoc.mpg.de/520618
urn:ISBN:3-540-44109-3/0302-9743
Craw, Susan; Preece, Alun: Advances in Case-Based Reasoning, 6th European Conference, ECCBR 2002; proceedings, Springer, 249-263 (2002)
en
oai:edoc.mpg.de:5206192010-12-0387:936
0/1 Optimization and 0/1 Primal Separation are Equivalent
Eisenbrand, Friedrich
Rinaldi, Giovanni
Ventura, Paolo
expertsonly
ACM SIAM
2002
Conference-Paper
http://edoc.mpg.de/520619
Proceedings of the 13-th annual ACM SIAM Symposium on Discrete Algorithms, ACM SIAM, 920-926 (2002)
en
oai:edoc.mpg.de:5206202010-12-0387:936
Cutting planes and the elementary closure in fixed dimension
Bockmayr, Alexander
Eisenbrand, Friedrich
expertsonly
2001
Article
http://edoc.mpg.de/520620
Mathematics of Operations Research, v.26, 304-312 (2001)
en
oai:edoc.mpg.de:5206212010-12-0387:936
On Factor Refinement in Number Fields
Buchmann, Johannes
Eisenbrand, Friedrich
expertsonly
1999
Article
http://edoc.mpg.de/520621
Mathematics of Computation, v.68, 345-350 (1999)
en
oai:edoc.mpg.de:5206222010-12-0387:936
Fast reduction of ternary quadratic forms
Eisenbrand, Friedrich
Rote, Günter
expertsonly
Springer
2001
Conference-Paper
http://edoc.mpg.de/520622
Silverman, J.: Proceedings of the 1st Conference on Lattices and Cryptography (CaLC-01), Springer, 99-111 (2001)
en
oai:edoc.mpg.de:5206232010-12-0387:936
Short vectors of planar integral lattices via continued fractions
Eisenbrand, Friedrich
expertsonly
2001
Article
http://edoc.mpg.de/520623
Information Processing Letters, v.79, 121-126 (2001)
en
oai:edoc.mpg.de:5206242010-12-0387:936
Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube
Eisenbrand, Friedrich
Schulz, Andreas S.
expertsonly
Springer
1999
Conference-Paper
http://edoc.mpg.de/520624
urn:ISBN:3-540-66019-4
Cornuéjols, Gérard; Burkard, Rainer E.; Woeginger, Gerhard J.: Proceedings of the 7th Conference on Integer Programming and Combinatorial Optimization (IPCO-99), Springer, 137-150 (1999)
en
oai:edoc.mpg.de:5206252010-12-0387:936
Fast 2-variable integer programming
Eisenbrand, Friedrich
Rote, Günter
expertsonly
Springer
2001
Conference-Paper
http://edoc.mpg.de/520625
Gerards, Bert; Aardal, Karen: Proceedings of the 8th Conference on Integer and Combinatorial Optimization (IPCO-01), Springer, 78-89 (2001)
en
oai:edoc.mpg.de:5206272010-12-0387:936
On the Chvátal Rank of Polytopes in the 0/1 Cube
Bockmayr, Alexander
Eisenbrand, Friedrich
Hartmann, Mark
Schulz, Andreas S.
expertsonly
1999
Article
http://edoc.mpg.de/520627
Discrete Applied Mathematics, v.98, 21-27 (1999)
en
oai:edoc.mpg.de:5206282010-12-0387:936
Combining logic and optimization in cutting plane theory
Eisenbrand, Friedrich
Bockmayr, Alexander
expertsonly
Springer
2000
Conference-Paper
http://edoc.mpg.de/520628
Kirchner, H.; Ringeissen, C.: Proceedings of the Workshop on Frontiers of Combining Systems (FROCOS-2000), Springer, 1-17 (2000)
en
oai:edoc.mpg.de:5206292010-12-0387:936
On the Membership Problem for the Elementary Closure of a Polyhedron
Eisenbrand, Friedrich
expertsonly
1999
Article
http://edoc.mpg.de/520629
Combinatorica, v.19, 297-300 (1999)
en