text: Density and Level Set-XFEM Schemes for Topology Optimization of 3-D Structures 17 Initial design Strain energy Density ratio Strain energy SIMP 1.3321e+03 E = 0.50E 4.4081e-05 XFEM B A XFEM 1.3185e+03 E = 0.10E 6.2862e-05 SIMP B A E = 0.01E 7.8627e-05 B A Table 7: Strain energy for the cuboid under torsion op- EB is void 7.6721e-05 E = 0.50E 4.3221e-05 timization problem with XFEM and a perimeter con- B A E = 0.10E 5.9192e-05 straint. XFEM B A E = 0.01E 6.4448e-05 B A E is void 6.6283e-05 B Table 8: Two-phase topology optimization using SIMP and XFEM. × × domain is discretized by 120 30 30 elements. Because of the symmetry condition, only one half of the cuboid is numerically analyzed. We compare the SIMP and LSM- XFEM results. The optimization problem is solved by a SIMP ap- Fig. 19: Initial setup for the long cantilever beam two- proach with a penalization factor of p = 3, a smooth- phase problem. × ing radius of r = 0.05333 (1.6 the element edge) ρ and the projection parameter of β = 0. The design do- straint does not prevent the formation of thin walls in main is initialized with a uniform material distribution the upper half. The thickness of the walls in the up- of ρi = 0.3. The optimized material distributions are per half of the design is 0.0188. Thus, the perimeter shown in Fig. 20 where material with a density lower constraint does not control the local feature size. The than ρi < 0.25 is transparent. The strain energies are design in Fig. 18(a) resembles closely the SIMP result reported in Tab. 8. from which it was restarted. However, considering the The LSM-XFEM results for a smoothing radius of × strain energy in Tab. 7, this design has a larger strain r = 0.05333 (1.6 the element edge) are shown in φ energy than the one in Fig. 18(b). Fig. 20 and the strain energies are given in Tab. 8. The study above has shown that neither smoothing Considering the full design domain, the level set ﬁeld × × the level set ﬁeld nor imposing a perimeter constraint is initialized with a 16 4 4 array of equally spaced allows controlling the minimum feature size. Further, holes with radius of 0.1050. The initial design is shown the eﬀect of a perimeter constraint is non-intuitive as in Fig. 1 and satisﬁes the volume constraint for the stiﬀ the result in Fig. 18(b) shows. The design has more phase. Note that the interface condition is enforced via structural features than the design without perimeter the stabilized Lagrange multiplier method (5) with an constraint in Fig. 14(b). element wise constant Lagrange multiplier, λ, and a 6.3 Two-phase Cantilevered Beam Design consistency factor of γ = 10 (EA + EB). Comparing the SIMP and LSM-XFEM results, the The examples in the two previous subsections were same trends can be observed for this “solid-solid” prob- concerned with “solid-void” problems. Here we study a lem as for the “solid-void” ones studied earlier. The “solid-solid” problem to demonstrate the applicability LSM-XFEM approach leads to three dimensional struc- of the proposed LSM-XFEM approach to this class of tures with thinner walls and higher stiﬀness. In con- problems. Note that the simpliﬁed XFEM formulation trast, the SIMP method generates truss-type structures, discussed in Section is not applicable to such problems. in particular if the discretization is too coarse and the The generalized enrichment strategy of Section is re- optimum wall thickness is less than the size of an ele- quired and the interface conditions of Eq. 5 need to be ment. satisﬁed. For illustration purposes only, we show a realization × × We study the optimal two-phase layout of a 4 1 1 of the LSM-XFEM optimized design for E = 0.1E B A cantilevered beam subject to a tip load; see Fig. 19. in Fig. 21. The structure was fabricated with a poly- The stiﬀ phase “A” has Young’s modulus of E = 1.0; jet 3D printing process on a Connex Objet 260 printer. A three values of Young’s moduli for the soft phase are White material represents phase “A”, black represents considered: E = [0.5, 0.1, 0.01]. Both phases have a phase “B”. The left and center pieces show the indi- B Poisson ratio of 0.3. The maximum volume of the stiﬀ vidual phases printed separately, the printed two-phase phase is limited to 30% of the total volume. The design design is shown on the right. ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Density

label: title

text: and

text: Level

text: Set-XFEM

text: Schemes

text: for

text: Topology

text: Optimization

text: of

text: Structures

text: Initial

label: table

text: design

text: Strain

text: energy

text: Density

text: ratio

text: Strain

text: energy

text: SIMP

text: E

text: XFEM

text: B

text: A

text: XFEM

text: E

text: SIMP

text: B

text: A

text: E

text: B

text: A

text: Table

text: Strain

text: energy

text: for

text: the

text: cuboid

text: under

text: torsion

text: op-

text: EB

text: is

text: void

text: E

text: timization

text: problem

text: with

text: XFEM

text: and

text: a

text: perimeter

text: con-

text: B

text: A

text: E

text: straint.

text: XFEM

text: B

text: A

text: E

text: B

text: A

text: E

text: is

text: void

text: B

text: Table

text: Two-phase

text: topology

text: optimization

text: using

text: SIMP

text: and

text: XFEM.

text: domain

text: is

text: discretized

text: by

text: elements.

text: Because

text: of

text: the

text: symmetry

text: condition,

text: only

text: one

text: half

text: of

text: the

text: cuboid

text: is

text: numerically

text: analyzed.

text: We

text: compare

text: the

text: SIMP

text: and

text: LSM-

text: XFEM

text: results.

text: The

text: optimization

text: problem

text: is

text: solved

text: by

text: a

text: SIMP

text: ap-

text: Fig.

text: Initial

text: setup

text: for

text: the

text: long

text: cantilever

text: beam

text: two-

text: proach

text: with

text: a

text: penalization

text: factor

text: of

text: p

text: a

text: smooth-

text: phase

text: problem.

text: ing

text: radius

text: of

text: r

text: the

text: element

text: edge)

text: ρ

text: and

text: the

text: projection

text: parameter

text: of

text: β

text: The

text: design

text: do-

text: straint

text: does

text: not

text: prevent

text: the

text: formation

text: of

text: thin

text: walls

text: in

text: main

text: is

text: initialized

text: with

text: a

text: uniform

text: material

text: distribution

text: the

text: upper

text: half.

text: The

text: thickness

text: of

text: the

text: walls

text: in

text: the

text: up-

text: of

text: ρi

text: The

text: optimized

text: material

text: distributions

text: are

text: per

text: half

text: of

text: the

text: design

text: is

text: Thus,

text: the

text: perimeter

text: shown

text: in

text: Fig.

text: where

text: material

text: with

text: a

text: density

text: lower

text: constraint

text: does

text: not

text: control

text: the

text: local

text: feature

text: size.

text: The

text: than

text: ρi

text: is

text: transparent.

text: The

text: strain

text: energies

text: are

text: design

text: in

text: Fig.

text: resembles

text: closely

text: the

text: SIMP

text: result

text: reported

text: in

text: Tab.

text: from

text: which

text: it

text: was

text: restarted.

text: However,

text: considering

text: the

text: The

text: LSM-XFEM

text: results

text: for

text: a

text: smoothing

text: radius

text: of

text: strain

text: energy

text: in

text: Tab.

text: this

text: design

text: has

text: a

text: larger

text: strain

text: r

text: the

text: element

text: edge)

text: are

text: shown

text: in

text: φ

text: energy

text: than

text: the

text: one

text: in

text: Fig.

text: Fig.

text: and

text: the

text: strain

text: energies

text: are

text: given

text: in

text: Tab.

text: The

text: study

text: above

text: has

text: shown

text: that

text: neither

text: smoothing

text: Considering

text: the

text: full

text: design

text: domain,

text: the

text: level

text: set

text: ﬁeld

text: the

text: level

text: set

text: ﬁeld

text: nor

text: imposing

text: a

text: perimeter

text: constraint

text: is

text: initialized

text: with

text: a

text: array

text: of

text: equally

text: spaced

text: allows

text: controlling

text: the

text: minimum

text: feature

text: size.

text: Further,

text: holes

text: with

text: radius

text: of

text: The

text: initial

text: design

text: is

text: shown

text: the

text: eﬀect

text: of

text: a

text: perimeter

text: constraint

text: is

text: non-intuitive

text: as

text: in

text: Fig.

text: and

text: satisﬁes

text: the

text: volume

text: constraint

text: for

text: the

text: stiﬀ

text: the

text: result

text: in

text: Fig.

text: shows.

text: The

text: design

text: has

text: more

text: phase.

text: Note

text: that

text: the

text: interface

text: condition

text: is

text: enforced

text: via

text: structural

text: features

text: than

text: the

text: design

text: without

text: perimeter

text: the

text: stabilized

text: Lagrange

text: multiplier

text: method

text: with

text: an

text: constraint

text: in

text: Fig.

text: element

text: wise

text: constant

text: Lagrange

text: multiplier,

text: λ,

text: and

text: a

text: Two-phase

text: Cantilevered

text: Beam

text: Design

text: consistency

text: factor

text: of

text: γ

text: (EA

text: EB).

text: Comparing

text: the

text: SIMP

text: and

text: LSM-XFEM

text: results,

text: the

text: The

text: examples

text: in

text: the

text: two

text: previous

text: subsections

text: were

text: same

text: trends

text: can

text: be

text: observed

text: for

text: this

text: “solid-solid”

text: prob-

text: concerned

text: with

text: “solid-void”

text: problems.

text: Here

text: we

text: study

text: a

text: lem

text: as

text: for

text: the

text: “solid-void”

text: ones

text: studied

text: earlier.

text: The

text: “solid-solid”

text: problem

text: to

text: demonstrate

text: the

text: applicability

text: LSM-XFEM

text: approach

text: leads

text: to

text: three

text: dimensional

text: struc-

text: of

text: the

text: proposed

text: LSM-XFEM

text: approach

text: to

text: this

text: class

text: of

text: tures

text: with

text: thinner

text: walls

text: and

text: higher

text: stiﬀness.

text: In

text: con-

text: problems.

text: Note

text: that

text: the

text: simpliﬁed

text: XFEM

text: formulation

text: trast,

text: the

text: SIMP

text: method

text: generates

text: truss-type

text: structures,

text: discussed

text: in

text: Section

text: is

text: not

text: applicable

text: to

text: such

text: problems.

text: in

text: particular

text: if

text: the

text: discretization

text: is

text: too

text: coarse

text: and

text: the

text: The

text: generalized

text: enrichment

text: strategy

text: of

text: Section

text: is

text: re-

text: optimum

text: wall

text: thickness

text: is

text: less

text: than

text: the

text: size

text: of

text: an

text: ele-

text: quired

text: and

text: the

text: interface

text: conditions

text: of

text: Eq.

text: need

text: to

text: be

text: ment.

text: satisﬁed.

text: For

text: illustration

text: purposes

text: only,

text: we

text: show

text: a

text: realization

text: We

text: study

text: the

text: optimal

text: two-phase

text: layout

text: of

text: a

text: of

text: the

text: LSM-XFEM

text: optimized

text: design

text: for

text: E

text: B

text: A

text: cantilevered

text: beam

text: subject

text: to

text: a

text: tip

text: load;

text: see

text: Fig.

text: in

text: Fig.

text: The

text: structure

text: was

text: fabricated

text: with

text: a

text: poly-

text: The

text: stiﬀ

