liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.ORCID-id: 0000-0003-2094-7376
Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.ORCID-id: 0000-0002-2081-2888
Visa övriga samt affilieringar
2016 (Engelska)Ingår i: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 17, nr 4, s. 695-725Artikel i tidskrift (Refereegranskat) Published
Resurstyp
Text
Abstract [en]

We study resource allocation in cellular systems and consider the problem of finding a power efficient scheduling in an uplink single carrier frequency division multiple access system. Due to the discrete nature of this problem and its computational difficulty, particularly in a real-time setting, the use of suboptimal algorithms is common practice. We aim at an effective way of gauging the performance of suboptimal algorithms by finding tight bounds on the global optimum. Toward this end, we first provide a basic integer linear programming formulation. Then we propose a significantly stronger column-oriented formulation and a corresponding column generation method, as well as an enhanced column generation scheme. The latter extends the first scheme through the inclusion of a stabilization technique, an approximate column generation principle, and a tailored heuristic that is embedded in the column generation scheme to find high-quality though not necessarily global optimal solutions. The computational evaluation demonstrates that compared with a poor performance by the integer linear programming formulation, the column generation method can produce near-optimal schedules that enable a sharp bounding interval. The enhanced column generation method significantly sharpens the bounding interval. Hence the column generation approach serves well for the purpose of benchmarking results for large-scale instances.

Ort, förlag, år, upplaga, sidor
Springer-Verlag New York, 2016. Vol. 17, nr 4, s. 695-725
Nyckelord [en]
Localized SC-FDMA, Stabilized column generation, Power minimization, Integer linear programming, Uplink scheduling, Matheuristic
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-127355DOI: 10.1007/s11081-015-9304-zISI: 000387857500004OAI: oai:DiVA.org:liu-127355DiVA, id: diva2:922125
Anmärkning

Funding agencies: Research School in Interdisciplinary Mathematics at Linkoping University; Excellence Center at Linkoping - Lund in Information Technology, Centrum for Industriell Informationsteknologi, Linkoping University, EC FP7 Marie Curie Project [318992]; Chinese Sc

Tillgänglig från: 2016-04-22 Skapad: 2016-04-22 Senast uppdaterad: 2019-08-06Bibliografiskt granskad
Ingår i avhandling
1. On the Integration of Heuristics with Column-Oriented Models for Discrete Optimization
Öppna denna publikation i ny flik eller fönster >>On the Integration of Heuristics with Column-Oriented Models for Discrete Optimization
2016 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Column-oriented models are today common in the eld of discrete optimization, and there is an increasing interest in using such models as a basis for heuristic solution methods. The common theme of this work is to explore some possibilities to integrate heuristic principles and column-oriented models for discrete optimization problems.

In the rst paper, we consider a resource allocation problem for cellular systems. We propose a strong column-oriented formulation and a corresponding column generation method, as well as an enhanced column generation scheme for this problem. The enhanced scheme is composed of a stabilization technique, an approximate column generation principle, and, for nding integer solutions, a heuristic that is embedded in the column generation scheme.

The second paper provides a new and strong convexied formulation of the xed charge transportation problem. This formulation is obtained by integrating the concepts of Lagrangian decomposition and column generation. It is shown both theoretically and practically that this integration yields a formulation which is stronger than three other convexied formulations of the problem.

Ort, förlag, år, upplaga, sidor
Linköping: Linköping University Electronic Press, 2016. s. 23
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1764
Nationell ämneskategori
Matematik Transportteknik och logistik
Identifikatorer
urn:nbn:se:liu:diva-127175 (URN)978-91-7685-769-4 (ISBN)
Disputation
2016-05-31, ACAS, A-huset, Campus Valla, Linköping, 13:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2016-04-22 Skapad: 2016-04-15 Senast uppdaterad: 2018-06-25Bibliografiskt granskad

Open Access i DiVA

fulltext(306 kB)188 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 306 kBChecksumma SHA-512
0b2e3cb9c1fc0da418acaeb09aa88e4cbae7ee59961c7ef66d77067b6de3adbc5b8e6994b54fae1183738c2499ad7c5f8d6c5f23440784ab6237c852e7055ed9
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextLänk till correction

Personposter BETA

Zhao, YixinLarsson, TorbjörnYuan, DiRönnberg, ElinaLei, Lei

Sök vidare i DiVA

Av författaren/redaktören
Zhao, YixinLarsson, TorbjörnYuan, DiRönnberg, ElinaLei, Lei
Av organisationen
OptimeringsläraTekniska fakultetenKommunikations- och transportsystem
I samma tidskrift
Optimization and Engineering
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 188 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 1251 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf