Optimization Online


An Exact Algorithm for a Resource Allocation Problem in Mobile Wireless Communications

Adam N. Letchford (A.N.Letchford***at***lancaster.ac.uk)
Qiang Ni (Q.Ni***at***lancaster.ac.uk)
Zhaoyu Zhong (Z.Zhong1***at***lancaster.ac.uk)

Abstract: We consider a challenging resource allocation problem arising in mobile wireless communications. The goal is to allocate the available channels and power in a so-called OFDMA system, in order to maximise the transmission rate, subject to quality of service (QoS) constraints. Standard MINLP software struggled to solve even small instances of this problem. Using outer approximation, perspective cuts and several implementation "tricks", we are able to solve realistic instances in about one minute. A novel ingredient of our algorithm is what we call pre-emptive cut generation: the generation of cutting planes that are not violated in the current iteration, but are likely to be violated in subsequent iterations.

Keywords: mixed-integer nonlinear programming, mobile wireless communications

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Now published as: A.N. Letchford, Q. Ni & Z. Zhong (2017) An exact algorithm for a resource allocation problem in mobile wireless communications. Comput. Optim. & Appl., 68(2), 193208.


Entry Submitted: 05/05/2016
Entry Accepted: 05/05/2016
Entry Last Modified: 09/23/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society