M. Berger, M. Schröder, K.-H. Küfer

A constraint programming approach for the two-dimensional rectangular packing problem with orthogonal orientations

Berichte des Fraunhofer ITWM, Nr. 147 (2008)

© Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM 2008

ISSN 1434-9973

Bericht 147 (2008)

Alle Rechte vorbehalten. Ohne ausdrückliche schriftliche Genehmigung des Herausgebers ist es nicht gestattet, das Buch oder Teile daraus in irgendeiner Form durch Fotokopie, Mikrofilm oder andere Verfahren zu reproduzieren oder in eine für Maschinen, insbesondere Datenverarbei tungsanlagen, ver-wendbare Sprache zu übertragen. Dasselbe gilt für das Recht der öffentlichen Wiedergabe.

Warennamen werden ohne Gewährleistung der freien Verwendbarkeit benutzt.

Die Veröffentlichungen in der Berichtsreihe des Fraunhofer ITWM können bezogen werden über:

Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM Fraunhofer-Platz 1

67663 Kaiserslautern Germany

Telefon: 06 31/3 16 00-0 Telefax: 06 31/3 16 00-10 99 E-Mail: info@itwm.fraunhofer.de Internet: www.itwm.fraunhofer.de

Vorwort

Das Tätigkeitsfeld des Fraunhofer-Instituts für Techno- und Wirtschaftsmathematik ITWM umfasst anwendungsnahe Grundlagenforschung, angewandte Forschung sowie Beratung und kundenspezifische Lösungen auf allen Gebieten, die für Tech-no- und Wirtschaftsmathematik bedeutsam sind.

In der Reihe »Berichte des Fraunhofer ITWM« soll die Arbeit des Instituts konti-nuierlich einer interessierten Öffentlichkeit in Industrie, Wirtschaft und Wissen-schaft vorgestellt werden. Durch die enge Verzahnung mit dem Fachbereich Ma-thematik der Universität Kaiserslautern sowie durch zahlreiche Kooperationen mit internationalen Institutionen und Hochschulen in den Bereichen Ausbildung und Forschung ist ein großes Potenzial für Forschungsberichte vorhanden. In die Be-richtreihe sollen sowohl hervorragende Diplom- und Projektarbeiten und Disser-tationen als auch Forschungsberichte der Institutsmitarbeiter und Institutsgäste zu aktuellen Fragen der Techno- und Wirtschaftsmathematik aufgenommen werden.

Darüber hinaus bietet die Reihe ein Forum für die Berichterstattung über die zahl-reichen Kooperationsprojekte des Instituts mit Partnern aus Industrie und Wirt-schaft.

Berichterstattung heißt hier Dokumentation des Transfers aktueller Ergebnisse aus mathematischer Forschungs- und Entwicklungsarbeit in industrielle Anwendungen und Softwareprodukte – und umgekehrt, denn Probleme der Praxis generieren neue interessante mathematische Fragestellungen.

Prof. Dr. Dieter Prätzel-Wolters Institutsleiter

Kaiserslautern, im Juni 2001

A CONSTRAINT PROGRAMMING APPROACH FOR THE

TWO-DIMENSIONAL RECTANGULAR PACKING PROBLEM WITH

ORTHOGONAL ORIENTATIONS

MARTIN BERGER, MICHAEL SCHRÖDER, AND KARL-HEINZ KÜFER

FRAUNHOFER INSTITUTE FOR INDUSTRIAL MATHEMATICS (ITWM)FRAUNHOFER-PLATZ 167663 KAISERSLAUTERN

GERMANY{BERGER,SCHROEDER,KUEFER}@ITWM.FRAUNHOFER.DE

TELEPHONE: +49 631 31600-4273FAX: +49 631 31600-5273

Abstract. We propose a constraint-based approach for the two-dimensional rectangu-lar packing problem with orthogonal orientations. This problem is to arrange a set ofrectangles that can be rotated by 90 degrees into a rectangle of minimal size such thatno two rectangles overlap. It arises in the placement of electronic devices during thelayout of 2.5D System-in-Package integrated electronic systems. Moffitt et al. [8] solvethe packing without orientations with a branch and bound approach and use constraintpropagation. We generalize their propagation techniques to allow orientations. Our ap-proach is compared to a mixed-integer program and we provide results that outperformit.

Keywords. rectangular packing, orthogonal ori-

entations, non-overlapping constraints, constraint

propagation.

1. Introduction

Rectangular packing problems occur in many real world applications and challengeresearchers from operations research, constraint programming, artificial intelligence andmany more. We address the two-dimensional rectangular packing problem with orthogo-nal orientations (RPWO) which is to arrange rectangles that can be rotated by 90 degreesinto a rectangular container such that no two overlap. Minimizing the container size is anNP-hard combinatorial optimization problem.

Such a problem arises in 2.5D System-in-Package (SiP) layout design [9]. 2.5D SiP is amodern integration approach of heterogeneous electronic components on modules which arestacked or folded vertically. SiP integration meets modern requirements for miniaturizedelectronic systems, has a predicted growing market demand but still lacks standardizeddesign automation tools. Figure 1 exemplarily illustrates two 2.5D SiP technologies.

The layout process is subdivided into a sequence of three optimization problems [10].In the partitioning step the components are assigned to the vertically stacked modules.In the placement step the components are placed on each module side. The placementproblem on each module involves a RPWO. The routing step includes the arrangement ofthe vertical interconnections and the routing within each module. Figure 2 illustrates thelayout steps in SiP design.

We propose to layout an SiP with our novel prototype electronic design automation(EDA) tool called 3D SiP Expert. This tool uses a database of SiP layouts that are

1

2 M. BERGER, M. SCHRÖDER, K.-H. KÜFER

Figure 1. Two illustrations for SiPs: Integrated on a flexible bended sub-strate (left) and integrated on rigid modules electrically interconnectedthrough conductive solder balls (right).

Figure 2. Layout process of SiPs: Paritioning of the components to mod-ules; placement of the components on the module sides; routing throughvertical interconnections and through the modules.

calculated in an offline phase. Then in an online phase, the engineer can use this toolto quickly navigate to the SiP layout of his interest. The designer can restrict and selectvalues of multiple criteria like size, wiring, thermal and electrical properties of the SiP.This novel approach accelerates the layout process and avoids time consuming re-designcycles.

For the RWPO of the placement problem in SiP layout we need an adequate algorithmicmethod. A multitude of methods from metaheuristics, linear, mixed integer, nonlinearand constraint programming have been developed for rectangular packing [11, 2, 7, 6, 1].However, the orientation is often disregarded and most of the approaches can not integrateimportant constraints arising in SiP design. Therefore, we extend the meta-constraintsatisfaction problem (CSP) approach of Moffitt et al. [8]. Their branch and bound solvesminimal area packing and uses constraint propagation.

We generalize the propagation algorithms for orientations and show the relation of themeta-CSP approach to mixed-integer programming (MIP). We compare our extendedmeta-CSP to an MIP and provide numerical results that outperform it. In conclusion,our approach solves RPWO and can be extended to address the wiring of SiP componentsin order to serve as algorithm of an SiP design automation tool.

The outline of the paper is as follows: In section 2 we introduce our notation andproblem formulation, then discuss the meta-CSP model in section 3 and our generalizationfor orthogonal orientations in section 4. In section 5 we propose an MIP formulation anddiscuss its similarities to our approach. Then we provide numerical results in section 6for our implementations, discuss them and conclude in section 7 with an outline for futurework.

2. Problem Formulation

We denote R := {r1, . . . , rn} as rectangle set with index set I := {1, . . . , n}; wi, hi ∈ N

represent the width and height, xi, yi ∈ R≥0 the coordinates of the lower left corner and

oi ∈ {0, 1} models the orientation of rectangle ri; W,H ∈ R≥0 represent the width and

height of the container with upper bounds Wmax,Hmax. We formulate RPWO as minimal

CONSTRAINT PROGRAMMING APPROACH FOR RPWO 3

half perimeter packing problem with linear objective f := W + H:

min f subject to(RPWO)

xi + sxi ≤W, W ≤Wmax,(1)

yi + syi ≤H, H ≤ Hmax,(2)

(1− oi)wi + oihi =sxi , oiwi + (1− oi)hi = s

yi , ∀i ∈ I,(3)

(xi + sxi ≤xj) ∨ (xj + sx

j ≤ xi)(4)

∨ (yi + syi ≤yj) ∨ (yj + s

yj ≤ yi), ∀i, j ∈ I, i < j,

xi ≥ 0, yi ≥ 0, ∀i ∈ I.(5)

(1-2) ensure the rectangle containment, (3) define the size of the oriented rectangles, (4)make sure that no two overlap by arranging them left (diLj), right (diRj), below (diBj) orabove (diAj) of each other and (5) are the non-negativity constraints for the coordinatesof the rectangles.

3. Meta-CSP Model

In [8] minimal area rectangular packing with fixed orientations is approached. Instead ofsearching xi, yi, meta-variables Cij are introduced for each non-overlapping constraint. Cij

ranges in domain D(Cij) := {diLj , diRj , diBj , diAj} and represents the geometric relationbetween ri and rj. The search tree is branched over the Cij and pruned with constraintpropagation. Propagation uses incrementally maintained graphs that describe a partial so-lution. Figure 3 shows a complete solution and the corresponding packing of the rectangles.

12

3 4

12

3

4

4

4

2 3

4

2

3

2 12

3 4

12

3 4

12

3

4

4

4

2 3

4

2

3

212

3

4

4

4

2 3

4

2

3

2

Figure 3. Example for a complete meta-CSP solution and the correspond-ing packing.

