Parallel cross-entropy optimization

Gareth Evans; Jonathan Keith; Dirk Kroese

doi:10.1109/WSC.2007.4419854

Parallel cross-entropy optimization

Gareth Evans, Jonathan Keith, Dirk Kroese

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

17 Citations (Scopus)

Abstract

The Cross-Entropy (CE) method is a modem and effective optimization method well suited to parallel implementations. There is a vast array of problems today, some of which are highly complex and can take weeks or even longer to solve using current optimization techniques. This paper presents a general method for designing parallel CE algorithms for Multiple Instruction Multiple Data (MIMD) distributed memory machines using the Message Passing Interface (MPI) library routines. We provide examples of its performance for two well-known test-cases: the (discrete) Max-Cut problem and (continuous) Rosenbrock problem. Speedup factors and a comparison to sequential CE methods are reported.

Original language	English
Title of host publication	Proceedings of the 2007 Winter Simulation Conference
Editors	Shane Henderson, Ming-hua Hsieh
Place of Publication	USA
Publisher	IEEE, Institute of Electrical and Electronics Engineers
Pages	2196 - 2202
Number of pages	7
ISBN (Print)	9781424413058
DOIs	https://doi.org/10.1109/WSC.2007.4419854
Publication status	Published - 2007
Externally published	Yes
Event	Winter Simulation Conference 2007 - Washington, United States of America Duration: 9 Dec 2007 → 12 Dec 2007

Conference

Conference	Winter Simulation Conference 2007
Abbreviated title	WSC 2007
Country/Territory	United States of America
City	Washington
Period	9/12/07 → 12/12/07

Access to Document

10.1109/WSC.2007.4419854

Cite this

@inproceedings{1263adf65dc04c93956142a12df5995a,

title = "Parallel cross-entropy optimization",

abstract = "The Cross-Entropy (CE) method is a modem and effective optimization method well suited to parallel implementations. There is a vast array of problems today, some of which are highly complex and can take weeks or even longer to solve using current optimization techniques. This paper presents a general method for designing parallel CE algorithms for Multiple Instruction Multiple Data (MIMD) distributed memory machines using the Message Passing Interface (MPI) library routines. We provide examples of its performance for two well-known test-cases: the (discrete) Max-Cut problem and (continuous) Rosenbrock problem. Speedup factors and a comparison to sequential CE methods are reported.",

author = "Gareth Evans and Jonathan Keith and Dirk Kroese",

year = "2007",

doi = "10.1109/WSC.2007.4419854",

language = "English",

isbn = "9781424413058",

pages = "2196 -- 2202",

editor = "Shane Henderson and Ming-hua Hsieh",

booktitle = "Proceedings of the 2007 Winter Simulation Conference",

publisher = "IEEE, Institute of Electrical and Electronics Engineers",

address = "United States of America",

note = "Winter Simulation Conference 2007, WSC 2007 ; Conference date: 09-12-2007 Through 12-12-2007",

}

Evans, G, Keith, J & Kroese, D 2007, Parallel cross-entropy optimization. in S Henderson & M Hsieh (eds), Proceedings of the 2007 Winter Simulation Conference. IEEE, Institute of Electrical and Electronics Engineers, USA, pp. 2196 - 2202, Winter Simulation Conference 2007, Washington, District of Columbia, United States of America, 9/12/07. https://doi.org/10.1109/WSC.2007.4419854

Parallel cross-entropy optimization. / Evans, Gareth; Keith, Jonathan; Kroese, Dirk.

Proceedings of the 2007 Winter Simulation Conference. ed. / Shane Henderson; Ming-hua Hsieh. USA : IEEE, Institute of Electrical and Electronics Engineers, 2007. p. 2196 - 2202.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Parallel cross-entropy optimization

AU - Evans, Gareth

AU - Keith, Jonathan

AU - Kroese, Dirk

PY - 2007

Y1 - 2007

N2 - The Cross-Entropy (CE) method is a modem and effective optimization method well suited to parallel implementations. There is a vast array of problems today, some of which are highly complex and can take weeks or even longer to solve using current optimization techniques. This paper presents a general method for designing parallel CE algorithms for Multiple Instruction Multiple Data (MIMD) distributed memory machines using the Message Passing Interface (MPI) library routines. We provide examples of its performance for two well-known test-cases: the (discrete) Max-Cut problem and (continuous) Rosenbrock problem. Speedup factors and a comparison to sequential CE methods are reported.

AB - The Cross-Entropy (CE) method is a modem and effective optimization method well suited to parallel implementations. There is a vast array of problems today, some of which are highly complex and can take weeks or even longer to solve using current optimization techniques. This paper presents a general method for designing parallel CE algorithms for Multiple Instruction Multiple Data (MIMD) distributed memory machines using the Message Passing Interface (MPI) library routines. We provide examples of its performance for two well-known test-cases: the (discrete) Max-Cut problem and (continuous) Rosenbrock problem. Speedup factors and a comparison to sequential CE methods are reported.

UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4419854

U2 - 10.1109/WSC.2007.4419854

DO - 10.1109/WSC.2007.4419854

M3 - Conference Paper

SN - 9781424413058

SP - 2196

EP - 2202

BT - Proceedings of the 2007 Winter Simulation Conference

A2 - Henderson, Shane

A2 - Hsieh, Ming-hua

PB - IEEE, Institute of Electrical and Electronics Engineers

CY - USA

T2 - Winter Simulation Conference 2007

Y2 - 9 December 2007 through 12 December 2007

ER -

Parallel cross-entropy optimization

Abstract

Conference

Access to Document

Other files and links

Cite this