text: phase

text: “A”

text: has

text: Young’s

text: modulus

text: of

text: E

text: jet

text: printing

text: process

text: on

text: a

text: Connex

text: Objet

text: printer.

text: A

text: three

text: values

text: of

text: Young’s

text: moduli

text: for

text: the

text: soft

text: phase

text: are

text: White

text: material

text: represents

text: phase

text: “A”,

text: black

text: represents

text: considered:

text: E

text: Both

text: phases

text: have

text: a

text: phase

text: “B”.

text: The

text: left

text: and

text: center

text: pieces

text: show

text: the

text: indi-

text: B

text: Poisson

text: ratio

text: of

text: The

text: maximum

text: volume

text: of

text: the

text: stiﬀ

text: vidual

text: phases

text: printed

text: separately,

text: the

text: printed

text: two-phase

text: phase

text: is

text: limited

text: to

text: of

text: the

text: total

text: volume.

text: The

text: design

text: design

text: is

text: shown

text: on

text: the

text: right.

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Density and Level Set-XFEM Schemes for Topology Optimization of 3-D Structures 19 Journal for Numerical Methods in Engineering 45 Guest J, Asadpoure A, Ha SH (2011) Eliminating beta- Bendsøe M (1989) Optimal shape design as a mate- continuation from heaviside projection and density rial distribution problem. Structural and Multidisci- ﬁlter algorithms. Structural and Multidisciplinary plinary Optimization 1(4):193–202 Optimization 44(4):443–453 Bendsøe MP, Sigmund O (2003) Topology Optimiza- Hansbo A, Hansbo P (2004) A ﬁnite element method tion: Theory, Methods and Applications. Springer for the simulation of strong and weak discontinuities Burger M, Hackl B, Ring W (2004) Incorporating topo- in solid mechanics. Computer Methods in Applied logical derivatives into level set methods. Journal of Mechanics and Engineering 193(33-35):3523 – 3540 Computational Physics 194(1):344–362 Heroux M, Bartlett R, Hoekstra VHR, Hu J, Kolda Deaton J, Grandhi R (2013) A survey of struc- T, Lehoucq R, Long K, Pawlowski R, Phipps E, tural and multidisciplinary continuum topol- Salinger A, Thornquist H, Tuminaro R, Willenbring ogy optimization: post 2000. Structural and J, Williams A (2003) An Overview of Trilinos. Tech. Multidisciplinary Optimization pp 1–38, URL Rep. SAND2003-2927, Sandia National Laboratories http://dx.doi.org/10.1007/s00158-013-0956-z Herrero D, Mart´ınez J, Mart´ı P (2013) An implemen- van Dijk N, Maute K, Langelaar M, Keulen F (2013) tation of level set based topology optimization using Level-set methods for structural topology optimiza- gpu. In: 10th World Congress on Structural and Mul- tion: a review. Structural and Multidisciplinary Op- tidisciplinary Optimization timization pp 1–36 Juntunen M, Stenberg R (2009) Nitsche’s method for Dolbow J, Harari I (2009) An eﬃcient ﬁnite element general boundary conditions. Mathematics of Com- method for embedded interface problems. Int J Nu- putation 78:1353–1374 mer Meth Engng 78:229–252 Kreissl S, Maute K (2012) Levelset based ﬂuid topol- Duysinx P, Miegroet L, Jacobs T, Fleury C (2006) Gen- ogy optimization using the extended ﬁnite element eralized shape optimization using x-fem and level set method. Structural and Multidisciplinary Optimiza- methods. In: IUTAM Symposium on Topological De- tion pp 1–16 sign Optimization of Structures, Machines and Ma- Lang C, Makhija D, Doostan A, Maute K (2013) terials, Springer, pp 23–32 A simple and eﬃcient preconditioning scheme for Eschenauer H, Kobelev V, Schumacher A (1994) Bub- xfem with heaviside enrichments. Computational ble method for topology and shape optimization of Mechancis structures. Structural and Multidisciplinary Opti- Lee P, Yang R, Maute K (2011) An Extended Finite mization 8(1):42–51 Element Method for the Analysis of Submicron Heat Fries T, Belytschko T (2010) The extended/generalized Transfer Phenomena, Multiscale Methods in Com- ﬁnite element method: an overview of the method and putational Mechanics, Lecture Notes in Applied and its applications. International Journal for Numerical Computational Mechanics, vol 55, Springer, pp 195– Methods in Engineering 84(3):253–304 212 Fries TP (2009) The intrinsic xfem for two-ﬂuid ﬂows. Li L, Wang M, Wei P (2012) Xfem schemes for level set Int J Numer Meth Fluids 60(4):437–471 based structural optimization. Frontiers of Mechani- Gain AL, Paulino GH (2013) A critical comparative cal Engineering 7(4):335–356 assessment of diﬀerential equation-driven methods Makhija D, Maute K (2013) Numerical instabilities in for structural topology optimization. Structural and level set topology optimization with the extended Multidisciplinary Optimization 48(4):685–710 ﬁnite element method. Structural and Multidisci- Gerstenberger A, Wall WA (2008a) Enhancement of plinary Optimization ﬁxed-grid methods towards complex ﬂuid-structure Maute K, Ramm E (1995) Adaptive topology optimiza- interaction applications. Int J Numer Meth Fluids tion. Structural and Multidisciplinary Optimization 57(9):1227–1248 10(2):100–112 Gerstenberger A, Wall WA (2008b) An extended ﬁnite Maute K, Ramm E (1997) Adaptive topology optimiza- element method/Lagrange multiplier based approach tion of shell structures. AIAA Journal 35(11):1767– for ﬂuid-structure interaction. Computer Methods in 1773 Applied Mechanics and Engineering 197:1699–1714 Maute K, Schwarz S, Ramm E (1998) Adaptive topol- Guest J, Pr´evost J, Belytschko T (2004) Achieving min- ogy optimization of elastoplastic structures. Struc- imum length scale in topology optimization using tural and Multidisciplinary Optimization 15(2):81– nodal design variables and projection functions. In- 91 ternational Journal for Numerical Methods in Engi- Maute K, Kreissl S, Makhija D, Yang R (2011) neering 61(2):238–254 Topology optimization of heat conduction in nano- ##LTLine##

text: Density

text: and

text: Level

text: Set-XFEM

text: Schemes

text: for

text: Topology

text: Optimization

text: of

text: Structures

label: paragraph

text: Journal

label: reference

text: for

text: Numerical

text: Methods

text: in

text: Engineering

text: Guest

text: J,

text: Asadpoure

text: A,

text: Ha

text: SH

text: Eliminating

text: beta-

text: Bendsøe

text: M

text: Optimal

text: shape

text: design

text: as

text: a

text: mate-

text: continuation

text: from

text: heaviside

text: projection

text: and

text: density

text: rial

text: distribution

text: problem.

text: Structural

text: and

text: Multidisci-

text: ﬁlter

text: algorithms.

text: Structural

text: and

text: Multidisciplinary

text: plinary

text: Optimization

text: Optimization

text: Bendsøe

text: MP,

text: Sigmund

text: O

text: Topology

text: Optimiza-

text: Hansbo

text: A,

text: Hansbo

text: P

text: A

text: ﬁnite

text: element

text: method

text: tion:

text: Theory,

text: Methods

text: and

text: Applications.

text: Springer

text: for

text: the

text: simulation

text: of

text: strong

text: and

text: weak

text: discontinuities

text: Burger

text: M,

text: Hackl

text: B,

text: Ring

text: W

text: Incorporating

text: topo-

text: in

text: solid

text: mechanics.

text: Computer

text: Methods

text: in

text: Applied

text: logical

text: derivatives

text: into

text: level

text: set

text: methods.

text: Journal

text: of

text: Mechanics

text: and

text: Engineering

text: Computational

text: Physics

text: Heroux

text: M,

text: Bartlett

text: R,

text: Hoekstra

text: VHR,

text: Hu

text: J,

text: Kolda

text: Deaton

text: J,

text: Grandhi

text: R

text: A

text: survey

text: of

text: struc-

text: T,

text: Lehoucq

text: R,

text: Long

text: K,

text: Pawlowski

text: R,

text: Phipps

text: E,

text: tural

text: and

text: multidisciplinary

text: continuum

text: topol-

text: Salinger

text: A,

text: Thornquist

text: H,

text: Tuminaro

text: R,

text: Willenbring

text: ogy

text: optimization:

text: post

text: Structural

text: and

text: J,

text: Williams

text: A

text: An

text: Overview

text: of

text: Trilinos.

text: Tech.

text: Multidisciplinary

text: Optimization

text: pp

text: URL

text: Rep.

text: Sandia

text: National

text: Laboratories

text: Herrero

text: D,

text: Mart´ınez

text: J,

text: Mart´ı

text: P

text: An

text: implemen-

text: van

text: Dijk

text: N,

text: Maute

text: K,

text: Langelaar

text: M,

text: Keulen

text: F

text: tation

text: of

text: level

text: set

text: based

text: topology

text: optimization

text: using

text: Level-set

text: methods

text: for

text: structural

text: topology

text: optimiza-

text: gpu.

text: In:

text: World

text: Congress

text: on

text: Structural

text: and

text: Mul-

text: tion:

text: a

text: review.

text: Structural

text: and

text: Multidisciplinary

text: Op-

text: tidisciplinary

text: Optimization

text: timization

text: pp

text: Juntunen

text: M,

text: Stenberg

text: R

text: Nitsche’s

text: method

text: for

text: Dolbow

text: J,

text: Harari

text: I

text: An

text: eﬃcient

text: ﬁnite

text: element

text: general

text: boundary

text: conditions.

text: Mathematics

text: of

text: Com-

text: method

text: for

text: embedded

text: interface

text: problems.

text: Int

text: J

text: Nu-

text: putation

text: mer

text: Meth

text: Engng

text: Kreissl

text: S,

text: Maute

text: K

text: Levelset

text: based

text: ﬂuid

text: topol-

text: Duysinx

text: P,

text: Miegroet

text: L,

text: Jacobs

text: T,

text: Fleury

text: C

text: Gen-

text: ogy

text: optimization

text: using

text: the

text: extended

text: ﬁnite

text: element

text: eralized

text: shape

text: optimization

text: using

text: x-fem

text: and

text: level

text: set

text: method.

text: Structural

text: and

text: Multidisciplinary

text: Optimiza-

text: methods.

text: In:

text: IUTAM

text: Symposium

text: on

text: Topological

text: De-

text: tion

text: pp

text: sign

text: Optimization

text: of

text: Structures,

text: Machines

text: and

text: Ma-

text: Lang

text: C,

text: Makhija

text: D,

text: Doostan

text: A,

text: Maute

text: K

text: terials,

text: Springer,

text: pp

text: A

text: simple

text: and

text: eﬃcient

text: preconditioning

text: scheme

text: for

text: Eschenauer

text: H,

text: Kobelev

text: V,

text: Schumacher

text: A

text: Bub-

text: xfem

text: with

text: heaviside

text: enrichments.

text: Computational

text: ble

text: method

text: for

text: topology

text: and

text: shape

text: optimization

text: of

text: Mechancis

text: structures.

text: Structural

text: and

text: Multidisciplinary

text: Opti-

text: Lee

text: P,

text: Yang

text: R,

text: Maute

text: K

text: An

text: Extended

text: Finite

