A Hybrid Cross-Entropy and Progressive Hedging Matheuristic with application to a RAPS System

A T Ernst, T Moore, B Owens, G Singh

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

In many applications the design of a system needs to be optimised but the effectiveness of the design choices can only be evaluated by considering the behaviour of the system over a longer time period or multiple scenarios. Here we develop a general hybrid matheuristic method that can be used in such situation sand apply it to a particular problem that arises in the design of a Remote Area Power Supply (RAPS) system in the presence of storage.

The major elements of our RAPS system include the load (demand for power), solar energy from photovoltaic (PV) panels, a diesel generator and a battery based storage facility. The aim is to find a fixed strategy is for using the diesel generator and battery storage facility to efficiently meet demand. Similar types of problems arise in a range of other design applications such as expansion planning of electricity transmission networks; selection and sizing of power generation facilities in a RAPS or electricity grid; or supply chain design (sizing warehouse storage and transport infrastructure). All of these applications can be formulated as large MIP models with have a similar structure: high level design variables relating to infrastructure or policy, and additional variables for evaluating the effectiveness of these decisions in a number of scenarios.

In this paper we consider how to deal with such problems by combining ideas from progressive hedging, a Lagrangian decomposition based method, with the cross-entropy optimisation meta-heuristic. We describe the general structure of mixed integer programming (MIP) problems to which this applies, show how our application can be formulated in this structure and then describe the new hybrid matheuristic. Indicative computational results are provided comparing the new method against the CPLEX integer programming solver, progressive hedging and cross-entropy optimisation.
Original languageEnglish
Title of host publicationMODSIM2015, 21st International Congress on Modelling and Simulation
EditorsRobert Anderssen, Tony Weber, Malcolm McPhee
Place of PublicationAustralia
PublisherModelling and Simulation Society of Australia and New Zealand
Pages1841-1847
Number of pages7
ISBN (Electronic)9780987214355
Publication statusPublished - 2015
EventInternational Congress on Modelling and Simulation 2015: Partnering with industry and the community for innovation and impact through modelling - Gold Coast Convention and Exhibition Centre, Broadbeach, Australia
Duration: 29 Nov 20154 Dec 2015
Conference number: 21st
https://web.archive.org/web/20150627050926/http://www.mssanz.org.au:80/modsim2015/
https://web.archive.org/web/20150626200712/http://mssanz.org.au:80/modsim2015/index.html

Conference

ConferenceInternational Congress on Modelling and Simulation 2015
Abbreviated titleMODSIM2015
CountryAustralia
CityBroadbeach
Period29/11/154/12/15
OtherThe 21st International Congress on Modelling and Simulation (MODSIM2015) was held at the Gold Coast Convention and Exhibition Centre, Broadbeach, Queensland, Australia from Sunday 29 November to Friday 4 December 2015.

It was held jointly with the 23rd National Conference of the Australian Society for Operations Research and the DSTO led Defence Operations Research Symposium (DORS 2015).

The theme for this event was Partnering with industry and the community for innovation and impact through modelling.
Internet address

Keywords

  • Matheuristics
  • progressive hedging
  • cross-entropy optimisation
  • remote area power supply

Cite this

Ernst, A. T., Moore, T., Owens, B., & Singh, G. (2015). A Hybrid Cross-Entropy and Progressive Hedging Matheuristic with application to a RAPS System. In R. Anderssen, T. Weber, & M. McPhee (Eds.), MODSIM2015, 21st International Congress on Modelling and Simulation (pp. 1841-1847). Australia: Modelling and Simulation Society of Australia and New Zealand.
Ernst, A T ; Moore, T ; Owens, B ; Singh, G. / A Hybrid Cross-Entropy and Progressive Hedging Matheuristic with application to a RAPS System. MODSIM2015, 21st International Congress on Modelling and Simulation. editor / Robert Anderssen ; Tony Weber ; Malcolm McPhee. Australia : Modelling and Simulation Society of Australia and New Zealand, 2015. pp. 1841-1847
@inproceedings{ff06e83f6b2e4c7cbd07870e45216a3b,
title = "A Hybrid Cross-Entropy and Progressive Hedging Matheuristic with application to a RAPS System",
abstract = "In many applications the design of a system needs to be optimised but the effectiveness of the design choices can only be evaluated by considering the behaviour of the system over a longer time period or multiple scenarios. Here we develop a general hybrid matheuristic method that can be used in such situation sand apply it to a particular problem that arises in the design of a Remote Area Power Supply (RAPS) system in the presence of storage.The major elements of our RAPS system include the load (demand for power), solar energy from photovoltaic (PV) panels, a diesel generator and a battery based storage facility. The aim is to find a fixed strategy is for using the diesel generator and battery storage facility to efficiently meet demand. Similar types of problems arise in a range of other design applications such as expansion planning of electricity transmission networks; selection and sizing of power generation facilities in a RAPS or electricity grid; or supply chain design (sizing warehouse storage and transport infrastructure). All of these applications can be formulated as large MIP models with have a similar structure: high level design variables relating to infrastructure or policy, and additional variables for evaluating the effectiveness of these decisions in a number of scenarios.In this paper we consider how to deal with such problems by combining ideas from progressive hedging, a Lagrangian decomposition based method, with the cross-entropy optimisation meta-heuristic. We describe the general structure of mixed integer programming (MIP) problems to which this applies, show how our application can be formulated in this structure and then describe the new hybrid matheuristic. Indicative computational results are provided comparing the new method against the CPLEX integer programming solver, progressive hedging and cross-entropy optimisation.",
keywords = "Matheuristics, progressive hedging, cross-entropy optimisation, remote area power supply",
author = "Ernst, {A T} and T Moore and B Owens and G Singh",
year = "2015",
language = "English",
pages = "1841--1847",
editor = "Robert Anderssen and Tony Weber and Malcolm McPhee",
booktitle = "MODSIM2015, 21st International Congress on Modelling and Simulation",
publisher = "Modelling and Simulation Society of Australia and New Zealand",
address = "New Zealand",

}