A partial packing for a subset S of R is described by two sets of inequalities u + s ≤ v,Ch for the horizontal and Cv for the vertical geometric relations. Ch and Cv are encoded intwo weighted directed graphs Gh and Gv that represent the left and below precedences ofri and rj. The vertices of both graphs represent the rectangles and the edges represent thehorizontal or vertical precedences of the rectangles. The weights of the edges from j to i

are given by the size −s of rectangle ri. The edges are weighted with the negative sizesof the rectangles in order to illustrate the graph algorithms canonically. Also for a betterillustration, we introduce both a source vertex n+1 with outgoing edges to each rectanglevertex i with the rectangle size −s as edge weight and a sink vertex 0 with incoming edgesfrom each rectangle vertex i with edge weight 0. Figure 4 shows Gh and Gv for the examplein figure 3.

Then, Ch (Cv) is consistent if and only if Gh (Gv) has no negative cycle. Negative cyclescan be detected in polynomial time by checking for negative entries on the main diagonalof the all-pairs shortest path matrix Ah (Av) of Gh (Gv) [4]. Ah and Av are maintained

4 M. BERGER, M. SCHRÖDER, K.-H. KÜFER

1

2

4

3

-4

-4-4

-20

0

0

0

0

n+1

-4

-4

-3

-2

1 2

43

-2 -2

0

0 0

0

0

n+1

-2

-3-4

-21

2

4

3

-4

-4-4

-20

0

0

0

0

n+1

-4

-4

-3

-2

1

2

4

3

-4

-4-4

-20

0

0

0

0

n+1

-4

-4

-3

-2

1 2

43

-2 -2

0

0 0

0

0

n+1

-2

-3-4

-21 2

43

-2 -2

0

0 0

0

0

n+1

-2

-3-4

-21 2

43

-2 -2

0

0 0

0

0

n+1

-2

-3-4

-2

Figure 4. Precedence graphs for the example in figure 3.

during search and updated with the Floyd-Warshall algorithm in O(n3). In figure 5 weprovide the all-pairs shortest path matrices for the example in figure 3.

Ah =

∞ ∞ ∞ ∞ ∞ ∞0 ∞ ∞ ∞ ∞ ∞−4 −4 ∞ ∞ ∞ ∞0 ∞ ∞ ∞ ∞ ∞−6 −6 −2 −4 ∞ ∞−9 −9 −5 −4 −3 ∞

Av =

∞ ∞ ∞ ∞ ∞ ∞−2 ∞ ∞ −2 ∞ ∞−2 ∞ ∞ −2 ∞ ∞0 ∞ ∞ ∞ ∞ ∞0 ∞ ∞ ∞ ∞ ∞−6 −4 −3 −5 −2 ∞

Figure 5. All-pairs shortest path matrices for the example in figure 3.

Whenever a meta-variable Cij is consistently instantiated with a horizontal disjunctduring search, the distance graph Gh is extended with an edge between vertex i and j

and Floyd-Warshall is applied to update Ah. Both Gv and Av are updated analogouslywhenever Cij is instantiated with a vertical disjunct.

The acyclic directed graphs Gh and Gv can be used to determine lower bounds for boththe rectangle coordinates xi, yi and the width W and height H of the container. Thenegative shortest path length from vertex i to vertex 0 gives the lower bound. Statingthese conditions with the help of the all-pairs shortest path matrices Ah and Av we obtainthe following lower bounds,

−Ah(i, 0) ≤ xi, −Av(i, 0) ≤ yi, ∀i ∈ I,(6)

−Ah(n + 1, 0) ≤W, −Av(n + 1, 0) ≤ H.(7)

Therefore, we also have a lower bound for our objective f , i.e.

(8) −Ah(n + 1, 0)−Av(n + 1, 0) ≤ f,

where equality holds once all Cij are instantiated.Besides using Gh, Gv , Ah, Av for getting the rectangle coordinates and dimensions of the

container, these data structures allow us to efficiently detect inconsistency early and toapply several specific propagation techniques. We discuss some techniques in the followingand refer to [8] for a detailed description. With Gh, Gv , Ah, Av the following propagationtechniques are applied in O(1) during search:

Forward checking (FC) removes inconsistent values of Cij with respect to a partialassignment. To check if value {d : u + s ≤ v} ∈ D(Cij) is consistent, A(i, j) must not beless than s. The propagation rules for FC are as follows:

∀Cij : (D(Cij) = ∅ ⇒ fail)(9)

∀Cij : (∃d ∈ D(Cij) : A(i, j) < s⇒ (D(Cij)← D(Cij) \ {d}))(10)

CONSTRAINT PROGRAMMING APPROACH FOR RPWO 5

Removal of subsumed variables (RS) assigns Cij transitively implied by Cik and Ckj. Avalue {d : u+ s ≤ v} ∈ D(Cij) of Cij is satisfied if and only if the shortest path from rj tori is smaller than −s. The propagation rule for RS is as follows:

∀Cij : (∃d ∈ D(Cij) : A(j, i) ≤ −s⇒ Cij = d)(11)

In figure 6 we illustrate how negative cycles are detected by FC and in figure 7 howsubsumed variables are detected by RS.

i ji j

Figure 6. Negative cy-cle detection with for-ward checking.

i ji j

Figure 7. Detection ofsubsumed variables.

Detecting cliques of displacement (DC) is another pruning technique. Partial solutionswith cliques consisting of pairwise, horizontally or vertically, aligned rectangles whosealignment exceeds the container, lead to a dead-end. A greedy heuristic is applied to ahorizontal and vertical displacement graph to detect such cliques early.

Furthermore, to avoid symmetric solutions, symmetry breaking before and during thesearch is applied in the branch and bound of [8]. A dynamic most constrained variablefirst heuristic orders Cij of large rectangle pairs first. Those relations of Cij that requirethe minimal increase in area are selected first. In case of a tie, the relation {d : u + s ≤ v}with the least amount of slack A(i, j) − s is selected.

4. Meta-CSP Model with Orientation

To introduce orientations into the meta-CSP model, we generalize the pruning techniquesFC, RS and DC. When an oi is not assigned, we either use the minimal si = min(wi, hi)or maximal side lengths si = max(wi, hi) of ri for propagation. Figure 8 illustrates theconcept of our generalization. When an oi is assigned, we use sx

i , syi analogously to the

meta-CSP model.

Figure 8. Minimal and maximal square for rectangle ri that are used inour generalization of the propagation techniques.

We apply si for FC and si for RS. The generalized propagation rules are as follows:

∀Cij : (∃d ∈ D(Cij) : A(i, j) < si ⇒ Cij 6= d) ,(12)

∀Cij : (∃d ∈ D(Cij) : A(j, i) ≤ −si ⇒ Cij = d) .(13)

For DC, we also apply si of ri with uninstantiated oi.To strengthen propagation we propose new pruning techniques that incorporate the

orientations. We assign oi of ri which only fits into the container with a certain oi. The

6 M. BERGER, M. SCHRÖDER, K.-H. KÜFER

rules for exceeding Wmax are as follows, analogous rules follow for the lower bound yiand

Hmax:

∀i ∈ I : (xi + hi > Wmax ⇒ oi = 0) ,(14)

(xi + wi > Wmax ⇒ oi = 1) .(15)

In a similar way we assign oi of ri which can only precede rj with a certain oi. The rulefor the left precedence (diLj) is as follows, analogous rules follow for the other geometricrelations:

∀i, j ∈ I, i < j : (Cij = diLj ∧ xi + hi > xj ⇒ oi = 0) ,(16)

(Cij = diLj ∧ xi + wi > xj ⇒ oi = 1) .(17)

Conversely, an instantiated oi is propagated on xi, yi:

oi = 0⇒ xi ← min (xi,Wmax − wi) ,(18)

yi ← min (yi,Hmax − hi) .

Again, an analogous rule is applied for the instantiation oi = 1.Furthermore, we propose a symmetry breaking technique which imposes a lex-leader

constraint on equal sized rectangles by removing one horizontal and one vertical geometricrelation of the corresponding Cij. An example for a lex-leader constraint and three equalsized rectangles is illustrated in figure 9.

1

2

3

?

1

2

3

1

2

3

?

1

2

3

Figure 9. Illustration of the lex-leader constraint for three equal sizedrectangles. In the domains of C12, C13 and C23 one horizontal and onevertical disjunct is removed.

In addition to the meta-variables Cij we have to search the orientations oi. With ourgeneralization we can instantiate Cij and oi order-independently. We instantiate oi and oj

right after the meta-variable Cij has been assigned. We call this order (Cij, oi, oj). Thisordering only marginally weakens propagation compared to ordering the oi first, which iscalled the standard order (o,C) here.

To strengthen our exhaustive search method we initialize it with an upper bound onf . We obtain the bound from a feasible solution constructed by a greedy best-fit packingheuristic.

Our heuristic tries to pack all rectangles into a given container with fixed width andheight. The half perimeter of the container is initially set to W +H =

⌊

2√

∑

i∈I wihi

⌋

andis iteratively incremented until a feasible packing of all rectangle is found. In every iterationdifferent width and height pairs are tried for a given half perimeter of the container.

The greedy heuristic packs one rectangle at a time. Each subsequent rectangle ri ispacked at insertion positions where one corner of ri and its adjacent sides touch otherrectangles or the container sides. Our insertion position generalizes the normal positiondefined in [3] for two-dimensional bin packing problems.

Instead of ordering the rectangles statically, our algorithm dynamically chooses the nextbest pair of rectangle and insertion position. Similar to the touching perimeter algorithm

CONSTRAINT PROGRAMMING APPROACH FOR RPWO 7

in [5] we prefer insertion positions where the inserted rectangle shares as many sides aspossible with already packed rectangles.

5. Mixed-integer Formulation

