liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On the Integration of Heuristics with Column-Oriented Models for Discrete Optimization
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2016. , 23 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1764
National Category
Mathematics Transport Systems and Logistics
Identifiers
URN: urn:nbn:se:liu:diva-127175ISBN: 978-91-7685-769-4 (Print)OAI: oai:DiVA.org:liu-127175DiVA: diva2:921971
Public defence
2016-05-31, ACAS, A-huset, Campus Valla, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2016-04-22 Created: 2016-04-15 Last updated: 2016-04-22Bibliographically approved
List of papers
1. Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation
Open this publication in new window or tab >>Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation
Show others...
2015 (English)In: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, 1-31 p.Article in journal (Refereed) Epub ahead of print
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.

Place, publisher, year, edition, pages
Springer-Verlag New York, 2015
Keyword
Localized SC-FDMA, Stabilized column generation, Power minimization, Integer linear programming, Uplink scheduling, Matheuristic
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-127355 (URN)10.1007/s11081-015-9304-z (DOI)
Available from: 2016-04-22 Created: 2016-04-22 Last updated: 2016-05-03Bibliographically approved
2. Power efficient uplink scheduling in SC-FDMA: Bounding global optimality by column generation
Open this publication in new window or tab >>Power efficient uplink scheduling in SC-FDMA: Bounding global optimality by column generation
Show others...
2013 (English)In: 2013 IEEE 18th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD, IEEE , 2013, 119-123 p.Conference paper (Refereed)
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 (SC-FDMA) system with localized allocation of subcarriers, that is, the subcarriers allocated to a user equipment have to be consecutive in the frequency domain in each time slot. This problem is discrete and nonconvex, thus the use of suboptimal algorithms has been a common practice. We leverage the power of mathematical programming in order to approach global optimality or a tight bounding interval confining global optimum, to arrive at an effective scheme for gauging the performance of suboptimal algorithms. Toward this end, we first provide a straightforward integer linear programming formulation, and then an alternative and less trivial, so-called column-oriented, formulation. The latter is solved by column generation, which is a solution technique for large-scale optimization problems with certain characteristics. The computational evaluation demonstrates that the column generation method produces very highquality subcarrier allocations that either coincide with the global optimum or enable an extremely sharp bounding interval. Hence the approach serves well for the purpose of benchmarking results for large-scale instances of power efficient SC-FDMA scheduling.

Place, publisher, year, edition, pages
IEEE, 2013
Series
, International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), ISSN 2378-4865 ; 2013
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-106237 (URN)10.1109/CAMAD.2013.6708101 (DOI)
Conference
2013 IEEE 18th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD)
Available from: 2014-04-29 Created: 2014-04-29 Last updated: 2016-04-22

Open Access in DiVA

omslag(2701 kB)37 downloads
File information
File name COVER01.pdfFile size 2701 kBChecksum SHA-512
b93f722f5ac2c834d11c881f6027e30e15e8a1b960ba1000243758666869db161077a2338741c7b98b3fdabc391b303b8c39d12a891160aa939e935e54f1b2b0
Type coverMimetype application/pdf

Search in DiVA

By author/editor
Zhao, Yixin
By organisation
Optimization Faculty of Science & Engineering
MathematicsTransport Systems and Logistics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 1862 hits
ReferencesLink to record
Permanent link

Direct link