text: mization

text: Element

text: Method

text: for

text: the

text: Analysis

text: of

text: Submicron

text: Heat

text: Fries

text: T,

text: Belytschko

text: T

text: The

text: extended/generalized

text: Transfer

text: Phenomena,

text: Multiscale

text: Methods

text: in

text: Com-

text: ﬁnite

text: element

text: method:

text: an

text: overview

text: of

text: the

text: method

text: and

text: putational

text: Mechanics,

text: Lecture

text: Notes

text: in

text: Applied

text: and

text: its

text: applications.

text: International

text: Journal

text: for

text: Numerical

text: Computational

text: Mechanics,

text: vol

text: Springer,

text: pp

text: Methods

text: in

text: Engineering

text: Fries

text: TP

text: The

text: intrinsic

text: xfem

text: for

text: two-ﬂuid

text: ﬂows.

text: Li

text: L,

text: Wang

text: M,

text: Wei

text: P

text: Xfem

text: schemes

text: for

text: level

text: set

text: Int

text: J

text: Numer

text: Meth

text: Fluids

text: based

text: structural

text: optimization.

text: Frontiers

text: of

text: Mechani-

text: Gain

text: AL,

text: Paulino

text: GH

text: A

text: critical

text: comparative

text: cal

text: Engineering

text: assessment

text: of

text: diﬀerential

text: equation-driven

text: methods

text: Makhija

text: D,

text: Maute

text: K

text: Numerical

text: instabilities

text: in

text: for

text: structural

text: topology

text: optimization.

text: Structural

text: and

text: level

text: set

text: topology

text: optimization

text: with

text: the

text: extended

text: Multidisciplinary

text: Optimization

text: ﬁnite

text: element

text: method.

text: Structural

text: and

text: Multidisci-

text: Gerstenberger

text: A,

text: Wall

text: WA

text: Enhancement

text: of

text: plinary

text: Optimization

text: ﬁxed-grid

text: methods

text: towards

text: complex

text: ﬂuid-structure

text: Maute

text: K,

text: Ramm

text: E

text: Adaptive

text: topology

text: optimiza-

text: interaction

text: applications.

text: Int

text: J

text: Numer

text: Meth

text: Fluids

text: tion.

text: Structural

text: and

text: Multidisciplinary

text: Optimization

text: Gerstenberger

text: A,

text: Wall

text: WA

text: An

text: extended

text: ﬁnite

text: Maute

text: K,

text: Ramm

text: E

text: Adaptive

text: topology

text: optimiza-

text: element

text: method/Lagrange

text: multiplier

text: based

text: approach

text: tion

text: of

text: shell

text: structures.

text: AIAA

text: Journal

text: for

text: ﬂuid-structure

text: interaction.

text: Computer

text: Methods

text: in

text: Applied

text: Mechanics

text: and

text: Engineering

text: Maute

text: K,

text: Schwarz

text: S,

text: Ramm

text: E

text: Adaptive

text: topol-

text: Guest

text: J,

text: Pr´evost

text: J,

text: Belytschko

text: T

text: Achieving

text: min-

text: ogy

text: optimization

text: of

text: elastoplastic

text: structures.

text: Struc-

text: imum

text: length

text: scale

text: in

text: topology

text: optimization

text: using

text: tural

text: and

text: Multidisciplinary

text: Optimization

text: nodal

text: design

text: variables

text: and

text: projection

text: functions.

text: In-

text: ternational

text: Journal

text: for

text: Numerical

text: Methods

text: in

text: Engi-

text: Maute

text: K,

text: Kreissl

text: S,

text: Makhija

text: D,

text: Yang

text: R

text: neering

text: Topology

text: optimization

text: of

text: heat

text: conduction

text: in

text: nano-

text: ##LTLine##


text: 10 Carlos H. Villanueva, Kurt Maute not depend on the tolerance values. In the LSM-XFEM trate the basic features of the LSM-XFEM approach − examples, the spring stiﬀness value, k, is 10 6. for three dimensional problems and show that the pro- While the LSF-XFEM results can be directly used posed LSM-XFEM approach and the SIMP formulation to fabricate the structure, for example by 3-D printing, may exhibit comparable convergence behaviors as the the SIMP results need to be post-processed. From a mesh is reﬁned. × × practitioner perspective, only the post-processed SIMP The 1 1 1 cubical design domain is pinned at results should be compared against the LSF-XFEM re- its four bottom corners in the vertical direction and a sults. To this end we post-process the SIMP results unit force is applied at the center of the bottom face. with a lumping method that uses the iso-contour of The Young’s modulus of the stiﬀ phase is set to 1 and the density distribution. To obtain a “0-1” density dis- the Poisson ratio to 0.3. The maximum volume of the tribution with smooth phase boundaries, we construct stiﬀ phase is 10%. We compare LSM-XFEM and SIMP × × × × iso-contours for ρ = ρT from the nodal density values, results for two mesh sizes: 24 24 24 and 65 65 65. ρi; see S≥ection . The volume enclosed by the iso-contour The problem is solved on the full mesh. with ρ ρT is considered solid; the remaining volume First, we apply the SIMP approach with a penaliza- is considered “void”. The threshold, ρT , is determined tion factor of p = 3. The size of the smoothing radius such that the volume of the solid domain satisﬁes the is mesh dependent, and is set to r = 3.2 for the coarse ρ volume constraint. The structural response of the re- mesh and r = 1.182 for the ﬁne mesh; the projection ρ sults post-processed with the iso-contour density lump- parameter is set to β = 0. Note that the smoothing ing (IDL) approach is analyzed conveniently with the radius is intentionally set relative to the element size × XFEM. (1.6 the element edge). The Young’s modulus of the − To gain further insight into the crispness of the void phase is set to E = 10 9. While this approach B SIMP results and the inﬂuence of the post-processing does not ensure mesh-independent optimization results, methods above on their performance, we measure the it still prevents the formation of checker-board patterns volume fraction, ρ¯, occupied by elemental densities with and provides insight into the dependency of the geom- (cid:90) 0 < ρˆe < 1 as follows: etry resolution of SIMP as the mesh is reﬁned. (cid:82) The design domain is initialized with a uniform ma- ρ¯ = 1 ρˆe(1 − ρˆe) dΩ (22) terial distribution of ρi = 0.1. The optimized material D ΩD dΩD ΩD distributions are shown in Figure 7 where material with a density lower than ρ < 0.75 is considered void. The i where Ω denotes the design domain. D strain energies are reported in Tab. 1. For both meshes 6.1 Cube with center load the volume constraint is active in the converged designs. As expected, the optimized geometry is smoother and the strain energy is lower for the reﬁned mesh. The SIMP results for the coarse and ﬁne mesh are post-processed with the IDL approach described above. The strain energies for varying threshold values, ρ , T are plotted in Fig. 8. The volume constraint is met for ρ = 0.78 for the coarse mesh and ρ = 0.44 for the T T ﬁne mesh. The diﬀerence between the SIMP-IDL and the SIMP results is of 0.04894% for the coarse mesh and 0.1230% for the ﬁne mesh. The value of ρ is higher T for the coarse mesh because it cannot converge to a design with void inclusions. In both cases the strain energies of the post-processed results match well the SIMP predictions as the density distributions converged well to “0-1” solutions. The volume fractions of intermediate densities are 0.285 and 0.0189 for the coarse and ﬁne mesh, respec- tively. The post-processed designs have lower strain en- Fig. 6: Cube with center load model. ergies because the post-processing counteracts the ef- fect of the density ﬁlter (18). We consider the “solid-void” optimization problem The same optimization problem is solved with the depicted in Fig. 6. With this example we will illus- proposed LSM-XFEM approach. The smoothing radius ##LTFigure## ##LTLine## ##LTLine##

text: Carlos

label: author

text: H.

text: Villanueva,

text: Kurt

text: Maute

text: not

text: depend

text: on

text: the

text: tolerance

text: values.

text: In

text: the

text: LSM-XFEM

text: trate

text: the

text: basic

text: features

text: of

text: the

text: LSM-XFEM

text: approach

text: examples,

text: the

text: spring

text: stiﬀness

text: value,

text: k,

text: is

text: for

text: three

text: dimensional

text: problems

text: and

text: show

text: that

text: the

text: pro-

text: While

text: the

text: LSF-XFEM

text: results

text: can

text: be

text: directly

text: used

text: posed

text: LSM-XFEM

text: approach

text: and

text: the

text: SIMP

text: formulation

text: to

text: fabricate

text: the

text: structure,

text: for

text: example

text: by

text: printing,

text: may

text: exhibit

text: comparable

text: convergence

text: behaviors

text: as

text: the

text: the

text: SIMP

text: results

text: need

text: to

text: be

text: post-processed.

text: From

text: a

text: mesh

text: is

text: reﬁned.

text: practitioner

text: perspective,

text: only

text: the

text: post-processed

text: SIMP

text: The

text: cubical

text: design

text: domain

text: is

text: pinned

text: at

text: results

text: should

text: be

text: compared

text: against

text: the

text: LSF-XFEM

text: re-

text: its

text: four

text: bottom

text: corners

text: in

text: the

text: vertical

text: direction

text: and

text: a

text: sults.

text: To

text: this

text: end

text: we

text: post-process

text: the

text: SIMP

text: results

text: unit

text: force

text: is

text: applied

text: at

text: the

text: center

text: of

text: the

text: bottom

text: face.

text: with

text: a

text: lumping

text: method

text: that

text: uses

text: the

text: iso-contour

text: of

text: The

text: Young’s

text: modulus

text: of

text: the

text: stiﬀ

text: phase

text: is

text: set

text: to

text: and

text: the

text: density

text: distribution.

text: To

text: obtain

text: a

text: density

text: dis-

text: the

text: Poisson

text: ratio

text: to

text: The

text: maximum

text: volume

text: of

text: the

text: tribution

text: with

text: smooth

text: phase

text: boundaries,

text: we

text: construct

text: stiﬀ

text: phase

text: is

text: We

text: compare

text: LSM-XFEM

text: and

text: SIMP

text: iso-contours

text: for

text: ρ

text: ρT

text: from

text: the

text: nodal

text: density

text: values,

text: results

text: for

text: two

text: mesh

text: sizes:

text: and

text: ρi;

text: see

text: S≥ection

text: The

text: volume

text: enclosed

text: by

text: the

text: iso-contour

text: The

text: problem

text: is

text: solved

text: on

text: the

text: full

text: mesh.

text: with

text: ρ

text: ρT

text: is

text: considered

text: solid;

text: the

text: remaining

text: volume

text: First,

text: we

text: apply

text: the

text: SIMP

text: approach

text: with

text: a

text: penaliza-

text: is

text: considered

text: “void”.

text: The

text: threshold,

text: ρT

text: is

text: determined

text: tion

text: factor

text: of

text: p

text: The

text: size

text: of

text: the

text: smoothing

text: radius

text: such

text: that

text: the

text: volume

text: of

text: the

text: solid

text: domain

text: satisﬁes

text: the

text: is

text: mesh

text: dependent,

text: and

text: is

text: set

text: to

text: r

text: for

text: the

text: coarse

text: ρ

text: volume

text: constraint.

text: The

text: structural

text: response

text: of

text: the

text: re-

text: mesh

text: and

text: r

text: for

text: the

text: ﬁne

text: mesh;

text: the

text: projection