Now we formulate RWPO as a mixed-integer program. Therefore, we have to resolvethe disjunctive non-overlapping constraints (4) through a big-M relaxation and auxiliaryvariables zk

ij ∈ {0, 1}, k = 1, . . . , 4:

xi + sxi ≤ xj + (1− z1

ij)Wmax,(19)

yi + syi ≤ yj + (1− z3

ij)Hmax,

xj + sxj ≤ xi + (1− z2

ij)Wmax,

yj + syj ≤ yi + (1− z4

ij)Hmax,

1 ≥ z1ij + z2

ij ,(20)

1 ≥ z3ij + z4

ij ,

1 ≤ z1ij + z2

ij + z3ij + z4

ij, ∀i, j ∈ I, i < j.(21)

The constraints (19) represent the linear disjuncts of the non-overlapping constraints (4),the constraints (20) assure that at most one horizontal and at most one vertical geometricrelation is implied and the constraints (21) assure that at least one geometric relationbetween any rectangle pair is implied.

The resulting MIP model and the meta-CSP model are similar in different ways. Wediscuss some similarities in the following.

Definition 1. The Critical Path Problem is to find the longest path from any source s to

any sink t in a directed acyclic graph G(V,E).

Lemma 2. The determination of lower bounds for W and H in the meta-CSP model is

equivalent to the solution of critical path problems of the following form:

max(xn+1) such that xj − xi ≤ −sxj ,∀(i, j) ∈ Eh,

and

max(yn+1) such that yj − yi ≤ −syj ,∀(i, j) ∈ Ev.

Proof. Given the property that G(V,E) is a directed acyclic graph the longest path problemcan be solved as shortest path problem with non-positive edge weights. The critical pathproblem for a directed acyclic graph G(V,E) with the source s, the sink t and non-negativeedge weights cij can be formulated as the following dual of a shortest path linear program[12]: max(πt−πs) such that shortest path optimality conditions hold: πj−πi ≤ cij , ∀(i, j) ∈E. The claim holds for πt := xn+1, πs := x0 = 0, πi := xi, πj := xj , cij := −sx

j , E := Eh

and πt := yn+1, πs := y0 = 0, πi := yi, πj := yj, cij := −syj , E := Ev, respectively. �

We now show that solving the linear relaxation of a partial solution s with fixed ori-entations in the MIP model has the same effect on the objective as solving the longestpath problems for the directed acyclic graphs of the partial solution within the meta-CSPmodel. Hence, both models provide the same lower bound for the objective function f .

Theorem 3. Let s be a partial solution for RWPO with fixed orientations, i.e. without

loss of generality oi = 0,∀i ∈ I. Then the objective function value fLP(s) for the linear

relaxation for s in the MIP model is equal to the objective function value fCP(s) resulting

from the critical path problems for the graphs Gh(V,Eh) and Gv(V,Ev) for s in the meta-

CSP model, i.e.,

fLP(s) = fCP(s).

8 M. BERGER, M. SCHRÖDER, K.-H. KÜFER

Proof. Given the partial solution s we have the following remaining linear relaxation for s

in the MIP:

min f , subject to(22)

xi + wi ≤W, ∀i ∈ I,(23)

W ≤Wmax,(24)

yi + hi ≤H, ∀i ∈ I,(25)

H ≤Hmax,(26)

xi + wi ≤xj, ∀(i, j) : z1ij = 1,(27)

xj + wj ≤xi, ∀(i, j) : z2ij = 1,(28)

yi + hi ≤yj, ∀(i, j) : z3ij = 1,(29)

yj + hj ≤yi, ∀(i, j) : z4ij = 1,(30)

xi + wi ≤xj + (1− z1ij)Wmax, ∀(i, j) : z1

ij 6= 1,(31)

xj + wj ≤xi + (1− z2ij)Wmax, ∀(i, j) : z2

ij 6= 1,(32)

yi + hi ≤yj + (1− z3ij)Hmax, ∀(i, j) : z3

ij 6= 1,(33)

yj + hj ≤yi + (1− z4ij)Hmax, ∀(i, j) : z4

ij 6= 1,(34)

1 ≤z1ij + z2

ij + z3ij + z4

ij,(35)

z1ij + z2

ij≤1,(36)

z3ij + z4

ij≤1, ∀i, j ∈ I, i < j,(37)

xi ≥0,(38)

yi ≥0, ∀i ∈ I.(39)

The containment constraints (23-26) and the non-negativity constraints (38-39) can bedisregarded in the following, as these constraints are equivalent in the MIP and meta-CSPmodel.

First, we show that fLP(s) ≤ fCP(s). Given the solution s in the meta-CSP model withfCP(s), we transform the directed acyclic graphs Gh(V,Eh) and Gv(V,Ev) to shortest pathlinear programs for W and H as described in proof of Lemma 2. These two independentshortest path problems can be subsumed to one linear program which is equivalent tothe dual linear program given by the objective (22) and the constraints (27-30). LetZIP := {zk

ij : integral in s} be all fixed binary variables that correspond to edges in the

graphs of the meta-CSP model and ZLP := {zkij : fractional in s} be all binary variables

that are not integral yet.In order to show that fLP(s) ≤ fCP(s), it remains to prove that we can consistently

assign values to ZLP that satisfy constraints (31-37) without increasing the objective func-tion fLP(s). Without loss of generality, we can either assume wi + wj ≤ W or assumehi + hj ≤ H because otherwise there is no solution for the given W and H. For the hori-zontal direction and the constraints (31,32,36) we distinguish three cases for any rectanglepair (ri, rj) where zk

ij ∈ ZLP , k ∈ {1, 2}, the analogous argumentation holds for the vertical

direction, zkij ∈ ZLP , k ∈ {3, 4} and the constraints (33,34,37):

(1) The assignment ZIP implies xi + wi ≤ xj . In this case, we can consistently extendZIP with z1

ij = 1, z2ij = 0 to satisfy the constraints (31,32,36) without increasing

fLP(s).

CONSTRAINT PROGRAMMING APPROACH FOR RPWO 9

(2) The assignment ZIP implies xj +wj ≤ xi. We can extend ZIP with z1ij = 0, z2

ij = 1

and satisfy the constraints (31,32,36) without increasing fLP(s).(3) The assignment ZIP implies xi + wi > xj and xj + wj > xi. The constraint (31)

can be transformed to inequality z1ij ≤ 1 −

xi+wi−xj

Wmax

. The constraint (32) can be

transformed to inequality z2ij ≤ 1−

xj+wj−xi

Wmax

. As xi+wi > xj and xj +wj > xi both

the termsxi+wi−xj

W≥

xi+wi−xj

Wmax

andxj+wj−xi

W≥

xj+wj−xi

Wmax

range in (0, 1). Adding

the two transformed constraints results in z1ij +z2

ij ≤ 2−wi+wj

Wmax

. The termwi+wj

W≥

wi+wj

Wmax

ranges in (0, 1] as we can assume wi + wj ≤ W without loss of generality.

Hence, by assigning z1ij = 1 −

xi+wi−xj

Wand z2

ij = min(1 −xj+wj−xi

W,

xi+wi−xj

W) we

satisfy the constraints (31,32,36) without increasing fLP(s).

Any combination of case (1) or (2) for the horizontal direction with any case of the verticaldirection satisfies constraint (35). Also, any combination of case (1) or (2) for the verticaldirection with any case of the horizontal direction satisfies constraint (35). Combiningcase (3) for the horizontal direction with case (3) for the vertical direction also satisfiesconstraint (35) for the following reasons:

• Supposexi+wi−xj

W≤ 1 −

xj+wj−xi

Wand

yi+hi−yj

H≤ 1 −

yj+hj−yi

H. Then z1

ij + z2ij +

z3ij + z4

ij = 2 > 1.

• Supposexi+wi−xj

W> 1 −

xj+wj−xi

Wand

yi+hi−yj

H≤ 1 −

yj+hj−yi

H. Then z1

ij + z2ij +

z3ij + z4

ij = 3−wi+wj

W> 1.

• Supposexi+wi−xj

W≤ 1 −

xj+wj−xi

Wand

yi+hi−yj

H> 1 −

yj+hj−yi

H. Then z1

ij + z2ij +

z3ij + z4

ij = 3−hi+hj

H> 1.

• Supposexi+wi−xj

W> 1 −

xj+wj−xi

Wand

yi+hi−yj

H> 1 −

yj+hj−yi

H. Then z1

ij + z2ij +

z3ij + z4

ij = 4−wi+wj

W−

hi+hj

H> 1.

Hence, constraint (35) is always satisfied and any consistent assignment to ZLP does notincrease fLP(s).

Now, we show that fCP(s) ≤ fLP(s). Given the partial solution s in the MIP modelwith fLP(s) we can disregard any variable of ZLP and the constraints (31-37) withoutincreasing fLP(s). We concentrate on the linear program given by the variables ZIP andbuild up the graphs Gh and Gv of the meta-CSP model. An edge e = (j, i) with edgeweight −wi is introduced in Gh whenever the corresponding variable z1

ij = 1. An edge

e = (i, j) with edge weight −wj is introduced in Gh whenever the corresponding variablez2ij = 1. Also, we introduce the source n + 1 and sink 0 as well as their in- and outgoing

edges as described in section 3. In an analogous way the graph Gv is build with regard tothe variables z3

ij and z4ij. Let Ph = (n + 1, . . . , i, . . . , 0) be a longest path in Gh and let

L(P ) its length. Then the following inequalities hold,

xi + wi ≤ xj ,∀(i, j) ∈ Ph.

This implies 0 ≤ x0 +∑

i∈Ph\{n+1} wi =∑

i∈Ph\{n+1} wi = L(Ph) ≤ xn+1 ≤W . Therefore,

