Conic Approximation with Provable Guarantee for Traffic Signal Offset Optimization

Yi Ouyang, Richard Y. Zhang, Javad Lavaei, Pravin Varaiya

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the offset optimization problem that coordinates the offsets of signalized intersections to reduce vehicle queues in large-scale signalized traffic networks. We adopt a recent approach that transforms the offset optimization problem into a complex-valued quadratically-constrained quadratic program (QCQP). Using the special structure of the QCQP, we provide a π /4-approximation algorithm to find a near-global solution based on the optimal solution of a semidefinite program (SDP) relaxation. Although large-scale SDPs are generally hard to solve, we exploit sparsity structures of traffic networks to propose a numerical algorithm that is able to efficiently solve the SDP relaxation of the offset optimization problem. The developed algorithm relies on a tree decomposition to reformulate the large-scale problem into a reduced-complexity SDP. Under the practical assumption that a real-world traffic network has a bounded treewidth, we show that the complexity of the overall algorithm scales near-linearly with the number of intersections. The results of this work, including the bounded treewidth property, are demonstrated on the Berkeley, Manhattan, and Los Angeles networks. From numerical experiments it is observed that the algorithm has a linear empirical time complexity, and the solutions of all cases achieve a near-globally optimal guarantee of more than 0.99.

Original languageEnglish (US)
Title of host publication2018 IEEE Conference on Decision and Control, CDC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)9781538613955
StatePublished - Jan 18 2019
Externally publishedYes
Event57th IEEE Conference on Decision and Control, CDC 2018 - Miami, United States
Duration: Dec 17 2018Dec 19 2018

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546


Conference57th IEEE Conference on Decision and Control, CDC 2018
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'Conic Approximation with Provable Guarantee for Traffic Signal Offset Optimization'. Together they form a unique fingerprint.

Cite this