text: ρ

text: sults

text: post-processed

text: with

text: the

text: iso-contour

text: density

text: lump-

text: parameter

text: is

text: set

text: to

text: β

text: Note

text: that

text: the

text: smoothing

text: ing

text: (IDL)

text: approach

text: is

text: analyzed

text: conveniently

text: with

text: the

text: radius

text: is

text: intentionally

text: set

text: relative

text: to

text: the

text: element

text: size

text: XFEM.

text: the

text: element

text: edge).

text: The

text: Young’s

text: modulus

text: of

text: the

text: To

text: gain

text: further

text: insight

text: into

text: the

text: crispness

text: of

text: the

text: void

text: phase

text: is

text: set

text: to

text: E

text: While

text: this

text: approach

text: B

text: SIMP

text: results

text: and

text: the

text: inﬂuence

text: of

text: the

text: post-processing

text: does

text: not

text: ensure

text: mesh-independent

text: optimization

text: results,

text: methods

text: above

text: on

text: their

text: performance,

text: we

text: measure

text: the

text: it

text: still

text: prevents

text: the

text: formation

text: of

text: checker-board

text: patterns

text: volume

text: fraction,

text: ρ¯,

text: occupied

text: by

text: elemental

text: densities

text: with

text: and

text: provides

text: insight

text: into

text: the

text: dependency

text: of

text: the

text: geom-

text: ρˆe

text: as

text: follows:

text: etry

text: resolution

text: of

text: SIMP

text: as

text: the

text: mesh

text: is

text: reﬁned.

text: The

text: design

text: domain

text: is

text: initialized

text: with

text: a

text: uniform

text: ma-

text: ρ¯

text: ρˆe)

text: dΩ

text: terial

text: distribution

text: of

text: ρi

text: The

text: optimized

text: material

text: D

text: ΩD

text: dΩD

text: ΩD

text: distributions

text: are

text: shown

text: in

text: Figure

text: where

text: material

text: with

text: a

text: density

text: lower

text: than

text: ρ

text: is

text: considered

text: void.

text: The

text: i

text: where

text: Ω

text: denotes

text: the

text: design

text: domain.

text: D

text: strain

text: energies

text: are

text: reported

text: in

text: Tab.

text: For

text: both

text: meshes

text: Cube

text: with

text: center

text: load

text: the

text: volume

text: constraint

text: is

text: active

text: in

text: the

text: converged

text: designs.

text: As

text: expected,

text: the

text: optimized

text: geometry

text: is

text: smoother

text: and

text: the

text: strain

text: energy

text: is

text: lower

text: for

text: the

text: reﬁned

text: mesh.

text: The

text: SIMP

text: results

text: for

text: the

text: coarse

text: and

text: ﬁne

text: mesh

text: are

text: post-processed

text: with

text: the

text: IDL

text: approach

text: described

text: above.

text: The

text: strain

text: energies

text: for

text: varying

text: threshold

text: values,

text: ρ

text: T

text: are

text: plotted

text: in

text: Fig.

text: The

text: volume

text: constraint

text: is

text: met

text: for

text: ρ

text: for

text: the

text: coarse

text: mesh

text: and

text: ρ

text: for

text: the

text: T

text: T

text: ﬁne

text: mesh.

text: The

text: diﬀerence

text: between

text: the

text: SIMP-IDL

text: and

text: the

text: SIMP

text: results

text: is

text: of

text: for

text: the

text: coarse

text: mesh

text: and

text: for

text: the

text: ﬁne

text: mesh.

text: The

text: value

text: of

text: ρ

text: is

text: higher

text: T

text: for

text: the

text: coarse

text: mesh

text: because

text: it

text: cannot

text: converge

text: to

text: a

text: design

text: with

text: void

text: inclusions.

text: In

text: both

text: cases

text: the

text: strain

text: energies

text: of

text: the

text: post-processed

text: results

text: match

text: well

text: the

text: SIMP

text: predictions

text: as

text: the

text: density

text: distributions

text: converged

text: well

text: to

text: solutions.

text: The

text: volume

text: fractions

text: of

text: intermediate

text: densities

text: are

text: and

text: for

text: the

text: coarse

text: and

text: ﬁne

text: mesh,

text: respec-

text: tively.

text: The

text: post-processed

text: designs

text: have

text: lower

text: strain

text: en-

text: Fig.

text: Cube

text: with

text: center

text: load

text: model.

text: ergies

text: because

text: the

text: post-processing

text: counteracts

text: the

text: ef-

text: fect

text: of

text: the

text: density

text: ﬁlter

text: We

text: consider

text: the

text: “solid-void”

text: optimization

text: problem

text: The

text: same

text: optimization

text: problem

text: is

text: solved

text: with

text: the

text: depicted

text: in

text: Fig.

text: With

text: this

text: example

text: we

text: will

text: illus-

text: proposed

text: LSM-XFEM

text: approach.

text: The

text: smoothing

text: radius

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##


text: 5 ∈ N { } (cid:88) (cid:88) (cid:88) (cid:0) (cid:1) rk, i / n for all vehicles k = 1, . . . , K, for some K, problem formulation is as follows: i then the dimensionality of the solution space is prohibitive. n n N Moreover, the inclusion of trafﬁc congestion effects introduces min τk (x ) + rkgxk (17) ∈N ij ij i ij additional nonlinearities in the dependence of the travel time xij,(cid:88)ri, i,j i(cid:88)=1 j=1 k=1 τij and energy consumption eij on t·h·e· trafﬁc ﬂow through arc s.t. for each k ∈ {1, . . . , N} : (i, j), which now depend on x1 , , xK. Instead, we will − ∈ N proceed by grouping subsets ofijvehiclesijinto N “subﬂows” xkij xkji = bi, for each i (18) where N may be selected to render the problem manageable. j∈O(cid:88)(i) j∈I(i) − (cid:54) b = 1, b = 1, b = 0, for i = 1, n (19) 1 n i − Ek = (Ek + rk ek (x ))xk , j = 2, . . . , n (20) j i i ij ij ij ∈ i I(j) Let all vehicles enter the network at the origin node 1 ≥ ∈ N Ek is given, Ek 0, for each i (21) and let R denote the rate of vehicles arriving at this node. 1 ∈ {i } ≥ Viewing vehicles as deﬁning a ﬂow, we divide them into xkij 0, 1 , rik 0 (22) N subﬂows (we will discuss the effect of N in Section Obviously, this MINLP problem is difﬁcult to solve. However, 3.3), each of which may be selected so as to include the as in the single-vehicle case, we are able to establish some same type of homogeneous vehicles (e.g., large vehicles vs properties that will allow us to simplify it. smaller ones or vehicles with the same initial energy). Thus, A. Properties all vehicles in the same subﬂow follow the same routing Even though the term τk (x ) in the objective function and recharging decisions so that we only consider energy ij ij is no longer linear in general, for each subﬂow k the con- recharging at the subﬂow level r→ath∞er than individual vehicles. straints (??)-(??) are still similar to the single-vehicle case. Note that asymptotically, as N , we can recover routing Consequently, we can derive similar useful properties for this at the individual vehicle level. problem in the form of the following two lemmas. Lemma 3(cid:88): F(cid:88)or each subﬂow k = 1, . . . , N, n n − − (cid:80)(rk ek (x ))xk = Ek Ek (23) Clearly, not all vehicles in our system are BPVs and are, i ij ij ij n 1 i=1 j=1 therefore, not part of our optimization process. These can be ∗ treated as uncontrollable interfering trafﬁc for our purposes Lemma 4: If n rk > 0 in the optimal routing policy, ∗ i=1 i and can be readily accommodated in our analysis, as long as then Ek = 0 for all k = 1, . . . , N. n their ﬂow rates are known. However, for simplicity, we will The proofs of the above two lemmas are almost identical assume here that every arriving vehicle is a BPV and joins a to those of Lemmas 1 and 2 respectively and are omitted. (cid:80) (cid:80) subﬂow. The only difference is that here the analysis is focused on (cid:80) (cid:80) each vehicle subﬂow instead of an individual vehicle. In view of Lemma 3, we can replace n n rkgxk in (??) by − i=1 j=1 i ij (Ek Ek)g + n n ek (x )gx and eliminate, for all n 1 i=1 j=1 ij ij ij − Our objective is to determine optimal routes and energy k = 1, . . . , N, the presence of rk, i = 1, . . . , n 1, from the i (cid:80) recharging amounts for each subﬂow of vehicles so as to objective function similar to the single-vehicle case. Since Ek 1 minimize the total elapsed time of these vehicle ﬂows traveling is given, this leaves only the task of determining the value of (cid:80) ∗ from the origin to the destination. The decision variables Ek. There are two possible cases: (i) rk > 0, i.e., the cko=nsi1st, .o. .f, Nx−ki,j as∈we{l0l,a1s}chfoarrgianllg aarmcsou(nit,sjr)ik afnodr aslulbnﬂoodwess k(siutinhb)ﬂvoewhiirchiklae∗s sa=udbe0ﬂq,ouwia.tee.h,earnsike∗trog=ygte0ot rfreoeacrchahalrltghieedadinaedtsitltiehnaeasttikotonhnwcveei,thhaiocnuldet i = 1, . . . , n 1 and k = 1, . . . , N. Given trafﬁc congestion (cid:80) (cid:80) recharging. effects, the time and energy consumption on each arc depends on the values of xk and the fraction of the total ﬂow rate Similar to the derivation of ≤(??), Case (ii) results in a new R associated with iejach subﬂow k; the simplest such ﬂow constraint i j ekij(xij)xkij E1k for subﬂow k. However, axnloiljote=catht(iexon1itjra,iv·se·lo·inn,egxNitwjim)hTeeraaenndedacrcoihr=rseus(bprﬂoi1on,w·d·in·igs, reaiNnses)irTgg.nyeTcdhoenRns,/uNmwep. tLidoeen-t s(c?ian?sce)e-(w?e?ikitj)h(wx(i?ijt?)h)-na(ol?lw?r)ik.deL=peet0nudisss niononsttaeasalldsxicm1iojpn,l.ce.e.nto,trxasNiotjel,voethnaesthpweroambslotehmree of the kth vehicle subﬂow on arc (i, j) by τk (x ) and ek (x ) interesting Case (i) for which Lemma 4 applies and we have raelssopecinticvoerlpyo. rAatse atlhreeadinyﬂmueennctieonoefd,unτickjo(nxtirjioj)llaanbijdlee(kijn(oxnii-jjB) PcViajn) Ek nk=∗ 1=, .0...(cid:88),TNhe:(cid:88)refore, along(cid:88)wit(cid:88)h Lemma 3, we have for each vehicle ﬂows, which can be treated as parameters in these n n n n − functions. Similar to the single vehicle case, we use Eik to rikxkij = ekij(xij)xkij E1k represent the residual energy of subﬂow k at node i, given by i=1 j=1 i=1 j=1 the aggregated residual energy of all vehicles in the subﬂow. Then, proceeding as in Theorem 1, we can replace the If the subﬂow does not go through node i, then Ek = 0. The original objective function (??) and have the following new i

text: N

text: rk,

text: i

text: n

text: for

text: all

text: vehicles

text: k

text: K,

text: for

text: some

text: K,

text: problem

text: formulation

text: is

text: as

text: follows:

text: i

text: then

text: the

text: dimensionality

text: of