the inequality W ≥ L(Ph) holds. The same argumentation holds for the graph Gv and weget the inequality H ≥ L(Pv). It follows that fLP(s) ≥W +H ≥ L(Ph)+L(Pv) = fCP(s).

In conclusion, fLP(s) ≤ fCP(s) and fCP(s) ≤ fLP(s) imply that fLP(s) = fCP(s). �

Corollary 4. It is useless to integrate the linear relaxation of the MIP model as a slave

lower bound generator within a master meta-CSP model, as both models provide the same

lower bound.

10 M. BERGER, M. SCHRÖDER, K.-H. KÜFER

6. Numerical Results

We implemented our extended meta-CSP approach with the generalized techniques inIlog Solver 6.5 and the MIP model in Ilog Cplex 11.1. For a fair comparison we appliedthe same symmetry breaking in both models. We tested the models on problem instancesof size n = 5, . . . , 27 with rectangles whose sizes are inspired by electronic devices typicallyfound in SiPs. The details of the test instances are specified in the appendix. We imposea runtime limit of 600 CPU seconds.

Table 1 shows that the variable ordering (o,C) and (Cij , oi, oj) lead to similar runtimesin many cases. However, for n = 10 and n = 15 the runtimes are significantly faster forour variable ordering (Cij , oi, oj).

Runtime CPU sec.n (Cij , oi, oj) (o,C)5 0,07 0,096 0,11 0,097 0,34 0,448 5,34 5,959 0,31 0,84

10 7,23 32,8611 – –12 – –13 125,69 104,3914 – –15 349,98 –

Table 1. Runtimes (<600CPU sec.) to prove optimal-ity for the variable ordering(Cij, oi, oj) and (o,C) with ourextended meta-CSP approach.

Runtime CPU sec.n meta-CSP MIP5 0,07 0,036 0,11 0,447 0,34 9,428 5,34 175,989 0,31 19,69

10 7,23 –11 – –12 – –13 125,69 –14 – –15 349,98 –

Table 2. Runtimes(<600 CPU sec.) toprove optimality withour extended meta-CSPapproach and with ourmixed-integer program.

Table 2 shows that our approach outperforms the MIP in proving optimality. This is dueto good initial upper bounds for f from the greedy heuristic and constraint propagationwhich shrinks the search tree. Our approach is significantly faster than the MIP whichalready fails for n ≥ 10 to find optimal solutions or to prove optimality. Our approachalso solves to optimality for n = 10, 13, 15 within the runtime limit. The solution qualityis comparable for n ≤ 21 but solutions of our approach are considerably better for n ≥ 22(see figure 10).

Furthermore, we tested our approach on a real world electronic circuit called eGrain, atiny, autonomous and functional unit with flexible communication possibilities. eGrain isdeveloped at the Fraunhofer Institute for Reliability and Microintegration (IZM), Berlin,and integrated as an SiP. Figure 11 illustrates the resulting placement of our approach.The greedy heuristic finds this placement after 83,19 CPU seconds and the exhaustivesearch could not further improve it within the runtime limit.

CONSTRAINT PROGRAMMING APPROACH FOR RPWO 11

50

75

100

125

150

175

200

225

250

Number of rectangles

f=W

+H

0

5

10

15

20

25

30

35

40

Op

tim

ali

ty g

ap

(%

)

meta-CSP 67 91 89 89 88 110 101 104 126 120 169 142 160 165 160 164 153 197 200 198 216 238 191

MIP 67 91 89 89 88 110 98 104 126 119 169 141 159 164 162 165 154 202 208 203 226 241 200

MIP Gap 0 0 0 0 0 0,9 17 23 3,9 3,6 13 18 10 18 20 25 25 27 34 29 31 33 27

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Figure 10. Values for f and optimality gap for the MIP.

7. Conclusion

We extend the meta-CSP approach to RWPO where orientations are allowed. Therefore,we are flexible enough to instantiate the Cij and oi in any order and propagate betweenCij, oi, xi and yi whenever possible. We show that the meta-CSP approach is similar to anMIP formulation but produces a smaller search tree due to constraint propagation.

In future work we will introduce a second objective for the wiring of the SiP componentsin order to use it for SiP design automation.

Acknowledgments. We are grateful to Dmitry David Polityko and Christian Richterat Fraunhofer IZM for introducing us to SiP integration, for many insightful discussionsand for providing the eGrain test instance. We also thank Sven Oliver Krumke for severalfruitful discussions on the mixed-integer program and the proof of Theorem 3. This workoriginates from the PhD activities of Martin Berger and is funded by the Fraunhofer ITWM.

References

[1] N. Beldiceanu and M. Carlsson. Sweep as a generic pruning technique applied to the non-overlappingrectangles constraint. In Proceedings of the 7th International Conference on Principles and Practice

of Constraint Programming, pages 377–391, London, UK, 2001. Springer-Verlag.[2] P. Chen and E. S. Kuh. Floorplan sizing by linear programming approximation. In DAC ’00: Pro-

ceedings of the 37th conference on Design automation, pages 468–471, New York, NY, USA, 2000.ACM.

[3] N. Christofides and C. Whitlock. An algorithm for two-dimensional cutting problems. Operations

Research, 25(1):30–44, January 1977.[4] R. Dechter, I. Meiri, and J. Pearl. Temporal constraint networks. Artificial Intelligence, 49(1-3):61–95,

1991.[5] A. Lodi. Algorithms for Two-Dimensional Bin Packing and Assignment Problems. PhD thesis, Uni-

versita di Bologna, 1999.

12 M. BERGER, M. SCHRÖDER, K.-H. KÜFER

Figure 11. Placement of our extended meta-CSP approach for the SiP eGrain.

[6] V. Maag, M. Berger, A. Winterfeld, and K.-H. Küfer. A novel non-linear approach to minimal arearectangular packing. Technical Report 126, Fraunhofer Institute for Industrial Mathematics, Septem-ber 2007.

[7] S. Martello, D. Pisinger, and D. Vigo. The three-dimensional bin packing problem. Technical report,Institute for Operations Research and the Management Sciences (INFORMS), Linthicum, Maryland,USA, 2000.

[8] M. D. Moffitt and M. E. Pollack. Optimal rectangle packing: A meta-CSP approach. In Proceedings

of the 16th International Conference on Automated Planning and Scheduling, 2006.[9] D. D. Polityko. Physikalischer Entwurf für die vertikale SiP Integration. PhD thesis, Berlin Institute

of Technology, June 2008.[10] C. Richter, D. D. Polityko, J. Hefer, S. Guttowski, H. Reichl, M. Berger, U. Nowak, and M. Schröder.

Technology aware modeling of 2.5D-SiP for automation in physical design. In Proceedings of the 9th

Electronics Packaging Technology Conference, pages 623–630, December 2007.[11] S. Watanabe and T. Hiroyasu. Multi-Objective Rectangular Packing Problem, volume 1 of Advances

in Natural Computation, chapter 24, pages 581–603. World Scientific, December 2004.[12] Laurence A. Wolsey. Integer Programming. Wiley-Interscience, New York, 1998. Keywords: optimiza-

tion, integer programming.

CONSTRAINT PROGRAMMING APPROACH FOR RPWO 13

Appendix A

In table 3 we list the test instances used in the computational evaluation of our methods.

n List of rectangles ri = (wi, hi)5 (23,16),(10,20),(10,20),(8,16),(10,20)6 (16,18),(5,10),(14,28),(14,28),(14,28),(14,28)7 (23,14),(10,20),(9,18),(10,20),(14,28),(14,28),(9,18)8 (24,13),(13,26),(10,20),(9,18),(13,26),(9,18),(9,18),(10,20)9 (12,24),(8,16),(8,16),(15,30),(15,30),(8,16),(8,16),(6,12),(6,12)

10 (13,15),(26,19),(9,18),(12,24),(12,24),(9,18),(12,24),(12,24),(14,28),(14,28)11 (24,11),(18,15),(9,18),(9,18),(9,18),(11,22),(11,22),(9,18),(9,18),(13,26),

(9,18)12 (11,21),(16,19),(10,20),(10,20),(9,18),(10,20),(11,22),(9,18),(11,22),(9,18),

(10,20),(11,22)13 (47,47),(14,25),(29,13),(5,10),(5,10),(5,10),(5,10),(5,10),(9,18),(9,18),

(5,10),(5,10),(9,18)14 (41,41),(16,13),(19,11),(22,26),(5,10),(5,10),(8,16),(5,10),(5,10),(8,16),

(8,16),(6,12),(5,10),(5,10)15 (52,52),(24,21),(27,27),(13,14),(6,12),(13,26),(13,26),(13,26),(13,26),(13,26),

(13,26),(6,12),(13,26),(6,12),(6,12)16 (47,47),(15,16),(19,26),(17,11),(8,16),(8,16),(7,14),(9,18),(8,16),(8,16),

(9,18),(9,18),(8,16),(8,16),(9,18),(7,14)17 (49,49),(16,17),(27,21),(22,21),(7,14),(7,14),(8,16),(7,14),(15,30),(8,16),

(7,14),(8,16),(7,14),(8,16),(15,30),(15,30),(7,14)18 (52,52),(12,28),(28,27),(15,23),(8,16),(7,14),(7,14),(12,24),(12,24),(8,16),

(7,14),(8,16),(12,24),(8,16),(7,14),(8,16),(8,16),(12,24)19 (52,52),(26,17),(13,22),(24,12),(17,20),(10,20),(10,20),(8,16),(7,14),(7,14),

(7,14),(8,16),(10,20),(7,14),(10,20),(10,20),(10,20),(7,14),(8,16)20 (44,44),(26,27),(20,17),(11,18),(21,18),(10,20),(10,20),(11,22),(11,22),(10,20),