Ernst, AT, Moore, T, Owens, B & Singh, G 2015, A Hybrid Cross-Entropy and Progressive Hedging Matheuristic with application to a RAPS System. in R Anderssen, T Weber & M McPhee (eds), MODSIM2015, 21st International Congress on Modelling and Simulation. Modelling and Simulation Society of Australia and New Zealand, Australia, pp. 1841-1847, International Congress on Modelling and Simulation 2015, Broadbeach, Australia, 29/11/15.

A Hybrid Cross-Entropy and Progressive Hedging Matheuristic with application to a RAPS System. / Ernst, A T; Moore, T; Owens, B; Singh, G.

MODSIM2015, 21st International Congress on Modelling and Simulation. ed. / Robert Anderssen; Tony Weber; Malcolm McPhee. Australia : Modelling and Simulation Society of Australia and New Zealand, 2015. p. 1841-1847.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - A Hybrid Cross-Entropy and Progressive Hedging Matheuristic with application to a RAPS System

AU - Ernst, A T

AU - Moore, T

AU - Owens, B

AU - Singh, G

PY - 2015

Y1 - 2015

N2 - In many applications the design of a system needs to be optimised but the effectiveness of the design choices can only be evaluated by considering the behaviour of the system over a longer time period or multiple scenarios. Here we develop a general hybrid matheuristic method that can be used in such situation sand apply it to a particular problem that arises in the design of a Remote Area Power Supply (RAPS) system in the presence of storage.The major elements of our RAPS system include the load (demand for power), solar energy from photovoltaic (PV) panels, a diesel generator and a battery based storage facility. The aim is to find a fixed strategy is for using the diesel generator and battery storage facility to efficiently meet demand. Similar types of problems arise in a range of other design applications such as expansion planning of electricity transmission networks; selection and sizing of power generation facilities in a RAPS or electricity grid; or supply chain design (sizing warehouse storage and transport infrastructure). All of these applications can be formulated as large MIP models with have a similar structure: high level design variables relating to infrastructure or policy, and additional variables for evaluating the effectiveness of these decisions in a number of scenarios.In this paper we consider how to deal with such problems by combining ideas from progressive hedging, a Lagrangian decomposition based method, with the cross-entropy optimisation meta-heuristic. We describe the general structure of mixed integer programming (MIP) problems to which this applies, show how our application can be formulated in this structure and then describe the new hybrid matheuristic. Indicative computational results are provided comparing the new method against the CPLEX integer programming solver, progressive hedging and cross-entropy optimisation.

AB - In many applications the design of a system needs to be optimised but the effectiveness of the design choices can only be evaluated by considering the behaviour of the system over a longer time period or multiple scenarios. Here we develop a general hybrid matheuristic method that can be used in such situation sand apply it to a particular problem that arises in the design of a Remote Area Power Supply (RAPS) system in the presence of storage.The major elements of our RAPS system include the load (demand for power), solar energy from photovoltaic (PV) panels, a diesel generator and a battery based storage facility. The aim is to find a fixed strategy is for using the diesel generator and battery storage facility to efficiently meet demand. Similar types of problems arise in a range of other design applications such as expansion planning of electricity transmission networks; selection and sizing of power generation facilities in a RAPS or electricity grid; or supply chain design (sizing warehouse storage and transport infrastructure). All of these applications can be formulated as large MIP models with have a similar structure: high level design variables relating to infrastructure or policy, and additional variables for evaluating the effectiveness of these decisions in a number of scenarios.In this paper we consider how to deal with such problems by combining ideas from progressive hedging, a Lagrangian decomposition based method, with the cross-entropy optimisation meta-heuristic. We describe the general structure of mixed integer programming (MIP) problems to which this applies, show how our application can be formulated in this structure and then describe the new hybrid matheuristic. Indicative computational results are provided comparing the new method against the CPLEX integer programming solver, progressive hedging and cross-entropy optimisation.

KW - Matheuristics

KW - progressive hedging

KW - cross-entropy optimisation

KW - remote area power supply

UR - http://www.mssanz.org.au/modsim2015/J10/ernst.pdf

M3 - Conference Paper

SP - 1841

EP - 1847

BT - MODSIM2015, 21st International Congress on Modelling and Simulation

A2 - Anderssen, Robert

A2 - Weber, Tony

A2 - McPhee, Malcolm

PB - Modelling and Simulation Society of Australia and New Zealand

CY - Australia

ER -

Ernst AT, Moore T, Owens B, Singh G. A Hybrid Cross-Entropy and Progressive Hedging Matheuristic with application to a RAPS System. In Anderssen R, Weber T, McPhee M, editors, MODSIM2015, 21st International Congress on Modelling and Simulation. Australia: Modelling and Simulation Society of Australia and New Zealand. 2015. p. 1841-1847