text: the

text: solution

text: space

text: is

text: prohibitive.

text: n

text: n

text: N

text: Moreover,

text: the

text: inclusion

text: of

text: trafﬁc

text: congestion

text: effects

text: introduces

text: min

text: τk

text: (x

text: rkgxk

text: ∈N

text: ij

text: ij

text: i

text: ij

text: additional

text: nonlinearities

text: in

text: the

text: dependence

text: of

text: the

text: travel

text: time

text: i,j

text: τij

text: and

text: energy

text: consumption

text: eij

text: on

text: t·h·e·

text: trafﬁc

text: ﬂow

text: through

text: arc

text: s.t.

text: for

text: each

text: k

text: N}

text: (i,

text: j),

text: which

text: now

text: depend

text: on

text: xK.

text: Instead,

text: we

text: will

text: N

text: proceed

text: by

text: grouping

text: subsets

text: ofijvehiclesijinto

text: N

text: “subﬂows”

text: xkij

text: xkji

text: bi,

text: for

text: each

text: i

text: where

text: N

text: may

text: be

text: selected

text: to

text: render

text: the

text: problem

text: manageable.

text: j∈I(i)

text: b

text: b

text: b

text: for

text: i

text: n

text: n

text: i

text: Ek

text: (Ek

text: rk

text: ek

text: (x

text: ))xk

text: j

text: n

text: j

text: i

text: i

text: ij

text: ij

text: ij

text: i

text: I(j)

text: Let

text: all

text: vehicles

text: enter

text: the

text: network

text: at

text: the

text: origin

text: node

text: N

text: Ek

text: is

text: given,

text: Ek

text: for

text: each

text: i

text: and

text: let

text: R

text: denote

text: the

text: rate

text: of

text: vehicles

text: arriving

text: at

text: this

text: node.

text: {i

text: Viewing

text: vehicles

text: as

text: deﬁning

text: a

text: ﬂow,

text: we

text: divide

text: them

text: into

text: xkij

text: rik

text: N

text: subﬂows

text: (we

text: will

text: discuss

text: the

text: effect

text: of

text: N

text: in

text: Section

text: Obviously,

text: this

text: MINLP

text: problem

text: is

text: difﬁcult

text: to

text: solve.

text: However,

text: each

text: of

text: which

text: may

text: be

text: selected

text: so

text: as

text: to

text: include

text: the

text: as

text: in

text: the

text: single-vehicle

text: case,

text: we

text: are

text: able

text: to

text: establish

text: some

text: same

text: type

text: of

text: homogeneous

text: vehicles

text: (e.g.,

text: large

text: vehicles

text: vs

text: properties

text: that

text: will

text: allow

text: us

text: to

text: simplify

text: it.

text: smaller

text: ones

text: or

text: vehicles

text: with

text: the

text: same

text: initial

text: energy).

text: Thus,

text: A.

text: Properties

text: all

text: vehicles

text: in

text: the

text: same

text: subﬂow

text: follow

text: the

text: same

text: routing

text: Even

text: though

text: the

text: term

text: τk

text: (x

text: in

text: the

text: objective

text: function

text: and

text: recharging

text: decisions

text: so

text: that

text: we

text: only

text: consider

text: energy

text: ij

text: ij

text: is

text: no

text: longer

text: linear

text: in

text: general,

text: for

text: each

text: subﬂow

text: k

text: the

text: con-

text: recharging

text: at

text: the

text: subﬂow

text: level

text: r→ath∞er

text: than

text: individual

text: vehicles.

text: straints

text: are

text: still

text: similar

text: to

text: the

text: single-vehicle

text: case.

text: Note

text: that

text: asymptotically,

text: as

text: N

text: we

text: can

text: recover

text: routing

text: Consequently,

text: we

text: can

text: derive

text: similar

text: useful

text: properties

text: for

text: this

text: at

text: the

text: individual

text: vehicle

text: level.

text: problem

text: in

text: the

text: form

text: of

text: the

text: following

text: two

text: lemmas.

text: Lemma

text: each

text: subﬂow

text: k

text: N,

text: n

text: n

text: ek

text: (x

text: ))xk

text: Ek

text: Ek

text: Clearly,

text: not

text: all

text: vehicles

text: in

text: our

text: system

text: are

text: BPVs

text: and

text: are,

text: i

text: ij

text: ij

text: ij

text: n

text: therefore,

text: not

text: part

text: of

text: our

text: optimization

text: process.

text: These

text: can

text: be

text: treated

text: as

text: uncontrollable

text: interfering

text: trafﬁc

text: for

text: our

text: purposes

text: Lemma

text: If

text: n

text: rk

text: in

text: the

text: optimal

text: routing

text: policy,

text: i

text: and

text: can

text: be

text: readily

text: accommodated

text: in

text: our

text: analysis,

text: as

text: long

text: as

text: then

text: Ek

text: for

text: all

text: k

text: N.

text: n

text: their

text: ﬂow

text: rates

text: are

text: known.

text: However,

text: for

text: simplicity,

text: we

text: will

text: The

text: proofs

text: of

text: the

text: above

text: two

text: lemmas

text: are

text: almost

text: identical

text: assume

text: here

text: that

text: every

text: arriving

text: vehicle

text: is

text: a

text: BPV

text: and

text: joins

text: a

text: to

text: those

text: of

text: Lemmas

text: and

text: respectively

text: and

text: are

text: omitted.

text: subﬂow.

text: The

text: only

text: difference

text: is

text: that

text: here

text: the

text: analysis

text: is

text: focused

text: on

text: each

text: vehicle

text: subﬂow

text: instead

text: of

text: an

text: individual

text: vehicle.

text: In

text: view

text: of

text: Lemma

text: we

text: can

text: replace

text: n

text: n

text: rkgxk

text: in

text: by

text: i

text: ij

text: (Ek

text: Ek)g

text: n

text: n

text: ek

text: (x

text: )gx

text: and

text: eliminate,

text: for

text: all

text: n

text: ij

text: ij

text: ij

text: Our

text: objective

text: is

text: to

text: determine

text: optimal

text: routes

text: and

text: energy

text: k

text: N,

text: the

text: presence

text: of

text: rk,

text: i

text: n

text: from

text: the

text: i

text: recharging

text: amounts

text: for

text: each

text: subﬂow

text: of

text: vehicles

text: so

text: as

text: to

text: objective

text: function

text: similar

text: to

text: the

text: single-vehicle

text: case.

text: Since

text: Ek

text: minimize

text: the

text: total

text: elapsed

text: time

text: of

text: these

text: vehicle

text: ﬂows

text: traveling

text: is

text: given,

text: this

text: leaves

text: only

text: the

text: task

text: of

text: determining

text: the

text: value

text: of

text: from

text: the

text: origin

text: to

text: the

text: destination.

text: The

text: decision

text: variables

text: Ek.

text: There

text: are

text: two

text: possible

text: cases:

text: (i)

text: rk

text: i.e.,

text: the

text: .o.

text: .f,

text: Nx−ki,j

text: aarmcsou(nit,sjr)ik

text: afnodr

text: aslulbnﬂoodwess

text: k(siutinhb)ﬂvoewhiirchiklae∗s

text: i

text: n

text: and

text: k

text: N.

text: Given

text: trafﬁc

text: congestion

text: recharging.

text: effects,

text: the

text: time

text: and

text: energy

text: consumption

text: on

text: each

text: arc

text: depends

text: on

text: the

text: values

text: of

text: xk

text: and

text: the

text: fraction

text: of

text: the

text: total

text: ﬂow

text: rate

text: Similar

text: to

text: the

text: derivation

text: of

text: Case

text: (ii)

text: results

text: in

text: a

text: new

text: R

text: associated

text: with

text: iejach

text: subﬂow

text: k;

text: the

text: simplest

text: such

text: ﬂow

text: constraint

text: i

text: j

text: ekij(xij)xkij

text: for

text: subﬂow

text: k.

text: However,

text: reaiNnses)irTgg.nyeTcdhoenRns,/uNmwep.

text: tLidoeen-t

text: of

text: the

text: kth

text: vehicle

text: subﬂow

text: on

text: arc

text: (i,

text: j)

text: by

text: τk

text: (x

text: and

text: ek

text: (x

text: interesting

text: Case

text: (i)

text: for

text: which

text: Lemma

text: applies

text: and

text: we

text: have

text: raelssopecinticvoerlpyo.

text: rAatse

text: PcViajn)

text: Ek

text: nk=∗

text: Lemma

text: we

text: have

text: for

text: each

text: vehicle

text: ﬂows,

text: which

text: can

text: be

text: treated

text: as

text: parameters

text: in

text: these

text: n

text: n

text: n

text: n

text: functions.

text: Similar

text: to

text: the

text: single

text: vehicle

text: case,

text: we

text: use

text: Eik

text: to

text: rikxkij

text: ekij(xij)xkij

text: represent

text: the

text: residual

text: energy

text: of

text: subﬂow

text: k

text: at

text: node

text: i,

text: given

text: by

text: the

text: aggregated

text: residual

text: energy

text: of

text: all

text: vehicles

text: in

text: the

text: subﬂow.

text: Then,

text: proceeding

text: as

text: in

text: Theorem

text: we

text: can

text: replace

text: the

text: If

text: the

text: subﬂow

text: does

text: not

text: go

text: through

text: node

text: i,

text: then

text: Ek

text: The

text: original

text: objective

text: function

text: and

text: have

text: the

text: following

text: new

text: i


text: 7 transform the objective function (??) into (??) and determine TABLE I the optimal routes xk∗ by solving the following NLP: dij VALUES FOR NETWORK OF FIG. ?? (miles) ij (cid:88) (cid:88) (cid:88) (cid:2) (cid:3)   d12 d14 d15 d23 d24 d46 d56 d37 d47 d67 N n n − 5 6.2 7 3.5 5 3.6 4.3 6 6 4 min τk (x ) + ek (x )g Ek (33) i,jx∈ijN (cid:88)k=1 i=1 j=(cid:88)1 ij ij ij ij 1 s.t. for each k ∈ {1, . . . , N} : Therefore, we aim to solve the multi-vehicle routing problem using (??)(cid:88)wh(cid:88)ich (cid:88)in this case becomes: − ∈ N xk xk = b , for each i   j∈O(i) ij j∈I(−i) ji i (cid:54) min n n N dijx(cid:80)kij NR + egd R xk b1 = 1, bn =0 ≤1,xbki =≤01, for i = 1, n i,jx∈kijN i=1 j=1 k=1 vf(1 − ( kNxkij )p)q ij N ij ij (cid:88) (cid:88) (35) ∈ { } s.t. for each k 1, . . . , N : The values of rik, i = 1, . . . , n, k = 1, . . . , N, can be − ∈ N determined so as to satisfy the energy constraints (??)-(??), xk xk = b , for each i ij ji i and they are obviously not unique. We may then proceed j∈O(i) j∈I(i) − (cid:54) with a second-level optimization problem to determine optimal b = 1, b = 1, b = 0, for i = 1, n 1 n i values similar to Section 2.2. ∈ { } xk 0, 1 C. Numerical Examples ij For simplicity, we let v = 1 mile/min, R = 1 vehicle/min, f · We consider a speciﬁc example which includes trafﬁc con- p = 2, q = 2 and e g = 1. The network topology gestion and energy consumption functions. The relationship used is that of Fig.??, where the distance of each arc is between the speed and density of a vehicle ﬂow is typically shown in Tab. ??. To solve the nonlinear binary programming estimated as follows (see [?]): problem (??), we use the optimization solver Opti (MATLAB (cid:18) (cid:18) (cid:19) (cid:19) toolbox for optimization). The results are shown in Tab. ?? for different values of N = 1, . . . , 30. As shown in Tab. ??, v(k(t)) = v 1 − k(t) p q (34) vehicles are mainly distributed through three routes and the f k trafﬁc congestion effect makes the ﬂow distribution differ from jam following the shortest path. The number of decision variables (hence, the solution search space) rapidly increases with the where v is the reference speed on the road without trafﬁc, number of subﬂows. However, looking at Fig. ?? which gives f k(t) represents the density of vehicles on the road at time t and the performance in terms of our objective function in (??) k the saturated density for a trafﬁc jam. The parameters as a function of the number of subﬂows, observe that the jam p and q are empirically identiﬁed for actual trafﬁc ﬂows. optimal objective value quickly converges around N = 10. In our multi-vehicle routing problem, we are interested in Thus, even though the best solution is found when N = 25, a the relationship between the density of the vehicle ﬂow and near-optimal solution can be determined under a small number traveling time on an arc (i, j), i.e., τk (x ). Given a network of subﬂows. This suggests that one can rapidly approximate ij ij topology (i.e., a road map), the distances d between nodes the asymptotic solution of the multi-vehicle problem (dealing ij are known. Moreover, we do not include uncontrollable vehicle with individual vehicles routed so as to optimize a systemwide ﬂows in our example for simplicity. In our approach, we need objective) based on a relatively small value of N. to identify N subﬂows and we do so by evenly dividing the Next, we obtain a solution to the same problem (??) using evnehtiircelevsehpiecrleuinniﬂt otwimien.toThNuss,ukbjﬂaomwsin, etahcihs ocafswehciacnh hb(cid:80)aessRet/Nas tShiencaeltienrnthaitsiveexaNmLpPlefaolrlmsuublaﬂtoiowns (a?re?)idwenhteicreal,0w≤e caxnkijfu≤rthe1r. Nthe, ismampleyinpgathth,aht ewnecedothenotthwe aanrtca(lli,vje)hidcelenssittyo giso thrkoxugkijh. cfoolmlobwinineg aNll-sx(cid:88)ukibjﬂo(cid:88)owverr(cid:18)eleaaxcehd parrcob(leim, j:), which leads(cid:19)to the Therefore, the time subﬂow k spends on arc (i, j) becomes n n τk (x ) = dij · x(cid:80)kij · NR xijm, i,ijn∈N (cid:88)i=1 j=1 v(cid:88)f(1d−ijx(ixjiRj)p)q + egdijRxij (36) ij ij v (1 − ( k xkij )p)q s.t. x − x = b , for each i ∈ N f N ij ji i ∈ ∈ j O(i) j I(i) − (cid:54) As for ekij(xij), we assume the energy consumption rates of b1 = 1, bn = ≤1, bi =≤0, for i = 1, n subﬂows on arc (i, j) are all identical, proportional to the 0 x 1 ij distance between nodes i and j, giving This is a relatively easy to solve NLP problem. Using the same parameter settings as before, we obtain the objective value of · · R ek (x ) = e d 31.4465 mins and the optimal routes are: ij ij ij N ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: transform

text: the

text: objective

text: function

text: into

text: and

text: determine

text: TABLE

text: I

text: the

text: optimal

text: routes

text: xk∗

text: by

text: solving

text: the

text: following

text: NLP:

text: dij

label: caption

text: VALUES

text: FOR

text: NETWORK

text: OF

text: FIG.

text: (miles)

text: ij

text: N

text: n

text: n

text: min

text: τk

text: (x

text: ek

text: (x

text: )g

text: Ek

text: i,jx∈ijN

text: ij

text: ij

text: ij

text: ij

text: s.t.

text: for

text: each

text: k

text: N}

text: Therefore,

text: we

text: aim

text: to

text: solve

text: the

text: multi-vehicle

text: routing

text: problem

text: using

text: this

text: case

text: becomes:

text: N

text: xk

text: xk

text: b

text: for

text: each

text: i

text: j∈O(i)

text: ij

text: j∈I(−i)

text: ji

text: i

text: min

text: n

text: n

text: N

text: NR

text: egd

text: R

text: xk

text: bn

text: for

text: i

text: n

text: i,jx∈kijN

text: kNxkij

text: )p)q