(8,16),(11,22),(8,16),(11,22),(11,22),(8,16),(8,16),(8,16),(11,22),(8,16)21 (42,42),(20,20),(14,11),(25,12),(13,12),(8,16),(8,16),(12,24),(8,16),(8,16),

(8,16),(8,16),(8,16),(12,24),(8,16),(8,16),(12,24),(8,16),(8,16),(8,16),(12,24)

22 (51,51),(29,20),(24,11),(25,12),(22,13),(14,28),(14,28),(15,30),(15,30),(15,30),(5,10),(5,10),(14,28),(15,30),(15,30),(5,10),(15,30),(14,28),(5,10),(5,10),(15,30),(14,28)

23 (40,40),(18,29),(17,25),(29,19),(13,29),(23,22),(11,22),(15,30),(11,22),(11,22),(11,22),(15,30),(11,22),(15,30),(15,30),(11,22),(11,22),(15,30),(11,22),(15,30),(11,22),(11,22),(11,22)

24 (49,49),(25,18),(20,13),(10,21),(26,11),(16,28),(12,24),(13,26),(13,26),(11,22),(13,26),(11,22),(12,24),(13,26),(11,22),(12,24),(13,26),(13,26),(12,24),(11,22),(11,22),(12,24),(11,22),(11,22)

25 (49,49),(42,42),(22,16),(29,27),(13,16),(19,21),(23,24),(10,20),(15,30),(15,30),(15,30),(15,30),(7,14),(7,14),(10,20),(10,20),(10,20),(15,30),(10,20),(15,30),(10,20),(7,14),(7,14),(15,30),(7,14)

26 (45,45),(46,46),(29,23),(29,25),(11,17),(15,27),(24,18),(14,28),(12,24),(14,28),(14,28),(14,28),(14,28),(12,24),(14,28),(14,28),(12,24),(14,28),(14,28),(14,28),(12,24),(12,24),(14,28),(14,28),(12,24),(12,24)

27 (51,51),(40,40),(11,24),(23,10),(12,17),(22,13),(16,13),(6,12),(6,12),(6,12),(15,30),(6,12),(7,14),(7,14),(15,30),(7,14),(7,14),(6,12),(6,12),(6,12),(7,14),(7,14),(7,14),(15,30),(15,30),(15,30),(6,12)

Table 3. Test instances for the computational evaluation.

Published reports of the Fraunhofer ITWM

The PDF-files of the following reports are available under: www.itwm.fraunhofer.de/de/zentral__berichte/berichte

1. D. Hietel, K. Steiner, J. StruckmeierA Finite - Volume Particle Method for Compressible Flows(19 pages, 1998)

2. M. Feldmann, S. SeiboldDamage Diagnosis of Rotors: Application of Hilbert Transform and Multi-Hypothe-sis TestingKeywords: Hilbert transform, damage diagnosis, Kalman filtering, non-linear dynamics(23 pages, 1998)

3. Y. Ben-Haim, S. SeiboldRobust Reliability of Diagnostic Multi- Hypothesis Algorithms: Application to Rotating MachineryKeywords: Robust reliability, convex models, Kalman fil-tering, multi-hypothesis diagnosis, rotating machinery, crack diagnosis(24 pages, 1998)

4. F.-Th. Lentes, N. SiedowThree-dimensional Radiative Heat Transfer in Glass Cooling Processes(23 pages, 1998)

5. A. Klar, R. WegenerA hierarchy of models for multilane vehicu-lar traffic Part I: Modeling(23 pages, 1998)

Part II: Numerical and stochastic investigations(17 pages, 1998)

6. A. Klar, N. SiedowBoundary Layers and Domain Decompos-ition for Radiative Heat Transfer and Diffu-sion Equations: Applications to Glass Manu-facturing Processes(24 pages, 1998)

7. I. ChoquetHeterogeneous catalysis modelling and numerical simulation in rarified gas flows Part I: Coverage locally at equilibrium (24 pages, 1998)

8. J. Ohser, B. Steinbach, C. LangEfficient Texture Analysis of Binary Images(17 pages, 1998)

9. J. OrlikHomogenization for viscoelasticity of the integral type with aging and shrinkage(20 pages, 1998)

10. J. MohringHelmholtz Resonators with Large Aperture(21 pages, 1998)

11. H. W. Hamacher, A. SchöbelOn Center Cycles in Grid Graphs(15 pages, 1998)

12. H. W. Hamacher, K.-H. KüferInverse radiation therapy planning - a multiple objective optimisation approach(14 pages, 1999)

13. C. Lang, J. Ohser, R. HilferOn the Analysis of Spatial Binary Images(20 pages, 1999)

14. M. JunkOn the Construction of Discrete Equilibrium Distributions for Kinetic Schemes(24 pages, 1999)

15. M. Junk, S. V. Raghurame RaoA new discrete velocity method for Navier-Stokes equations(20 pages, 1999)

16. H. NeunzertMathematics as a Key to Key Technologies(39 pages (4 PDF-Files), 1999)

17. J. Ohser, K. SandauConsiderations about the Estimation of the Size Distribution in Wicksell’s Corpuscle Problem(18 pages, 1999)

18. E. Carrizosa, H. W. Hamacher, R. Klein, S. Nickel

Solving nonconvex planar location prob-lems by finite dominating setsKeywords: Continuous Location, Polyhedral Gauges, Finite Dominating Sets, Approximation, Sandwich Algo-rithm, Greedy Algorithm(19 pages, 2000)

19. A. BeckerA Review on Image Distortion MeasuresKeywords: Distortion measure, human visual system(26 pages, 2000)

20. H. W. Hamacher, M. Labbé, S. Nickel, T. Sonneborn

Polyhedral Properties of the Uncapacitated Multiple Allocation Hub Location Problem Keywords: integer programming, hub location, facility location, valid inequalities, facets, branch and cut(21 pages, 2000)

21. H. W. Hamacher, A. SchöbelDesign of Zone Tariff Systems in Public Transportation(30 pages, 2001)

22. D. Hietel, M. Junk, R. Keck, D. TeleagaThe Finite-Volume-Particle Method for Conservation Laws(16 pages, 2001)

23. T. Bender, H. Hennes, J. Kalcsics, M. T. Melo, S. Nickel

Location Software and Interface with GIS and Supply Chain ManagementKeywords: facility location, software development, geographical information systems, supply chain man-agement(48 pages, 2001)

24. H. W. Hamacher, S. A. TjandraMathematical Modelling of Evacuation Problems: A State of Art(44 pages, 2001)

25. J. Kuhnert, S. TiwariGrid free method for solving the Poisson equationKeywords: Poisson equation, Least squares method, Grid free method(19 pages, 2001)

26. T. Götz, H. Rave, D. Reinel-Bitzer, K. Steiner, H. Tiemeier

Simulation of the fiber spinning processKeywords: Melt spinning, fiber model, Lattice Boltzmann, CFD(19 pages, 2001)

27. A. Zemitis On interaction of a liquid film with an obstacleKeywords: impinging jets, liquid film, models, numeri-cal solution, shape(22 pages, 2001)

28. I. Ginzburg, K. SteinerFree surface lattice-Boltzmann method to model the filling of expanding cavities by Bingham FluidsKeywords: Generalized LBE, free-surface phenomena, interface boundary conditions, filling processes, Bing-ham viscoplastic model, regularized models(22 pages, 2001)

29. H. Neunzert»Denn nichts ist für den Menschen als Men-schen etwas wert, was er nicht mit Leiden-schaft tun kann« Vortrag anlässlich der Verleihung des Akademie preises des Landes Rheinland-Pfalz am 21.11.2001Keywords: Lehre, Forschung, angewandte Mathematik, Mehrskalenanalyse, Strömungsmechanik(18 pages, 2001)

30. J. Kuhnert, S. TiwariFinite pointset method based on the projec-tion method for simulations of the incom-pressible Navier-Stokes equationsKeywords: Incompressible Navier-Stokes equations, Meshfree method, Projection method, Particle scheme, Least squares approximation AMS subject classification: 76D05, 76M28(25 pages, 2001)

31. R. Korn, M. KrekelOptimal Portfolios with Fixed Consumption or Income StreamsKeywords: Portfolio optimisation, stochastic control, HJB equation, discretisation of control problems(23 pages, 2002)

32. M. KrekelOptimal portfolios with a loan dependent credit spreadKeywords: Portfolio optimisation, stochastic control, HJB equation, credit spread, log utility, power utility, non-linear wealth dynamics(25 pages, 2002)

33. J. Ohser, W. Nagel, K. SchladitzThe Euler number of discretized sets – on the choice of adjacency in homogeneous lattices Keywords: image analysis, Euler number, neighborhod relationships, cuboidal lattice(32 pages, 2002)

34. I. Ginzburg, K. Steiner Lattice Boltzmann Model for Free-Surface flow and Its Application to Filling Process in Casting Keywords: Lattice Boltzmann models; free-surface phe-nomena; interface boundary conditions; filling pro-cesses; injection molding; volume of fluid method; in-terface boundary conditions; advection-schemes; up-wind-schemes(54 pages, 2002)

35. M. Günther, A. Klar, T. Materne, R. WegenerMultivalued fundamental diagrams and stop and go waves for continuum traffic equationsKeywords: traffic flow, macroscopic equations, kinetic derivation, multivalued fundamental diagram, stop and go waves, phase transitions(25 pages, 2002)

36. S. Feldmann, P. Lang, D. Prätzel-WoltersParameter influence on the zeros of net-work determinantsKeywords: Networks, Equicofactor matrix polynomials, Realization theory, Matrix perturbation theory(30 pages, 2002)

