Clark School Home UMD

ISR News Story

Work by Raghavan, Chen, Ljubic wins Best Paper Award

“The Generalized Regenerator Location Problem,” a paper by Professor S. Raghavan (BMGT/ISR); his former student Si Chen (BMGT Ph.D. 2007), currently at the Federal Reserve; and Ivana Ljubić of the Essec Business School in Paris has been selected for the INFORMS Telecommunications Section Prize Best Paper Award. The prize is awarded by the Institute for Operations Research and the Management Sciences (INFORMS) Telecommunications Section for the most outstanding paper applying operation research techniques in the context of telecommunications.

The award was determined after a finalists presentation at the INFORMS Telecommunications Conference in March this year and will be formally presented at the INFORMS Annual Meeting in Nashville this November. It originally was published in the INFORMS Journal on Computing, 27(2), 204-220, 2015.

The paper deals with a problem in optical networks. In an optical network a signal can only travel a maximum distance dmax before its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. This paper introduces the generalized regenerator location problem (GRLP) in which we are given a set S of nodes that corresponds to candidate locations for regenerators, and a set T of nodes that must communicate with each other. This work actually builds upon earlier work where the same authors introduced and studied the case where S = T = N, which is referred to as the regenerator location problem (RLP).

Regenerator location problems are closely related to the network design problem with relays—where similar constraints on the optical reach are present but the network is designed considering paths from a single source. More recently, in the context of electric vehicle transportation networks, the location of charging stations has garnered significant interest. The location of these charging stations can be modeled as a generalized regenerator location problem. Thus the GRLP is significantly more general than previously considered versions of the problem.

There are several innovations within the paper:

• First within the problem definition the authors significantly expand the scope of the definition of the problem so that any regenerator location problem can be modeled as the generalized regenerator location problem.

• Next, they establish a correspondence between the (node-weighted) directed Steiner forest problem and the GRLP. Using this fact, they provide several ways to derive natural and extended integer programming (IP) and mixed-integer programming (MIP) models for the GRLP and compare the strength of these models. The strongest of these models is derived on natural node selection variables (i.e., there are no edge variables). This is very beneficial computationally, as the size of the models that can be solved to optimality dramatically increases.

• They develop a branch-and-cut approach to solve the problem to optimality. The results indicate that the exact approach can easily solve instances with up to 200 nodes to optimality.

• As an alternative, especially to find high quality solutions for large instances of the GRLP, they propose reduction procedures, two construction heuristics, and a local search procedure that they collectively refer to as a heuristic framework. Their computational results show the heuristic framework is a high-quality approach for solving large-scale GRLP instances.

Related Articles:
Raghavan wins INFORMS teaching prize
Ph.D. student Rui Zhang is second place winner in WINFORMS competition
CEE Ph.D. student James Jones wins WINFORMS Student Excellence Award
NEXTOR celebrates 20 years of aviation operations research
Barg, Tamo named winners of IEEE Information Theory Society Paper Awad
Khaligh Wins Best Vehicular Electronics Paper Award for Third Time
Ball gives plenary address at INFORMS Workshop
Arellano, Carney, Austin win Best Paper Award at ICONS 2015
Austin, Delgoshaei, Nguyen win MITRE Award at CSER
Alumna Enlu Zhou wins NSF CAREER Award for optimization and sampling in stochastic simulation

November 9, 2016


Prev   Next

 

 

Current Headlines

Alum Domenic Forte receives NSF CAREER Award

Danny Kim Named MWC/ARCS Lockheed Martin Scholar to Continue Research into Malware Mitigation Technology 

ENES 489P holds end-of-semester design contest

Congratulations, ISR graduates!

UMD's reACT Represents at the Smithsonian's Earth Optimism Summit

Miao Yu promoted to full professor

BBI FY17 Seed Grant Winners Announced

Alexander Pearse wins Dean's Doctoral Research Award

Eirini Eleni Tsiropoulou receives first Susan Frazier Postdoctoral Researcher Travel Award

Sayyed Sina Miran to receive Outstanding Graduate Assistant Award from UMD Graduate School

News Resources

Return to Newsroom

Search News

Archived News

Events Resources

Events Calendar