text: ij

text: N

text: ij

text: ij

text: s.t.

text: for

text: each

text: k

text: N

text: The

text: values

text: of

text: rik,

text: i

text: n,

text: k

text: N,

text: can

text: be

text: N

text: determined

text: so

text: as

text: to

text: satisfy

text: the

text: energy

text: constraints

text: xk

text: xk

text: b

text: for

text: each

text: i

text: ij

text: ji

text: i

text: and

text: they

text: are

text: obviously

text: not

text: unique.

text: We

text: may

text: then

text: proceed

text: j∈O(i)

text: j∈I(i)

text: with

text: a

text: second-level

text: optimization

text: problem

text: to

text: determine

text: optimal

text: b

text: b

text: b

text: for

text: i

text: n

text: n

text: i

text: values

text: similar

text: to

text: Section

text: xk

text: C.

text: Numerical

text: Examples

text: ij

text: For

text: simplicity,

text: we

text: let

text: v

text: mile/min,

text: R

text: vehicle/min,

text: f

text: We

text: consider

text: a

text: speciﬁc

text: example

text: which

text: includes

text: trafﬁc

text: con-

text: p

text: q

text: and

text: e

text: g

text: The

text: network

text: topology

text: gestion

text: and

text: energy

text: consumption

text: functions.

text: The

text: relationship

text: used

text: is

text: that

text: of

text: Fig.??,

text: where

text: the

text: distance

text: of

text: each

text: arc

text: is

text: between

text: the

text: speed

text: and

text: density

text: of

text: a

text: vehicle

text: ﬂow

text: is

text: typically

text: shown

text: in

text: Tab.

text: To

text: solve

text: the

text: nonlinear

text: binary

text: programming

text: estimated

text: as

text: follows