37. K. Koch, J. Ohser, K. Schladitz Spectral theory for random closed sets and es-timating the covariance via frequency spaceKeywords: Random set, Bartlett spectrum, fast Fourier transform, power spectrum(28 pages, 2002)

38. D. d’Humières, I. GinzburgMulti-reflection boundary conditions for lattice Boltzmann modelsKeywords: lattice Boltzmann equation, boudary condis-tions, bounce-back rule, Navier-Stokes equation(72 pages, 2002)

39. R. KornElementare FinanzmathematikKeywords: Finanzmathematik, Aktien, Optionen, Port-folio-Optimierung, Börse, Lehrerweiterbildung, Mathe-matikunterricht(98 pages, 2002)

40. J. Kallrath, M. C. Müller, S. NickelBatch Presorting Problems: Models and Complexity ResultsKeywords: Complexity theory, Integer programming, Assigment, Logistics(19 pages, 2002)

41. J. LinnOn the frame-invariant description of the phase space of the Folgar-Tucker equation Key words: fiber orientation, Folgar-Tucker equation, in-jection molding(5 pages, 2003)

42. T. Hanne, S. Nickel A Multi-Objective Evolutionary Algorithm for Scheduling and Inspection Planning in Software Development Projects Key words: multiple objective programming, project management and scheduling, software development, evolutionary algorithms, efficient set(29 pages, 2003)

43. T. Bortfeld , K.-H. Küfer, M. Monz, A. Scherrer, C. Thieke, H. Trinkaus

Intensity-Modulated Radiotherapy - A Large Scale Multi-Criteria Programming Problem Keywords: multiple criteria optimization, representa-tive systems of Pareto solutions, adaptive triangulation, clustering and disaggregation techniques, visualization of Pareto solutions, medical physics, external beam ra-diotherapy planning, intensity modulated radiotherapy(31 pages, 2003)

44. T. Halfmann, T. WichmannOverview of Symbolic Methods in Industrial Analog Circuit Design Keywords: CAD, automated analog circuit design, sym-bolic analysis, computer algebra, behavioral modeling, system simulation, circuit sizing, macro modeling, dif-ferential-algebraic equations, index(17 pages, 2003)

45. S. E. Mikhailov, J. OrlikAsymptotic Homogenisation in Strength and Fatigue Durability Analysis of Compos-itesKeywords: multiscale structures, asymptotic homoge-nization, strength, fatigue, singularity, non-local con-ditions(14 pages, 2003)

46. P. Domínguez-Marín, P. Hansen, N. Mladenovi ́c , S. Nickel

Heuristic Procedures for Solving the Discrete Ordered Median ProblemKeywords: genetic algorithms, variable neighborhood search, discrete facility location(31 pages, 2003)

47. N. Boland, P. Domínguez-Marín, S. Nickel, J. Puerto

Exact Procedures for Solving the Discrete Ordered Median ProblemKeywords: discrete location, Integer programming(41 pages, 2003)

48. S. Feldmann, P. LangPadé-like reduction of stable discrete linear systems preserving their stability Keywords: Discrete linear systems, model reduction, stability, Hankel matrix, Stein equation(16 pages, 2003)

49. J. Kallrath, S. NickelA Polynomial Case of the Batch Presorting Problem Keywords: batch presorting problem, online optimization, competetive analysis, polynomial algorithms, logistics(17 pages, 2003)

50. T. Hanne, H. L. TrinkausknowCube for MCDM – Visual and Interactive Support for Multicriteria Decision MakingKey words: Multicriteria decision making, knowledge management, decision support systems, visual interfac-es, interactive navigation, real-life applications.(26 pages, 2003)

51. O. Iliev, V. LaptevOn Numerical Simulation of Flow Through Oil FiltersKeywords: oil filters, coupled flow in plain and porous media, Navier-Stokes, Brinkman, numerical simulation(8 pages, 2003)

52. W. Dörfler, O. Iliev, D. Stoyanov, D. VassilevaOn a Multigrid Adaptive Refinement Solver for Saturated Non-Newtonian Flow in Porous MediaKeywords: Nonlinear multigrid, adaptive refinement, non-Newtonian flow in porous media(17 pages, 2003)

53. S. KruseOn the Pricing of Forward Starting Options under Stochastic VolatilityKeywords: Option pricing, forward starting options, Heston model, stochastic volatility, cliquet options(11 pages, 2003)

54. O. Iliev, D. StoyanovMultigrid – adaptive local refinement solver for incompressible flowsKeywords: Navier-Stokes equations, incompressible flow, projection-type splitting, SIMPLE, multigrid methods, adaptive local refinement, lid-driven flow in a cavity (37 pages, 2003)

55. V. Starikovicius The multiphase flow and heat transfer in porous media Keywords: Two-phase flow in porous media, various formulations, global pressure, multiphase mixture mod-el, numerical simulation(30 pages, 2003)

56. P. Lang, A. Sarishvili, A. WirsenBlocked neural networks for knowledge ex-traction in the software development processKeywords: Blocked Neural Networks, Nonlinear Regres-sion, Knowledge Extraction, Code Inspection(21 pages, 2003)

57. H. Knaf, P. Lang, S. Zeiser Diagnosis aiding in Regulation Thermography using Fuzzy Logic Keywords: fuzzy logic,knowledge representation, expert system(22 pages, 2003)

58. M. T. Melo, S. Nickel, F. Saldanha da GamaLarge scale models for dynamic multi-commodity capacitated facility location Keywords: supply chain management, strategic planning, dynamic location, modeling(40 pages, 2003)

59. J. Orlik Homogenization for contact problems with periodically rough surfacesKeywords: asymptotic homogenization, contact problems(28 pages, 2004)

60. A. Scherrer, K.-H. Küfer, M. Monz, F. Alonso, T. Bortfeld

IMRT planning on adaptive volume struc-tures – a significant advance of computa-tional complexityKeywords: Intensity-modulated radiation therapy (IMRT), inverse treatment planning, adaptive volume structures, hierarchical clustering, local refinement, adaptive clustering, convex programming, mesh gener-ation, multi-grid methods(24 pages, 2004)

61. D. KehrwaldParallel lattice Boltzmann simulation of complex flowsKeywords: Lattice Boltzmann methods, parallel com-puting, microstructure simulation, virtual material de-sign, pseudo-plastic fluids, liquid composite moulding(12 pages, 2004)

62. O. Iliev, J. Linn, M. Moog, D. Niedziela, V. Starikovicius

On the Performance of Certain Iterative Solvers for Coupled Systems Arising in Dis-cretization of Non-Newtonian Flow Equa-tionsKeywords: Performance of iterative solvers, Precondi-tioners, Non-Newtonian flow(17 pages, 2004)

63. R. Ciegis, O. Iliev, S. Rief, K. Steiner On Modelling and Simulation of Different Regimes for Liquid Polymer Moulding Keywords: Liquid Polymer Moulding, Modelling, Simu-lation, Infiltration, Front Propagation, non-Newtonian flow in porous media (43 pages, 2004)

64. T. Hanne, H. NeuSimulating Human Resources in Software Development ProcessesKeywords: Human resource modeling, software pro-cess, productivity, human factors, learning curve(14 pages, 2004)

65. O. Iliev, A. Mikelic, P. PopovFluid structure interaction problems in de-formable porous media: Toward permeabil-ity of deformable porous mediaKeywords: fluid-structure interaction, deformable po-rous media, upscaling, linear elasticity, stokes, finite el-ements(28 pages, 2004)

66. F. Gaspar, O. Iliev, F. Lisbona, A. Naumovich, P. Vabishchevich

On numerical solution of 1-D poroelasticity equations in a multilayered domainKeywords: poroelasticity, multilayered material, finite volume discretization, MAC type grid(41 pages, 2004)

67. J. Ohser, K. Schladitz, K. Koch, M. NötheDiffraction by image processing and its ap-plication in materials scienceKeywords: porous microstructure, image analysis, ran-dom set, fast Fourier transform, power spectrum, Bartlett spectrum(13 pages, 2004)

68. H. NeunzertMathematics as a Technology: Challenges for the next 10 YearsKeywords: applied mathematics, technology, modelling, simulation, visualization, optimization, glass processing, spinning processes, fiber-fluid interaction, trubulence effects, topological optimization, multicriteria optimiza-tion, Uncertainty and Risk, financial mathematics, Mal-liavin calculus, Monte-Carlo methods, virtual material design, filtration, bio-informatics, system biology(29 pages, 2004)

69. R. Ewing, O. Iliev, R. Lazarov, A. NaumovichOn convergence of certain finite difference discretizations for 1 D poroelasticity inter-face problems Keywords: poroelasticity, multilayered material, finite volume discretizations, MAC type grid, error estimates (26 pages,2004)

70. W. Dörfler, O. Iliev, D. Stoyanov, D. Vassileva On Efficient Simulation of Non-Newto-nian Flow in Saturated Porous Media with a Multigrid Adaptive Refinement Solver Keywords: Nonlinear multigrid, adaptive renement, non-Newtonian in porous media(25 pages, 2004)

71. J. Kalcsics, S. Nickel, M. Schröder Towards a Unified Territory Design Approach – Applications, Algorithms and GIS IntegrationKeywords: territory desgin, political districting, sales territory alignment, optimization algorithms, Geo-graphical Information Systems(40 pages, 2005)

72. K. Schladitz, S. Peters, D. Reinel-Bitzer, A. Wiegmann, J. Ohser

Design of acoustic trim based on geometric modeling and flow simulation for non-woven Keywords: random system of fibers, Poisson line pro-cess, flow resistivity, acoustic absorption, Lattice-Boltzmann method, non-woven(21 pages, 2005)

73. V. Rutka, A. WiegmannExplicit Jump Immersed Interface Method for virtual material design of the effective elastic moduli of composite materials Keywords: virtual material design, explicit jump im-mersed interface method, effective elastic moduli, composite materials(22 pages, 2005)

74. T. HanneEine Übersicht zum Scheduling von BaustellenKeywords: Projektplanung, Scheduling, Bauplanung, Bauindustrie(32 pages, 2005)

75. J. LinnThe Folgar-Tucker Model as a Differetial Algebraic System for Fiber Orientation Calculation Keywords: fiber orientation, Folgar–Tucker model, in-variants, algebraic constraints, phase space, trace sta-bility(15 pages, 2005)

76. M. Speckert, K. Dreßler, H. Mauch, A. Lion, G. J. Wierda

Simulation eines neuartigen Prüf systems für Achserprobungen durch MKS-Model-lierung einschließlich RegelungKeywords: virtual test rig, suspension testing, multibody simulation, modeling hexapod test rig, opti-mization of test rig configuration(20 pages, 2005)

77. K.-H. Küfer, M. Monz, A. Scherrer, P. Süss, F. Alonso, A. S. A. Sultan, Th. Bortfeld, D. Craft, Chr. Thieke

Multicriteria optimization in intensity modulated radiotherapy planning Keywords: multicriteria optimization, extreme solu-tions, real-time decision making, adaptive approxima-tion schemes, clustering methods, IMRT planning, re-verse engineering (51 pages, 2005)

78. S. Amstutz, H. Andrä A new algorithm for topology optimization using a level-set methodKeywords: shape optimization, topology optimization, topological sensitivity, level-set(22 pages, 2005)

79. N. EttrichGeneration of surface elevation models for urban drainage simulationKeywords: Flooding, simulation, urban elevation models, laser scanning(22 pages, 2005)

80. H. Andrä, J. Linn, I. Matei, I. Shklyar, K. Steiner, E. Teichmann

OPTCAST – Entwicklung adäquater Struk-turoptimierungsverfahren für Gießereien Technischer Bericht (KURZFASSUNG)Keywords: Topologieoptimierung, Level-Set-Methode, Gießprozesssimulation, Gießtechnische Restriktionen, CAE-Kette zur Strukturoptimierung(77 pages, 2005)

81. N. Marheineke, R. WegenerFiber Dynamics in Turbulent Flows Part I: General Modeling Framework Keywords: fiber-fluid interaction; Cosserat rod; turbu-lence modeling; Kolmogorov’s energy spectrum; dou-ble-velocity correlations; differentiable Gaussian fields(20 pages, 2005)

Part II: Specific Taylor Drag Keywords: flexible fibers; k-e turbulence model; fi-ber-turbulence interaction scales; air drag; random Gaussian aerodynamic force; white noise; stochastic differential equations; ARMA process (18 pages, 2005)

82. C. H. Lampert, O. Wirjadi An Optimal Non-Orthogonal Separation of the Anisotropic Gaussian Convolution FilterKeywords: Anisotropic Gaussian filter, linear filtering, ori-entation space, nD image processing, separable filters(25 pages, 2005)

83. H. Andrä, D. StoyanovError indicators in the parallel finite ele-ment solver for linear elasticity DDFEM Keywords: linear elasticity, finite element method, hier-archical shape functions, domain decom-position, par-allel implementation, a posteriori error estimates(21 pages, 2006)

84. M. Schröder, I. SolchenbachOptimization of Transfer Quality in Regional Public TransitKeywords: public transit, transfer quality, quadratic assignment problem(16 pages, 2006)

85. A. Naumovich, F. J. Gaspar On a multigrid solver for the three-dimen-sional Biot poroelasticity system in multi-layered domains Keywords: poroelasticity, interface problem, multigrid, operator-dependent prolongation(11 pages, 2006)

86. S. Panda, R. Wegener, N. MarheinekeSlender Body Theory for the Dynamics of Curved Viscous Fibers Keywords: curved viscous fibers; fluid dynamics; Navier-Stokes equations; free boundary value problem; asymp-totic expansions; slender body theory(14 pages, 2006)

87. E. Ivanov, H. Andrä, A. KudryavtsevDomain Decomposition Approach for Auto-matic Parallel Generation of Tetrahedral GridsKey words: Grid Generation, Unstructured Grid, Delau-nay Triangulation, Parallel Programming, Domain De-composition, Load Balancing(18 pages, 2006)

88. S. Tiwari, S. Antonov, D. Hietel, J. Kuhnert, R. Wegener

A Meshfree Method for Simulations of In-teractions between Fluids and Flexible StructuresKey words: Meshfree Method, FPM, Fluid Structure Interaction, Sheet of Paper, Dynamical Coupling(16 pages, 2006)

89. R. Ciegis , O. Iliev, V. Starikovicius, K. SteinerNumerical Algorithms for Solving Problems of Multiphase Flows in Porous MediaKeywords: nonlinear algorithms, finite-volume method, software tools, porous media, flows(16 pages, 2006)

90. D. Niedziela, O. Iliev, A. LatzOn 3D Numerical Simulations of Viscoelastic FluidsKeywords: non-Newtonian fluids, anisotropic viscosity, integral constitutive equation (18 pages, 2006)

91. A. WinterfeldApplication of general semi-infinite Pro-gramming to Lapidary Cutting ProblemsKeywords: large scale optimization, nonlinear program-ming, general semi-infinite optimization, design center-ing, clustering(26 pages, 2006)

92. J. Orlik, A. OstrovskaSpace-Time Finite Element Approximation and Numerical Solution of Hereditary Linear Viscoelasticity ProblemsKeywords: hereditary viscoelasticity; kern approxima-tion by interpolation; space-time finite element approx-imation, stability and a priori estimate(24 pages, 2006)

93. V. Rutka, A. Wiegmann, H. AndräEJIIM for Calculation of effective Elastic Moduli in 3D Linear ElasticityKeywords: Elliptic PDE, linear elasticity, irregular do-main, finite differences, fast solvers, effective elas-tic moduli(24 pages, 2006)

94. A. Wiegmann, A. ZemitisEJ-HEAT: A Fast Explicit Jump Harmonic Averaging Solver for the Effective Heat Conductivity of Composite MaterialsKeywords: Stationary heat equation, effective ther-mal conductivity, explicit jump, discontinuous coeffi-cients, virtual material design, microstructure simula-tion, EJ-HEAT(21 pages, 2006)

95. A. NaumovichOn a finite volume discretization of the three-dimensional Biot poroelasticity sys-tem in multilayered domainsKeywords: Biot poroelasticity system, interface problems, finite volume discretization, finite difference method(21 pages, 2006)

96. M. Krekel, J. WenzelA unified approach to Credit Default Swap-tion and Constant Maturity Credit Default Swap valuationKeywords: LIBOR market model, credit risk, Credit De-fault Swaption, Constant Maturity Credit Default Swap-method(43 pages, 2006)

97. A. DreyerInterval Methods for Analog CirciutsKeywords: interval arithmetic, analog circuits, tolerance analysis, parametric linear systems, frequency response, symbolic analysis, CAD, computer algebra(36 pages, 2006)

98. N. Weigel, S. Weihe, G. Bitsch, K. DreßlerUsage of Simulation for Design and Optimi-zation of TestingKeywords: Vehicle test rigs, MBS, control, hydraulics, testing philosophy(14 pages, 2006)

99. H. Lang, G. Bitsch, K. Dreßler, M. SpeckertComparison of the solutions of the elastic and elastoplastic boundary value problemsKeywords: Elastic BVP, elastoplastic BVP, variational inequalities, rate-independency, hysteresis, linear kine-matic hardening, stop- and play-operator(21 pages, 2006)

100. M. Speckert, K. Dreßler, H. MauchMBS Simulation of a hexapod based sus-pension test rigKeywords: Test rig, MBS simulation, suspension, hydraulics, controlling, design optimization(12 pages, 2006)

101. S. Azizi Sultan, K.-H. KüferA dynamic algorithm for beam orientations in multicriteria IMRT planningKeywords: radiotherapy planning, beam orientation optimization, dynamic approach, evolutionary algo-rithm, global optimization(14 pages, 2006)

102. T. Götz, A. Klar, N. Marheineke, R. WegenerA Stochastic Model for the Fiber Lay-down Process in the Nonwoven ProductionKeywords: fiber dynamics, stochastic Hamiltonian sys-tem, stochastic averaging(17 pages, 2006)

103. Ph. Süss, K.-H. KüferBalancing control and simplicity: a variable aggregation method in intensity modulated radiation therapy planningKeywords: IMRT planning, variable aggregation, clus-tering methods (22 pages, 2006)

104. A. Beaudry, G. Laporte, T. Melo, S. NickelDynamic transportation of patients in hos-pitalsKeywords: in-house hospital transportation, dial-a-ride, dynamic mode, tabu search (37 pages, 2006)

105. Th. HanneApplying multiobjective evolutionary algo-rithms in industrial projectsKeywords: multiobjective evolutionary algorithms, dis-crete optimization, continuous optimization, electronic circuit design, semi-infinite programming, scheduling(18 pages, 2006)

106. J. Franke, S. HalimWild bootstrap tests for comparing signals and imagesKeywords: wild bootstrap test, texture classification, textile quality control, defect detection, kernel estimate, nonparametric regression(13 pages, 2007)

107. Z. Drezner, S. NickelSolving the ordered one-median problem in the planeKeywords: planar location, global optimization, ordered median, big triangle small triangle method, bounds, numerical experiments(21 pages, 2007)

108. Th. Götz, A. Klar, A. Unterreiter, R. Wegener

Numerical evidance for the non- existing of solutions of the equations desribing rota-tional fiber spinningKeywords: rotational fiber spinning, viscous fibers, boundary value problem, existence of solutions(11 pages, 2007)