text: (see

text: problem

text: we

text: use

text: the

text: optimization

text: solver

text: Opti

text: (MATLAB

text: toolbox

text: for

text: optimization).

text: The

text: results

text: are

text: shown

text: in

text: Tab.

text: for

text: different

text: values

text: of

text: N

text: As

text: shown

text: in

text: Tab.

text: v(k(t))

text: v

text: k(t)

text: p

text: q

text: vehicles

text: are

text: mainly

text: distributed

text: through

text: three

text: routes

text: and

text: the

text: f

text: k

text: trafﬁc

text: congestion

text: effect

text: makes

text: the

text: ﬂow

text: distribution

text: differ

text: from

text: jam

text: following

text: the

text: shortest

text: path.

text: The

text: number

text: of

text: decision

text: variables

text: (hence,

text: the

text: solution

text: search

text: space)

text: rapidly

text: increases

text: with

text: the

text: where

text: v

text: is

text: the

text: reference

text: speed

text: on

text: the

text: road

text: without

text: trafﬁc,

text: number

text: of

text: subﬂows.

text: However,

text: looking

text: at

text: Fig.

text: which

text: gives

text: f

text: k(t)

text: represents

text: the

text: density

text: of

text: vehicles

text: on

text: the

text: road

text: at

text: time

text: t

text: and

text: the

text: performance

text: in

text: terms

text: of

text: our

text: objective

text: function

text: in

text: k

text: the

text: saturated

text: density

text: for

text: a

text: trafﬁc

text: jam.

text: The

text: parameters

text: as

text: a

text: function

text: of

text: the

text: number

text: of

text: subﬂows,

text: observe

text: that

text: the

text: jam

text: p

text: and

text: q

text: are

text: empirically

text: identiﬁed

text: for

text: actual

text: trafﬁc

text: ﬂows.

text: optimal

text: objective

text: value

text: quickly

text: converges

text: around

text: N

text: In

text: our

text: multi-vehicle

text: routing

text: problem,

text: we

text: are

text: interested

text: in

text: Thus,

text: even

text: though

text: the

text: best

text: solution

text: is

text: found

text: when

text: N

text: a

text: the

text: relationship

text: between

text: the

text: density

text: of

text: the

text: vehicle

text: ﬂow

text: and

text: near-optimal

text: solution

text: can

text: be

text: determined

text: under

text: a

text: small

text: number

text: traveling

text: time

text: on

text: an

text: arc

text: (i,

text: j),

text: i.e.,

text: τk

text: (x

text: Given

text: a

text: network

text: of

text: subﬂows.

text: This

text: suggests

text: that

text: one

text: can

text: rapidly

text: approximate

text: ij

text: ij

text: topology

text: (i.e.,

text: a

text: road

text: map),

text: the

text: distances

text: d

text: between

text: nodes

text: the

text: asymptotic

text: solution

text: of

text: the

text: multi-vehicle

text: problem

text: (dealing

text: ij

text: are

text: known.

text: Moreover,

text: we

text: do

text: not

text: include

text: uncontrollable

text: vehicle

text: with

text: individual

text: vehicles

text: routed

text: so

text: as

text: to

text: optimize

text: a

text: systemwide

text: ﬂows

text: in

text: our

text: example

text: for

text: simplicity.

text: In

text: our

text: approach,

text: we

text: need

text: objective)

text: based

text: on

text: a

text: relatively

text: small

text: value

text: of

text: N.

text: to

text: identify

text: N

text: subﬂows

text: and

text: we

text: do

text: so

text: by

text: evenly

text: dividing

text: the

text: Next,

text: we

text: obtain

text: a

text: solution

text: to

text: the

text: same

text: problem

text: using

text: evnehtiircelevsehpiecrleuinniﬂt

text: otwimien.toThNuss,ukbjﬂaomwsin,

text: etahcihs

text: ocafswehciacnh

text: Nthe,

text: ismampleyinpgathth,aht

text: ewnecedothenotthwe

text: aanrtca(lli,vje)hidcelenssittyo

text: giso

text: thrkoxugkijh.

text: cfoolmlobwinineg

text: parrcob(leim,

text: j:),

text: which

text: the

text: Therefore,

text: the

text: time

text: subﬂow

text: k

text: spends

text: on

text: arc

text: (i,

text: j)

text: becomes

text: n

text: n

text: τk

text: (x

text: dij

text: NR

text: xijm,

text: i,ijn∈N

text: egdijRxij

text: ij

text: ij

text: v

text: k

text: xkij

text: )p)q

text: s.t.

text: x

text: x

text: b

text: for

text: each

text: i

text: N

text: f

text: N

text: ij

text: ji

text: i

text: j

text: O(i)

text: j

text: I(i)

text: As

text: for

text: ekij(xij),

text: we

text: assume

text: the

text: energy

text: consumption

text: rates

text: of

text: bn

text: bi

text: for

text: i

text: n

text: subﬂows

text: on

text: arc

text: (i,

text: j)

text: are

text: all

text: identical,

text: proportional

text: to

text: the

text: x

text: ij

text: distance

text: between

text: nodes

text: i

text: and

text: j,

text: giving

text: This

text: is

text: a

text: relatively

text: easy

text: to

text: solve

text: NLP

text: problem.

text: Using

text: the

text: same

text: parameter

text: settings

text: as

text: before,

text: we

text: obtain

text: the

text: objective

text: value

text: of

text: R

text: ek

text: (x

text: e

text: d

text: mins

text: and

text: the

text: optimal

text: routes

text: are:

text: ij

text: ij

text: ij

text: N

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: |X| where q = . We(cid:88)use(cid:88)the following two quantities in the where p is the conditional probability of U given X. paper extensively: U|X 1 | | − | | A transmission system with parameters (Xn,YM, τ) for reli- Dd(W) = 2q (cid:88) (cid:88) W(x u) W(x u + d) able communication over a given channel ( , , W) consists u∈U x∈X { } → X odfecaondinengcmo(cid:88)daipnpginmgaDppecin:gYEnn→c :{11,,22,,......,,MM} such thnatand a D˜d(W) = 21q (W(x|u) − W(x|u + d))2 u∈U x∈X 1 M (cid:54) | ≤ where d is some element of G and + is the group operation. Wn (Dec(Y n) = m Xn = Enc(m)) τ M m=1 X Y Given a channel ( , , W), the rate R is said to be achievable For any N = 2n, a polar code of length N designed for the Y if for all (cid:15) > 0 and for all sufﬁciently large n, there channel (Z , , W) is a linear (coset) code characterized by a 2 ⊆ { · · · } exists a transmission system for reliable communication with generator matrix G(cid:20)N and a(cid:21)set of indices A 1, , N of parameters (n, M, τ) such that almost perfect channels. The generator matrix for polar codes 1 ≥ − ≤ is deﬁned as GN = BNF⊗n where BN is a permutation log M R (cid:15), τ (cid:15) 1 0 ⊗ n of rows, F = and denotes the Kronecker 1 1 The channel capacity is the supremum of the set of achievable product. The set A is a function of the channel. The decoding rates. It is known that the channel capacity is given by: algorithm for polar codes is a speciﬁc form of successive cancellation [1]. C = sup I(X; Y ) (2) pX For any discrete memoryless channel, there always exists where p is the channel input distribution. an Abelian group of the same size as that of the channel X input alphabet. In general, for an Abelian group, there may not exist a multiplication operation. Since polar encoders All groups referred to in this paper are Abelian groups. are characterized by a matrix multiplication, before using Given a group (G, +), a subset H of G is called a subgroup these codes for channels of arbitrary input alphabet sizes, of G if it is closed under the group operation. In this case, a generator matrix for codes over Abelian groups needs to (H, +) is a group in its own right. This is denoted by be properly deﬁned. Polar codes over Abelian groups are ≤ H G. A coset C of a subgroup H is a shift of H by an introduced in [4]. ∈ ∈ arbitrary element a G (i.e. C = a + H for some a G). For any subgroup H of G, its cosets partition the group G. A transversal T of a subgroup H of G is a subset of G We denote by O((cid:15)) any function of (cid:15) which is right- → ↓ containing one and only one elem(cid:104)en(cid:105)t from each coset (shift) continuous around 0 and that(cid:76)O((cid:15)) {0 as (cid:15) ·0·.· } of H. Given an element d of G, d denotes the subgroup of For positive integers N and r, let A , A , , A be a { · · · }0 1 r G generated by d. i.e. the smallest subgroup of G containing partition of the index set 1, 2, , N . Given sets T for · · · t d. A subgroup M of G is called maximal if it is a proper t = 0, , r, the direct sum r TAt is deﬁned as the set · · · t=0 t ∈ subgroup and there does not exist another proper subgroup of of all tuples uN = (u , , u ) such that u T whenever ∈ 1 1 N i t G containing M. i A . t X Y X For a channel ( , , W), assume is equipped with the structure of a group (G, +). The symmetric capacity is deﬁned III. THE LOSSY SOURCE CODING PROBLEM as I¯(W) = I(X; Y ) where the channel input X is uniformly In this section, we prove the following theorem: X distributed over and Y is the output of the channel. The Bhattacharyya distance betw(cid:88)een(cid:112)two distinct input symbols x Theorem III.1. For an arbitrary discrete memoryless source X U and x˜ is deﬁned as ( , , p , d), nested polar codes achieve the Shannon rate- X | | distortion function (2). Z(W ) = W(y x)W(y x˜) {x,x˜} X U U (cid:88)y∈Y For the source ( , , pX, d), let =| |G where G is and the average Bhattacharyya distance is deﬁned as an arbitrary Abelian group and∈let q = G be the size of the group. For a pair (R, D) R2, let X be distributed Z(W) = q(q 1− 1)Z(W{x,x˜}) aEc{cdo(rXdin, Ug )t}o ≤pXDa.nWdeleptroUvebtehaat trhaenrdeomexivstasriaabplaeirsuocfhpothlaart x,x˜∈X ⊆ x(cid:54)=x˜ codes C C such that C induces a partition of C through i o i o ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: |X|

text: where

text: q

text: following

text: two

text: quantities

text: in

text: the

text: where

text: p

text: is

text: the

text: conditional

text: probability

text: of

text: U

text: given

text: X.

text: paper

text: extensively:

text: U|X

text: A

text: transmission

text: system

text: with

text: parameters

text: (Xn,YM,

text: τ)

text: for

text: reli-

text: Dd(W)

text: W(x

text: u)

text: W(x

text: u

text: d)

text: able

text: communication

text: over

text: a

text: given

text: channel

text: W)

text: consists

text: u∈U

text: x∈X

text: X

text: such

text: thnatand

text: a

text: D˜d(W)

text: (W(x|u)

text: W(x|u

text: u∈U

text: x∈X

text: M

font: default

text: where

text: d

text: is

text: some

text: element

text: of

text: G

text: and

text: is

text: the

text: group

text: operation.

text: Wn

text: (Dec(Y

text: n)

text: m

text: Xn

text: Enc(m))

text: τ

text: M

text: X

text: Y

text: Given

text: a

text: channel

text: W),

text: the

text: rate

text: R

text: is

text: said

text: to

text: be

text: achievable

text: For

text: any

text: N

text: a

text: polar

text: code

text: of

text: length

text: N

text: designed

text: for

text: the

text: Y

text: if

text: for

text: all

text: and

text: for

text: all

text: sufﬁciently

text: large

text: n,

text: there

text: channel

text: (Z

text: W)

text: is

text: a

text: linear

text: (coset)

text: code

text: characterized

text: by

text: a

text: exists

text: a

text: transmission

text: system

text: for

text: reliable

text: communication

text: with

text: generator

text: matrix

text: and

text: of

text: indices

text: A

text: N

text: of

text: parameters

text: (n,

text: M,

text: τ)

text: such

text: that

text: almost

text: perfect

text: channels.

text: The

text: generator

text: matrix

text: for

text: polar

text: codes

text: is

text: deﬁned

text: as

text: GN

text: BNF⊗n

text: where

text: BN

text: is

text: a

text: permutation

text: log

text: M

text: R

text: τ

text: n

text: of

text: rows,

text: F

text: and

text: denotes

text: the

text: Kronecker

text: The

text: channel

text: capacity

text: is

text: the

text: supremum

text: of

text: the

text: set

text: of

text: achievable

text: product.

text: The

text: set

text: A

text: is

text: a

text: function

text: of

text: the

text: channel.

text: The

text: decoding

text: rates.

text: It

text: is

text: known

text: that

text: the

text: channel

text: capacity

text: is

text: given

text: by:

text: algorithm

text: for

text: polar

text: codes

text: is

text: a

text: speciﬁc

text: form

text: of

text: successive

text: cancellation

text: C

text: sup

text: I(X;

text: Y

text: pX

text: For

text: any

text: discrete

text: memoryless

text: channel,

text: there

text: always

text: exists

text: where

text: p

text: is

text: the

text: channel

text: input

text: distribution.

text: an

text: Abelian

text: group

text: of

text: the

text: same

text: size

text: as

text: that

text: of

text: the

text: channel

text: X

text: input

text: alphabet.

text: In

text: general,

text: for

text: an

text: Abelian

text: group,

text: there

text: may

text: not

text: exist

text: a

text: multiplication

text: operation.

text: Since

text: polar

text: encoders

text: All

text: groups

text: referred

text: to

text: in

text: this

text: paper

text: are

text: Abelian

text: groups.

text: are

text: characterized

text: by

text: a

text: matrix

text: multiplication,

text: before

text: using

text: Given

text: a

text: group

text: (G,

text: a

text: subset

text: H

text: of

text: G

text: is

text: called

text: a

text: subgroup

text: these

text: codes

text: for

text: channels

text: of

text: arbitrary

text: input

text: alphabet

text: sizes,

text: of

text: G

text: if

text: it

text: is

text: closed

text: under

text: the

text: group

text: operation.

text: In

text: this

text: case,

text: a

text: generator

text: matrix

text: for

text: codes

text: over

text: Abelian

text: groups

text: needs

text: to

text: (H,

text: is

text: a

text: group

text: in

text: its

text: own

text: right.

text: This

text: is

text: denoted

text: by

text: be

text: properly

text: deﬁned.

text: Polar

text: codes

text: over

text: Abelian

text: groups

text: are

text: H

text: G.

text: A

text: coset

text: C

text: of

text: a

text: subgroup

text: H

text: is

text: a

text: shift

text: of

text: H

text: by

text: an

text: introduced

text: in

text: arbitrary

text: element

text: a

text: G

text: (i.e.

text: C

text: a

text: H

text: for

text: some

text: a

text: G).

text: For

text: any

text: subgroup

text: H

text: of

text: G,

text: its

text: cosets

text: partition

text: the

text: group

text: G.

text: A

text: transversal

text: T

text: of

text: a

text: subgroup

text: H

text: of

text: G

text: is

text: a

text: subset

text: of

text: G

text: We

text: denote

text: by

text: any

text: function

text: of

text: which

text: is

text: right-

text: containing

text: one

text: and

text: only

text: one

text: from

text: each

text: coset

text: (shift)

text: continuous

text: around

text: and

text: as

text: ·0·.·

text: of

text: H.

text: Given

text: an

text: element

text: d

text: of

text: G,

text: d

text: denotes

text: the

text: subgroup

text: of

text: For

text: positive

text: integers

text: N

text: and

text: r,

text: let

text: A

text: A

text: A

text: be

text: a

text: r

text: G

text: generated

text: by

text: d.

text: i.e.

text: the

text: smallest

text: subgroup

text: of

text: G

text: containing

text: partition

text: of

text: the

text: index

text: set

text: N

text: Given

text: sets

text: T

text: for

text: t

text: d.

text: A

text: subgroup

text: M

text: of

text: G

text: is

text: called

text: maximal

text: if

text: it

text: is

text: a

text: proper

text: t

text: r,

text: the

text: direct

text: sum

text: r

text: TAt

text: is

text: deﬁned

text: as

text: the

text: set

text: t

text: subgroup

text: and

text: there

text: does

text: not

text: exist

text: another

text: proper

text: subgroup

text: of

text: of

text: all

text: tuples

text: uN

text: (u

text: u

text: such

text: that

text: u

text: T

text: whenever

text: N

text: i

text: t

text: G

text: containing

text: M.

text: i

text: A

text: t

text: X

text: Y

text: X

text: For

text: a

text: channel

text: W),

text: assume

text: is

text: equipped

text: with

text: the

text: structure

text: of

text: a

text: group

text: (G,

text: The

text: symmetric

text: capacity

text: is

text: deﬁned

text: III.

text: THE

text: LOSSY

text: SOURCE

text: CODING

text: PROBLEM

text: as

text: I¯(W)

text: I(X;

text: Y

text: where

text: the

text: channel

text: input

text: X

text: is

text: uniformly

text: In

text: this

text: section,

text: we

text: prove

text: the

text: following

text: theorem:

text: X

text: distributed

text: over

text: and

text: Y

text: is

text: the

text: output

text: of

text: the

text: channel.

text: The

text: Bhattacharyya

text: distance

text: distinct

text: input

text: symbols

text: x

text: Theorem

text: For

text: an

text: arbitrary

text: discrete

text: memoryless

text: source

text: X

text: U

text: and

text: x˜

text: is

text: deﬁned

text: as

text: p

text: d),

text: nested

text: polar

text: codes

text: achieve

text: the

text: Shannon

text: rate-

text: X

text: distortion

text: function

text: Z(W

text: W(y

text: x)W(y

text: x˜)

text: {x,x˜}

text: X

text: U

text: U

text: For

text: the

text: source

text: pX,

text: d),

text: let

text: |G

text: where

text: G

text: is

text: and

text: the

text: average

text: Bhattacharyya

text: distance

text: is

text: deﬁned

text: as

text: an

text: arbitrary

text: Abelian

text: group

text: and∈let

text: q

text: G

text: be

text: the

text: size

text: of

text: the

text: group.

text: For

text: a

text: pair

text: (R,

text: D)

text: let

text: X

text: be

text: distributed

text: Z(W)

text: q(q

text: 1−

text: aEc{cdo(rXdin,

text: Ug

text: )t}o

text: ≤pXDa.nWdeleptroUvebtehaat

text: x,x˜∈X

text: codes

text: C

text: C

text: such

text: that

text: C

text: induces

text: a

text: partition

text: of

text: C

text: through

text: i

text: o

text: i

text: o

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: **Volume Title** ASP Conference Series, Vol. **Volume Number** **Author** (cid:13)c **Copyright Year** Astronomical Society of the Paciﬁc The Limb Brightening and its Relationship with the Millimeter-wave Cavity V. De la Luz,1 M. Chavez,1 and E. Bertone1 1Instituto Nacional de Astrof´ısica Ø´ptica y Electrø´nica, Luis Enrique Erro 1, Sta. Ma. Tonantzintla, Puebla, Mexico Abstract. Through a detailed theoretical analysis of the local emission at millimeter,sub- millimeter and infrared wavelength regimes (from 10 GHz up to 10 THz), we found that, associated with the temperature minimum, there is an optically thin cavity sur- rounded by two regions of high local emissivity. We call this structure the Chromo- spheric Solar Millimeter Cavity (CSMC). In order to search for traces of this cavity in the available radio observations on the solar limb, we have developed a robust method to associate the radiation at diﬀerent heights with the observed brightness temperatures. We foresee that this approach will allow us to determine the relationship between the CSMC and the solar limb brightening. 1. Introduction The ﬁrst observations of the solar radio emission shown a high brightness temper- ature hundreds of times grater than the observed thermal radiation from the photosphere (?). This radio emission was associated with the solar Corona region (?). In ? the solar limb brightening and the solar radii below 24 GHz was theoretically predicted. This early work, shows that the solar radii grows in diameter while the fre- quency of the emission decreases. The observed apparent temperatures was associated with the chromosphere and coronal regions. Several observations at high frequencies were performed in order to character- ize the limb brightening (We can found an extended review about the observations at short millimeter range in ?). These works show that the theoretical limb brightening could be aﬀected by the spicules. However, ? shows that the height scale of the tran- sition zone model is unimportant. Is important remark that these ﬁrst models present higher temperature minimum than the actual values. The temperature minimum plays a fundamental role in the chromospheric emission because it is requiered to reproduce observations of CO moleculae. The CO have a threshold around 4200 K to avoid their desintegration (?). The relation between the limb brightening and the microstructure (spicules) was studied in detail in ?. However, the approximation of full ionizated chromosphere and the empirical model of the chromosphere is not a good approximation at millimeter region (?) besides that their minimum of temperature is higher than 4200 K. In De la Luz et al 2012 (under review) we found that the temperature minimum of the chromosphere create a structure called Chromospheric Solar Millimeter-wave Cav- ity (CSMC). This structure is the responsible of the morphology of the solar spectrum 1

text: **Volume

text: Title**

text: ASP

text: Conference

text: Series,

text: Vol.

text: **Volume

text: Number**

text: **Author**

text: **Copyright

text: Year**

text: Astronomical

text: Society

text: of

text: the

text: Paciﬁc

text: The

text: Limb

text: Brightening

text: and

text: its

text: Relationship

text: with

text: the

text: Millimeter-wave

text: Cavity

text: V.

text: De

text: la

text: M.

text: and

text: E.

text: Nacional

text: de

text: Astrof´ısica

text: Ø´ptica

text: y

text: Electrø´nica,

text: Luis

text: Enrique

text: Erro

text: Sta.

text: Ma.

text: Tonantzintla,

text: Puebla,

text: Mexico

text: Abstract.

text: Through

label: abstract

text: a

text: detailed

text: theoretical

text: analysis

text: of

text: the

text: local

text: emission

text: at

text: millimeter,sub-

text: millimeter

text: and

text: infrared

text: wavelength

text: regimes

text: (from

text: GHz

text: up

text: to

text: THz),

text: we

text: found

text: that,

text: associated

text: with

text: the

text: temperature

text: minimum,

text: there

text: is

text: an

text: optically

text: thin

text: cavity

text: sur-

text: rounded

text: by

text: two

text: regions

text: of

text: high

text: local

text: emissivity.

text: We

text: call

text: this

text: structure

text: the

text: Chromo-

text: spheric

text: Solar

text: Millimeter

text: Cavity

text: (CSMC).

text: In

text: order

text: to

text: search

text: for

text: traces

text: of

text: this

text: cavity

text: in

text: the

text: available

text: radio

text: observations

text: on

text: the

text: solar

text: limb,

text: we

text: have

text: developed

text: a

text: robust

text: method

text: to

text: associate

text: the

text: radiation

text: at

text: diﬀerent

text: heights

text: with

text: the

text: observed

text: brightness

text: temperatures.

text: We

text: foresee

text: that

text: this

text: approach

text: will

text: allow

text: us

text: to

text: determine

text: the

text: relationship

text: between

text: the

text: CSMC

text: and

text: the

text: solar

text: limb

text: brightening.

text: Introduction

text: The

text: ﬁrst

text: observations

text: of

text: the

text: solar

text: radio

text: emission

text: shown

text: a

text: high

text: brightness

text: temper-

text: ature

text: hundreds

text: of

text: times

text: grater

text: than

text: the

text: observed

text: thermal

text: radiation

text: from

text: the

text: photosphere

text: This

text: radio

text: emission

text: was

text: associated

text: with

text: the

text: solar

text: Corona

text: region

text: In

text: the

text: solar

text: limb

text: brightening

text: and

text: the

text: solar

text: radii

text: below

text: GHz

text: was

text: theoretically

text: predicted.

text: This

text: early

text: work,

text: shows

text: that

text: the

text: solar

text: radii

text: grows

text: in

text: diameter

text: while

text: the

text: fre-

text: quency

text: of

text: the

text: emission

text: decreases.

text: The

text: observed

text: apparent

text: temperatures

text: was

text: associated

text: with

text: the

text: chromosphere

text: and

text: coronal

text: regions.

text: Several

text: observations

text: at

text: high

text: frequencies

text: were

text: performed

text: in

text: order

text: to

text: character-

text: ize

text: the

text: limb

text: brightening

text: (We

text: can

text: found

text: an

text: extended

text: review

text: about

text: the

text: observations

text: at

text: short

text: millimeter

text: range

text: in

text: These

text: works

text: show

text: that

text: the

text: theoretical

text: limb

text: brightening

text: could

text: be

text: aﬀected

text: by

text: the

text: spicules.

text: However,

text: shows

text: that

text: the

text: height

text: scale

text: of

text: the

text: tran-

text: sition

text: zone

text: model

text: is

text: unimportant.

text: Is

text: important

text: remark

text: that

text: these

text: ﬁrst

text: models

text: present

text: higher

text: temperature

text: minimum

text: than

text: the

text: actual

text: values.

text: The

text: temperature

text: minimum

text: plays

text: a

text: fundamental

text: role

text: in

text: the

text: chromospheric

text: emission

text: because

text: it

text: is

text: requiered

text: to

text: reproduce

text: observations

text: of

text: CO

text: moleculae.

text: The

text: CO

text: have

text: a

text: threshold

text: around

text: K

text: to

text: avoid

text: their

text: desintegration

text: The

text: relation

text: between

text: the

text: limb

text: brightening

text: and

text: the

text: microstructure

text: (spicules)

text: was

text: studied

text: in

text: detail

text: in

text: However,

text: the

text: approximation

text: of

text: full

text: ionizated

text: chromosphere

text: and

text: the

text: empirical

text: model

text: of

text: the

text: chromosphere

text: is

text: not

text: a

text: good

text: approximation

text: at

text: millimeter

text: region

text: besides

text: that

text: their

text: minimum

text: of

text: temperature

text: is

text: higher

text: than

text: K.

text: In

text: De

text: la

text: Luz

text: et

text: al

text: (under

text: review)

text: we

text: found

text: that

text: the

text: temperature

text: minimum

text: of

text: the

text: chromosphere

text: create

text: a

text: structure

text: called

text: Chromospheric

text: Solar

text: Millimeter-wave

text: Cav-

text: ity

text: (CSMC).

text: This

text: structure

text: is

text: the

text: responsible

text: of

text: the

text: morphology

text: of

text: the

text: solar

text: spectrum


text: 4 De la Luz, Chavez, and Bertone Figure 1. Local emission eﬃciency of the solar limb from 127 km (upper-left) to the 1018 km over the photosphere (bottom-right). We found three optical thick regions, while the computations move to the corona, these three regions move to the center and at the same time down in frequency. The 6th sub-ﬁgure (from up to down and from left to right) shows the at 840 km over the photosphere the two regions of emission merges in a single region. ##LTFigure## ##LTFigure##

text: De

text: la

text: Luz,

text: Chavez,

text: and

text: Bertone

text: Figure

text: Local

text: emission

text: eﬃciency

text: of

text: the

text: solar

text: limb

text: from

text: km

text: (upper-left)

text: to

text: the

text: km

text: over

text: the

text: photosphere

text: (bottom-right).

text: We

text: found

text: three

text: optical

text: thick

text: regions,

text: while

text: the

text: computations

text: move

text: to

text: the

text: corona,

text: these

text: three

text: regions

text: move

text: to

text: the

text: center

text: and

text: at

text: the

text: same

text: time

text: down

text: in

text: frequency.

text: The

text: sub-ﬁgure

text: (from

text: up

text: to

text: down

text: and

text: from

text: left

text: to

text: right)

text: shows

text: the

text: at

text: km

text: over

text: the

text: photosphere

text: the

text: two

text: regions

text: of

text: emission

text: merges

text: in

text: a

text: single

text: region.

text: ##LTFigure##

label: figure

text: ##LTFigure##