109. Ph. Süss, K.-H. KüferSmooth intensity maps and the Bortfeld-Boyer sequencerKeywords: probabilistic analysis, intensity modulated radiotherapy treatment (IMRT), IMRT plan application, step-and-shoot sequencing(8 pages, 2007)

110. E. Ivanov, O. Gluchshenko, H. Andrä, A. Kudryavtsev

Parallel software tool for decomposing and meshing of 3d structuresKeywords: a-priori domain decomposition, unstruc-tured grid, Delaunay mesh generation(14 pages, 2007)

111. O. Iliev, R. Lazarov, J. WillemsNumerical study of two-grid precondition-ers for 1d elliptic problems with highly oscillating discontinuous coefficientsKeywords: two-grid algorithm, oscillating coefficients, preconditioner (20 pages, 2007)

112. L. Bonilla, T. Götz, A. Klar, N. Marheineke, R. Wegener

Hydrodynamic limit of the Fokker-Planck-equation describing fiber lay-down pro-cessesKeywords: stochastic dierential equations, Fokker-Planck equation, asymptotic expansion, Ornstein-Uhlenbeck process(17 pages, 2007)

113. S. RiefModeling and simulation of the pressing section of a paper machineKeywords: paper machine, computational fluid dynam-ics, porous media(41 pages, 2007)

114. R. Ciegis, O. Iliev, Z. LakdawalaOn parallel numerical algorithms for simu-lating industrial filtration problemsKeywords: Navier-Stokes-Brinkmann equations, finite volume discretization method, SIMPLE, parallel comput-ing, data decomposition method (24 pages, 2007)

115. N. Marheineke, R. WegenerDynamics of curved viscous fibers with sur-face tensionKeywords: Slender body theory, curved viscous bers with surface tension, free boundary value problem(25 pages, 2007)

116. S. Feth, J. Franke, M. SpeckertResampling-Methoden zur mse-Korrektur und Anwendungen in der BetriebsfestigkeitKeywords: Weibull, Bootstrap, Maximum-Likelihood, Betriebsfestigkeit(16 pages, 2007)

117. H. KnafKernel Fisher discriminant functions – a con-cise and rigorous introductionKeywords: wild bootstrap test, texture classification, textile quality control, defect detection, kernel estimate, nonparametric regression(30 pages, 2007)

118. O. Iliev, I. RybakOn numerical upscaling for flows in hetero-geneous porous mediaKeywords: numerical upscaling, heterogeneous porous media, single phase flow, Darcy‘s law, multiscale prob-lem, effective permeability, multipoint flux approxima-tion, anisotropy(17 pages, 2007)

119. O. Iliev, I. RybakOn approximation property of multipoint flux approximation methodKeywords: Multipoint flux approximation, finite volume method, elliptic equation, discontinuous tensor coeffi-cients, anisotropy(15 pages, 2007)

120. O. Iliev, I. Rybak, J. WillemsOn upscaling heat conductivity for a class of industrial problemsKeywords: Multiscale problems, effective heat conduc-tivity, numerical upscaling, domain decomposition(21 pages, 2007)

121. R. Ewing, O. Iliev, R. Lazarov, I. RybakOn two-level preconditioners for flow in porous mediaKeywords: Multiscale problem, Darcy‘s law, single phase flow, anisotropic heterogeneous porous media, numerical upscaling, multigrid, domain decomposition, efficient preconditioner(18 pages, 2007)

122. M. Brickenstein, A. DreyerPOLYBORI: A Gröbner basis framework for Boolean polynomialsKeywords: Gröbner basis, formal verification, Boolean polynomials, algebraic cryptoanalysis, satisfiability(23 pages, 2007)

123. O. WirjadiSurvey of 3d image segmentation methodsKeywords: image processing, 3d, image segmentation, binarization(20 pages, 2007)

124. S. Zeytun, A. GuptaA Comparative Study of the Vasicek and the CIR Model of the Short RateKeywords: interest rates, Vasicek model, CIR-model, calibration, parameter estimation(17 pages, 2007)

125. G. Hanselmann, A. Sarishvili Heterogeneous redundancy in software quality prediction using a hybrid Bayesian approachKeywords: reliability prediction, fault prediction, non-homogeneous poisson process, Bayesian model aver-aging(17 pages, 2007)

126. V. Maag, M. Berger, A. Winterfeld, K.-H. Küfer

A novel non-linear approach to minimal area rectangular packingKeywords: rectangular packing, non-overlapping con-straints, non-linear optimization, regularization, relax-ation (18 pages, 2007)

127. M. Monz, K.-H. Küfer, T. Bortfeld, C. Thieke Pareto navigation – systematic multi-criteria-based IMRT treatment plan determinationKeywords: convex, interactive multi-objective optimiza-tion, intensity modulated radiotherapy planning(15 pages, 2007)

128. M. Krause, A. ScherrerOn the role of modeling parameters in IMRT plan optimizationKeywords: intensity-modulated radiotherapy (IMRT), inverse IMRT planning, convex optimization, sensitiv-ity analysis, elasticity, modeling parameters, equivalent uniform dose (EUD)(18 pages, 2007)

129. A. WiegmannComputation of the permeability of porous materials from their microstructure by FFF-StokesKeywords: permeability, numerical homogenization, fast Stokes solver(24 pages, 2007)

130. T. Melo, S. Nickel, F. Saldanha da GamaFacility Location and Supply Chain Manage-ment – A comprehensive reviewKeywords: facility location, supply chain management, network design(54 pages, 2007)

131. T. Hanne, T. Melo, S. NickelBringing robustness to patient flow manage ment through optimized patient transports in hospitalsKeywords: Dial-a-Ride problem, online problem, case study, tabu search, hospital logistics (23 pages, 2007)

132. R. Ewing, O. Iliev, R. Lazarov, I. Rybak, J. Willems

An efficient approach for upscaling proper-ties of composite materials with high con-trast of coefficientsKeywords: effective heat conductivity, permeability of fractured porous media, numerical upscaling, fibrous insulation materials, metal foams(16 pages, 2008)

133. S. Gelareh, S. NickelNew approaches to hub location problems in public transport planningKeywords: integer programming, hub location, trans-portation, decomposition, heuristic(25 pages, 2008)

134. G. Thömmes, J. Becker, M. Junk, A. K. Vai-kuntam, D. Kehrwald, A. Klar, K. Steiner, A. Wiegmann

A Lattice Boltzmann Method for immiscible multiphase flow simulations using the Level Set MethodKeywords: Lattice Boltzmann method, Level Set method, free surface, multiphase flow(28 pages, 2008)

135. J. OrlikHomogenization in elasto-plasticityKeywords: multiscale structures, asymptotic homogeni-zation, nonlinear energy (40 pages, 2008)

136. J. Almquist, H. Schmidt, P. Lang, J. Deitmer, M. Jirstrand, D. Prätzel-Wolters, H. Becker

Determination of interaction between MCT1 and CAII via a mathematical and physiological approachKeywords: mathematical modeling; model reduction; electrophysiology; pH-sensitive microelectrodes; pro-ton antenna (20 pages, 2008)

137. E. Savenkov, H. Andrä, O. Iliev∗An analysis of one regularization approach for solution of pure Neumann problemKeywords: pure Neumann problem, elasticity, regular-ization, finite element method, condition number(27 pages, 2008)

138. O. Berman, J. Kalcsics, D. Krass, S. NickelThe ordered gradual covering location problem on a networkKeywords: gradual covering, ordered median function, network location(32 pages, 2008)

139. S. Gelareh, S. NickelMulti-period public transport design: A novel model and solution approachesKeywords: Integer programming, hub location, public transport, multi-period planning, heuristics(31 pages, 2008)

140. T. Melo, S. Nickel, F. Saldanha-da-GamaNetwork design decisions in supply chainplanningKeywords: supply chain design, integer programming models, location models, heuristics(20 pages, 2008)

141. C. Lautensack, A. Särkkä, J. Freitag, K. Schladitz

Anisotropy analysis of pressed point pro-cessesKeywords: estimation of compression, isotropy test, nearest neighbour distance, orientation analysis, polar ice, Ripley’s K function(35 pages, 2008)

142. O. Iliev, R. Lazarov, J. WillemsA Graph-Laplacian approach for calculating the effective thermal conductivity of com-plicated fiber geometriesKeywords: graph laplacian, effective heat conductivity, numerical upscaling, fibrous materials(14 pages, 2008)

143. J. Linn, T. Stephan, J. Carlsson, R. BohlinFast simulation of quasistatic rod deforma-tions for VR applicationsKeywords: quasistatic deformations, geometrically exact rod models, variational formulation, energy min-imization, finite differences, nonlinear conjugate gra-dients(7 pages, 2008)

144. J. Linn, T. StephanSimulation of quasistatic deformations us-ing discrete rod modelsKeywords: quasistatic deformations, geometrically exact rod models, variational formulation, energy min-imization, finite differences, nonlinear conjugate gra-dients(9 pages, 2008)

145. J. Marburger, N. Marheineke, R. PinnauAdjoint based optimal control using mesh-less discretizationsKeywords: Mesh-less methods, particle methods, Eul-erian-Lagrangian formulation, optimization strategies, adjoint method, hyperbolic equations(14 pages, 2008

146. S. Desmettre, J. Gould, A. Szimayer

Own-company stockholding and work effort preferences of an unconstrained executiveKeywords: optimal portfolio choice, executive compen-sation(33 pages, 2008)

147. M. Berger, M. schröder, K.-H. KüferA constraint programming approach for the two-dimensional rectangular packing prob-lem with orthogonal orientationsKeywords: rectangular packing, orthogonal orienta-tions non-overlapping constraints, constraint propa-gation(13 pages, 2008)

Status quo: October 2008