liu.seSök publikationer i DiVA
Ändra sökning
Avgränsa sökresultatet
5678 351 - 367 av 367
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
• apa
• 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
Träffar per sida
• 5
• 10
• 20
• 50
• 100
• 250
Sortering
• Standard (Relevans)
• Författare A-Ö
• Författare Ö-A
• Titel A-Ö
• Titel Ö-A
• Publikationstyp A-Ö
• Publikationstyp Ö-A
• Äldst först
• Nyast först
• Skapad (Äldst först)
• Skapad (Nyast först)
• Senast uppdaterad (Äldst först)
• Senast uppdaterad (Nyast först)
• Disputationsdatum (tidigaste först)
• Disputationsdatum (senaste först)
• Standard (Relevans)
• Författare A-Ö
• Författare Ö-A
• Titel A-Ö
• Titel Ö-A
• Publikationstyp A-Ö
• Publikationstyp Ö-A
• Äldst först
• Nyast först
• Skapad (Äldst först)
• Skapad (Nyast först)
• Senast uppdaterad (Äldst först)
• Senast uppdaterad (Nyast först)
• Disputationsdatum (tidigaste först)
• Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
• 351.
Linköpings universitet, Filosofiska fakulteten. Linköpings universitet, Institutionen för datavetenskap, Statistik.
Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Filosofiska fakulteten. Linköpings universitet, Institutionen för datavetenskap, Statistik.
New optimization methods for isotonic regression in L1 norm2007Ingår i: EUROPT-OMS Conference on Optimization,2007, University of Hradec Kralove, Czech Republic: Guadeamus , 2007, s. 133-133Konferensbidrag (Övrigt vetenskapligt)

Isotonic regression problem (IR) has numerous important applications in statistics, operations research, biology, image and signal processing and other areas. IR is a minimization problem with the objective function defined by the distance from a given point to a convex set defined by monotonicity constraints of the form: i-th component of the decision vector is less or equal to its j-th component. The distance in IR is usually associated with the Lp norm, whereas the norms L1 and L2 are of the highest practical interest. The conventional optimization methods are unable to solve large-scale IR problems originating from large data sets. Historically, the major efforts were focused on IR problem in the L2 norm. Exact algorithms such as the minimum lower sets algorithm by Brunk, the min-max algorithm by Lee, the network flow algorithm by Maxwell & Muchstadt and the IBCR algorithm by Block et al. were developed. Among them the IBCR algorithm has been proved to be the most numerically efficient, but it is not robust enough. An alternative approach is related to solving IR problem approximately. Following this approach, Burdakov et al. developed GPAV algorithm whose block refinement extension, GPAVR, is able to solve IR problem with high accuracy in a far shorter time than the exact algorithms. Apart from this, GPAVR is a very robust algorithm. Unfortunately, for the norm L1 there are no algorithms which are as efficient as those in L2 norm. In our talk, we introduce new algorithms, GPAVR1 and IBCR1. They are extensions of the algorithms GPAV and IBCR to L1 norm. We present also results of numerical experiments, which demonstrate the high efficiency of the new algorithms, especially for very large-scale problems.

• 352.
Linköpings universitet, Institutionen för datavetenskap, Statistik. Linköpings universitet, Tekniska fakulteten.
Linköpings universitet, Institutionen för datavetenskap, Statistik. Linköpings universitet, Tekniska fakulteten. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
Bootstrap confidence intervals for large-scale multivariate monotonic regression problems2016Ingår i: Communications in statistics. Simulation and computation, ISSN 0361-0918, E-ISSN 1532-4141, Vol. 45, nr 3, s. 1025-1040Artikel i tidskrift (Refereegranskat)

Recently, the methods used to estimate monotonic regression (MR) models have been substantially improved, and some algorithms can now produce high-accuracy monotonic fits to multivariate datasets containing over a million observations. Nevertheless, the computational burden can be prohibitively large for resampling techniques in which numerous datasets are processed independently of each other. Here, we present efficient algorithms for estimation of confidence limits in large-scale settings that take into account the similarity of the bootstrap or jackknifed datasets to which MR models are fitted. In addition, we introduce modifications that substantially improve the accuracy of MR solutions for binary response variables. The performance of our algorithms isillustrated using data on death in coronary heart disease for a large population. This example also illustrates that MR can be a valuable complement to logistic regression.

• 353.
Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, Statistik.
Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, Statistik. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
Bootstrap estimation of the variance of the error term in monotonic regression models2013Ingår i: Journal of Statistical Computation and Simulation, ISSN 0094-9655, E-ISSN 1563-5163, Vol. 83, nr 4, s. 625-638Artikel i tidskrift (Refereegranskat)

The variance of the error term in ordinary regression models and linear smoothers is usually estimated by adjusting the average squared residual for the trace of the smoothing matrix (the degrees of freedom of the predicted response). However, other types of variance estimators are needed when using monotonic regression (MR) models, which are particularly suitable for estimating response functions with pronounced thresholds. Here, we propose a simple bootstrap estimator to compensate for the over-fitting that occurs when MR models are estimated from empirical data. Furthermore, we show that, in the case of one or two predictors, the performance of this estimator can be enhanced by introducing adjustment factors that take into account the slope of the response function and characteristics of the distribution of the explanatory variables. Extensive simulations show that our estimators perform satisfactorily for a great variety of monotonic functions and error distributions.

• 354.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
Manpower planning for airline pilots: A tabu search approach2010Självständigt arbete på avancerad nivå (magisterexamen), 20 poäng / 30 hpStudentuppsats (Examensarbete)

The airline industry faces some of the largest and most complicated optimization problems among all industries today. A large part of their costs iscrew costs and large savings can be made by efficient manpower planning. The research focus has been on the later steps in the planning process such as crew scheduling. The focus of this thesis is on the largely unexplored research area of staffing and transition planning for pilots. For the important question of which pilot should receive training to which position no solution strategy with optimization has, before this thesis, been presented. One reason for this might be that many complicated regulations concern this question, making an easily solved model impossible. I have developed a tabu search based algorithm with encouraging results. The algorithm was tested on data from Scandinavian Airlines. Compared to a reference algorithm based on commercial mixed integer programming software, the tabu search algorithm finds similar solutions about 30 times faster. I show how tabu search can be tailored to a specific complicated problem, and the results are good enough to not only be of theoretical interest but also of direct practical interest for use in the airline industry.

Ladda ner fulltext (pdf)
fulltext
• 355.
Forest Res, Rotorua, New Zealand Linkoping Univ, Div Optimizat, SE-58183 Linkoping, Sweden.
Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
Dynamic control of timber production at a sawmill with log sawing optimization2002Ingår i: Scandinavian Journal of Forest Research, ISSN 0282-7581, E-ISSN 1651-1891, Vol. 17, nr 1, s. 79-89Artikel i tidskrift (Refereegranskat)

Today most sawmills use optimization techniques to maximize yields from logs. If open market conditions are assumed when maximizing volume or value yields, overproduction of some products and underproduction of others may result. In this study, a system is described that links production with log sawing optimization while also addressing demands for timber products of differing qualities. The system is based on an optimization framework that is implemented in a log sawing simulator, AUTOSAW. Unlike other optimization systems that use static product "values" such as board volume or timber price, dynamic values are used that are updated regularly according to previous timber production. The efficiency of the system was tested with three orderbooks, via comparisons with volume- and value-optimized solutions obtained from sawing pruned Pinus radiata D. Don logs. In each case, product optimization required fewer logs to satisfy all demands than did either volume or value optimization. Furthermore, underproduction was eliminated and overproduction reduced.

• 356.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
Accelerating column generation schemes: applications to routing problems2005Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)

Many integer optimization problems of great practical importance are today attacked with column generation. Merits of column generation is that it enables the use of compact and flexible formulations of many complex optimization problems, and that it often gives rise to good (strong) formulations. A potential drawback with column generation is the well-known tailing-off phenomenon, that is, that the objective value is improved rapidly in early iterations but very slowly in the late iterations.

We study various techniques for accelerating column generation methods for (integer) linear programs. We evaluate the use of stabilized column generation on a Traveling Salesman Subtour Problem, TSSP, a problem which is closely related to the Prize Collecting Traveling Salesman Problem. We further study how subgradient optimization can be used with the purpose of predicting optimal columns (and, optionally, non-binding restrictions). This technique is tested on the TSSP and the multicommodity network flow problem.

Another idea evaluated in this thesis is the use of over-generation of columns in a column generation scheme for an integer programming problem, in this case a vehicle routing problem with a heterogeneous fleet of vehicles.

The thesis also includes a note on a class of relatives to the Held and Karp 1–tree problem. It is shown that two subclasses have polynomial time-complexity. Further, we note a mistake in an earlier work and provide a counter-example to the erroneous result.

1. A stabilized column generation scheme for the traveling salesman subtour problem
Öppna denna publikation i ny flik eller fönster >>A stabilized column generation scheme for the traveling salesman subtour problem
2006 (Engelska)Ingår i: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 154, nr 15, s. 2212-2238Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.

We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.

Matematik
Identifikatorer
urn:nbn:se:liu:diva-36277 (URN)10.1016/j.dam.2005.04.012 (DOI)30825 (Lokalt ID)30825 (Arkivnummer)30825 (OAI)
Tillgänglig från: 2009-10-10 Skapad: 2009-10-10 Senast uppdaterad: 2017-12-13
2. A note on relatives to the Held and Karp 1-tree problem
Öppna denna publikation i ny flik eller fönster >>A note on relatives to the Held and Karp 1-tree problem
2006 (Engelska)Ingår i: Operations Research Letters, ISSN 0167-6377, E-ISSN 1872-7468, Vol. 34, nr 3, s. 275-282Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We study a class of graph problems which includes as special cases the Held and Karp 1-tree problem, and the minimum spanning tree problem with one degree constraint studied by Glover and Klingman. For another special case, we note a mistake in a paper by Ramesh, Yoon and Karwan.

Matematik
Identifikatorer
urn:nbn:se:liu:diva-36273 (URN)10.1016/j.orl.2005.04.010 (DOI)30783 (Lokalt ID)30783 (Arkivnummer)30783 (OAI)
Tillgänglig från: 2009-10-10 Skapad: 2009-10-10 Senast uppdaterad: 2017-12-13
3. Subgradient optimization prior to column generation: a means for predicting optimal columns (and non-binding restrictions)
Öppna denna publikation i ny flik eller fönster >>Subgradient optimization prior to column generation: a means for predicting optimal columns (and non-binding restrictions)
2005 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

Many classes of combinatorial and mixed integer optimization problems are attacked with decomposition methods. One technique is to perform subgradient optimization on a Lagrangean dual problem: another is to perform column generation on a Dantzig-Wolfe problem, or equivalently, cut generation on its linear programming dual. These techniques both have advantages and disadvantages. In this paper these techniques are combined into a two-phase method, with the purpose of overcoming drawbacks of the techniques.

The two-phase method consists of a prediction phase and a solution phase. In the prediction phase, subgradient optimization is performed: subgradients found are stored and used as starting columns for the solution phase. (Optionally, non-binding restricitions can be predicted based on information from the prediction phase.) The columns found are used to construct a Dantzig/Wolfe master problem. In the solution phase, column generation is performed if needed. A solid theoretical bases for the two-phase method is presented which includes strong asymptotical results. ln practise, truncated usage must be performed: practical guidelines are given in the paper.

The two-phase method is tested on two applications: a multicommodity network flow problem and a convexified version of the traveling salesman subtour problem. Two categories of numerical experiments are presented. ln the first category, various aspects of truncated usage of the theory are illustrated. In the second category, the two-phase method is tested on a relatively large number of test problems.

An overall conclusion of our work is that the two-phase method can perform significantly better, in terms of CPU-times, compared to a (stabilized) Dantzig-Wolfe algorithm. ln general, whenever the subproblems are computationaly inexpensive, compared to the Dantzig-Wolfe master programs, the two-phase method might be an interesting alternative to use instead of pure Dantzig-Wolfe.

Ort, förlag, år, upplaga, sidor
Linköping: Linköpings universitet, 2005
Serie
LiTH-MAT-R ; 77
Matematik
Identifikatorer
urn:nbn:se:liu:diva-29698 (URN)15091 (Lokalt ID)15091 (Arkivnummer)15091 (OAI)
Tillgänglig från: 2009-10-09 Skapad: 2009-10-09 Senast uppdaterad: 2013-08-30
4. A column generation scheme for the fixed fleet heterogeneous vehicle routing problem
Öppna denna publikation i ny flik eller fönster >>A column generation scheme for the fixed fleet heterogeneous vehicle routing problem
2005 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

We present an optimizing column generation procedure for solving the vehicle routing problem with a fixed heterogeneous fleet of vehicles; if the method is used in a truncated fashion it turns into a heuristic. The method is based on a new mathematical formulation, which includes a new type of valid inequalities, strengthened by the use of Chvátal-Gomory rounding, and a Lagrangian dualization of this formulation. The dual problem is attacked by subgradient optimization and a near-optimal dual solution obtained is used for enumerating routes that are promising candidates for being used in an optimal solution. These routes are collected in a set partitioning problem, which is finally solved, and an upper bound to the optimal objective value is obtained. The method is evaluated on a set of small-scale test instances. The valid inequalities improves the lower bound significantly: the improvement depends on the ratio between total customer demand and total vehicle capacity. The qualities of the upper bounds varies quite much among the instances.

Ort, förlag, år, upplaga, sidor
Linköping: Linköpings universitet, 2005
Serie
LiTH-MAT-R ; 12
Matematik
Identifikatorer
urn:nbn:se:liu:diva-29699 (URN)15092 (Lokalt ID)15092 (Arkivnummer)15092 (OAI)
Tillgänglig från: 2009-10-09 Skapad: 2009-10-09 Senast uppdaterad: 2013-08-30
• 357.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
Decomposition schemes for the traveling salesman subtour problem2002Licentiatavhandling, monografi (Övrigt vetenskapligt)

Given an undirected graph with edge costs and both revenues and weights on the vertices, the Traveling Salesman Subtour Problem is to find a subtour that passes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour. This problem generalizes the Traveling Salesman Problem and is therefore $\tiny\mathcal{N} \mathcal{P}$-hard. The Traveling Salesman Subtour Problem and its relatives are of interest in themselves, and they also arise as subproblems in various contexts.

We present a new and strong formulation, which is inspired by the classic side-constrained 1-tree formulation of the Traveling Salesman Problem. Here, the side constraints comprise vertex degree restrictions, a knapsack constraint and variable upper bound (VUB) constraints. In our solution approaches, these side constraints are Lagrangian relaxed. The relaxed problem is transformed, via a simple variable substitution, into the problem of finding a minimum cost degree-constrained 1-tree in an expanded graph.

The Lagrangian dual problem is attacked with subgradient optimization and a cutting plane scheme. The latter is implemented in its dually equivalent form, that is, as a column generation scheme. The column generation procedure is stabilized by restricting the dual variables to stay inside a box around the current dual iterate; this technique is a slight modification of the so called boxstep method. Further, a combined algorithm is presented. This combination inherits the advantages of subgradient optimization and column generation, and it aims to avoid their respective drawbacks.

An important conclusion from our work is that the use of the VUB constraints significantly improves the quality of the lower bounds, although they are redundant in the integer programming formulation. We also conclude that the stabilizing technique is crucial for obtaining computational efficiency in the column generation scheme. Finally, it is established that it might be very advantageous to use the subgradient optimization procedure as a means for initiating the column generation scheme.

• 358.
Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
Tree-relaxations of relatives to the Traveling Salesman Problem2004Ingår i: Workshop i tillämpad matematik,2004, 2004Konferensbidrag (Övrigt vetenskapligt)
• 359.
Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära.
Mathematical Formulations of the Heterogeneous Fleet Vehicle Routing Problem2003Ingår i: ROUTE 2003, International Workshop on Vehicle Routing, Intermodal Transport and related areas,2003, 2003Konferensbidrag (Övrigt vetenskapligt)
• 360.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
Power efficient uplink scheduling in SC-FDMA: Bounding global optimality by column generation2013Ingår i: 2013 IEEE 18th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD, IEEE , 2013, s. 119-123Konferensbidrag (Refereegranskat)

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.

• 361.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
On the Integration of Heuristics with Column-Oriented Models for Discrete Optimization2016Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)

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.

1. Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation
Öppna denna publikation i ny flik eller fönster >>Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation
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
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
Nyckelord
Localized SC-FDMA, Stabilized column generation, Power minimization, Integer linear programming, Uplink scheduling, Matheuristic
Matematik
Identifikatorer
urn:nbn:se:liu:diva-127355 (URN)10.1007/s11081-015-9304-z (DOI)000387857500004 ()
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
2. Power efficient uplink scheduling in SC-FDMA: Bounding global optimality by column generation
Öppna denna publikation i ny flik eller fönster >>Power efficient uplink scheduling in SC-FDMA: Bounding global optimality by column generation
2013 (Engelska)Ingår i: 2013 IEEE 18th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD, IEEE , 2013, s. 119-123Konferensbidrag, Publicerat paper (Refereegranskat)
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.

IEEE, 2013
Serie
International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), ISSN 2378-4865 ; 2013
Matematik
Identifikatorer
urn:nbn:se:liu:diva-106237 (URN)10.1109/CAMAD.2013.6708101 (DOI)
Konferens
2013 IEEE 18th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD)
Tillgänglig från: 2014-04-29 Skapad: 2014-04-29 Senast uppdaterad: 2018-06-25
Ladda ner (pdf)
omslag
Ladda ner (jpg)
presentationsbild
• 362.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
A Large Neighbourhood Search Principle for Column-Oriented Models: Theoretical Derivation and Example Applications2016Ingår i: Matheuristics 2016: Proceedings of the Sixth International Workshop on Model-based Metaheuristics / [ed] V. Maniezzo and T. Stutzle, Bruxelles, Belgium: IRIDIA , 2016Konferensbidrag (Refereegranskat)
• 363.
Nanjing University of Science and Technology, School of Automation.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
An integer programming column generation principlefor heuristic search methods2019Ingår i: International Transactions in Operational Research, ISSN 0969-6016, E-ISSN 1475-3995, Vol. 27, nr 1, s. 665-695Artikel i tidskrift (Refereegranskat)

There is an increasing interest in integrating column generation and heuristic approaches to efficiently solve large-scale discrete optimisation problems. We contribute in this direction. Based on the insights from Lagrangian duality theory, we present an auxiliary problem that can be used for finding near-optimal solutions to a discrete column-oriented model. The structure of this auxiliary problem makes it suitable for being addressed with a heuristic search method involving column generation. To this end, we suggest a large neighbourhood search strategy where the repair step is to solve a column generation type subproblem. The suggested search strategy and mathematical models involved need to be tailored to the problem structure. To illustrate important design options and computational behaviour, four applications are studied: bin packing, generalised assignment, a resource allocation problem and the fixed-charge transportation problem.

• 364.
Nanjing University of Science and Technology, School of Automation.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. University of Florida, Department of Industrial and System Engineering.
The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation2018Ingår i: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 72, nr 3, s. 517-538Artikel i tidskrift (Refereegranskat)

A new and strong convexified formulation of the fixed charge transportation problem is provided. This formulation is obtained by integrating the concepts of Lagrangian decomposition and column generation. The decomposition is made by splitting the shipping variables into supply and demand side copies, while the columns correspond to extreme flow patterns for single sources or sinks. It is shown that the combination of Lagrangian decomposition and column generation provides a formulation whose strength dominates those of three other convexified formulations of the problem. Numerical results illustrate that our integrated approach has the ability to provide strong lower bounds. The Lagrangian decomposition yields a dual problem with an unbounded set of optimal solutions. We propose a regularized column generation scheme which prioritizes an optimal dual solution with a small 1-norm. We further demonstrate numerically that information gained from the strong formulation can also be used for constructing a small-sized core problem which yields high-quality upper bounds.

• 365.
Nanjing Univ Sci and Technol, Peoples R China.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. 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. Linköpings universitet, Institutionen för teknik och naturvetenskap. Linköpings universitet, Tekniska fakulteten.
Correction: Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation (vol 17, pg 695, 2016)2019Ingår i: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 20, nr 3, s. 959-959Artikel i tidskrift (Övrigt vetenskapligt)

At the time of the final publication of the paper, in December 2016, Yixin Zhaos affiliation had changed.

• 366.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. 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. Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation2016Ingår i: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 17, nr 4, s. 695-725Artikel i tidskrift (Refereegranskat)

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.

Ladda ner fulltext (pdf)
fulltext
• 367. Köp publikationen >>
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
Large-Scale Optimization Methods with Application to Design of Filter Networks2014Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)

Nowadays, large-scale optimization problems are among those most challenging. Any progress in developing methods for large-scale optimization results in solving important applied problems more effectively. Limited memory methods and trust-region methods represent two ecient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited memory methods are usually combined with a line search. We develop new limited memory trust-region algorithms for large-scale unconstrained optimization. They are competitive with the traditional limited memory line-search algorithms.

In this thesis, we consider applied optimization problems originating from the design of lter networks. Filter networks represent an ecient tool in medical image processing. It is based on replacing a set of dense multidimensional lters by a network of smaller sparse lters called sub-filters. This allows for improving image processing time, while maintaining image quality and the robustness of image processing.

Design of lter networks is a nontrivial procedure that involves three steps: 1) choosing the network structure, 2) choosing the sparsity pattern of each sub-filter and 3) optimizing the nonzero coecient values. So far, steps 1 and 2 were mainly based on the individual expertise of network designers and their intuition. Given a sparsity pattern, the choice of the coecients at stage 3 is related to solving a weighted nonlinear least-squares problem. Even in the case of sequentially connected lters, the resulting problem is of a multilinear least-squares (MLLS) type, which is a non-convex large-scale optimization problem. This is a very dicult global optimization problem that may have a large number of local minima, and each of them is singular and non-isolated. It is characterized by a large number of decision variables, especially for 3D and 4D lters.

We develop an effective global optimization approach to solving the MLLS problem that reduces signicantly the computational time. Furthermore, we  develop efficient methods for optimizing sparsity of individual sub-filters  in lter networks of a more general structure. This approach offers practitioners a means of nding a proper trade-o between the image processing quality and time. It allows also for improving the network structure, which makes automated some stages of designing lter networks.

1. On Efficiently Combining Limited Memory and Trust-Region Techniques
Öppna denna publikation i ny flik eller fönster >>On Efficiently Combining Limited Memory and Trust-Region Techniques
2013 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

Limited memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited memory methods are usually combined with a line search. We show how to efficiently combine limited memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead compared with the cost of computing the quasi-Newton direction in line-search limited memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.

Ort, förlag, år, upplaga, sidor
Linköping: Linköping University Electronic Press, 2013. s. 33
Serie
LiTH-MAT-R, ISSN 0348-2960 ; 2013:13
Nyckelord
Unconstrained Optimization; Large-scale Problems; Limited Memory Methods;
Nationell ämneskategori
Beräkningsmatematik
Identifikatorer
urn:nbn:se:liu:diva-102005 (URN)LiTH-MAT-R--2013/13--SE (ISRN)
Tillgänglig från: 2013-11-26 Skapad: 2013-11-26 Senast uppdaterad: 2016-01-12Bibliografiskt granskad
2. Global search strategies for solving multilinear least-squares problems
Öppna denna publikation i ny flik eller fönster >>Global search strategies for solving multilinear least-squares problems
2012 (Engelska)Ingår i: Sultan Qaboos University Journal for Science, ISSN 1027-524X, Vol. 17, nr 1, s. 12-21Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

The multilinear least-squares (MLLS) problem is an extension of the linear leastsquares problem. The difference is that a multilinear operator is used in place of a matrix-vector product. The MLLS is typically a large-scale problem characterized by a large number of local minimizers. It originates, for instance, from the design of filter networks. We present a global search strategy that allows for moving from one local minimizer to a better one. The efficiency of this strategy is illustrated by results of numerical experiments performed for some problems related to the design of filter networks.

Ort, förlag, år, upplaga, sidor
Sultan Qaboos University, 2012
Nyckelord
Global optimization; Global search strategies; Multilinear least-squares; Filter
Nationell ämneskategori
Beräkningsmatematik Medicinsk bildbehandling
Identifikatorer
urn:nbn:se:liu:diva-78918 (URN)
Tillgänglig från: 2012-08-28 Skapad: 2012-06-25 Senast uppdaterad: 2015-09-03Bibliografiskt granskad
3. Sparsity Optimization in Design of Multidimensional Filter Networks
Öppna denna publikation i ny flik eller fönster >>Sparsity Optimization in Design of Multidimensional Filter Networks
2013 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

Filter networks is a powerful tool used for reducing the image processing time, while maintaining its reasonably high quality.They are composed of sparse sub-filters whose low sparsity ensures fast image processing.The filter network design is related to solvinga sparse optimization problem where a cardinality constraint bounds above the sparsity level.In the case of sequentially connected sub-filters, which is the simplest network structure of those considered in this paper, a cardinality-constrained multilinear least-squares (MLLS) problem is to be solved. If to disregard the cardinality constraint, the MLLS is typically a large-scale problem characterized by a large number of local minimizers. Each of the local minimizers is singular and non-isolated.The cardinality constraint makes the problem even more difficult to solve.An approach for approximately solving the cardinality-constrained MLLS problem is presented.It is then applied to solving a bi-criteria optimization problem in which both thetime and quality of image processing are optimized. The developed approach is extended to designing filter networks of a more general structure. Its efficiency is demonstrated by designing certain 2D and 3D filter networks. It is also compared with the existing approaches.

Ort, förlag, år, upplaga, sidor
Linköping: Linköping University Electronic Press, 2013. s. 21
Serie
LiTH-MAT-R, ISSN 0348-2960 ; 2013:16
Nyckelord
Sparse optimization; Cardinality Constraint; Multicriteria Optimization; Multilinear Least-Squares Problem; Filter networks; Medical imaging
Nationell ämneskategori
Beräkningsmatematik Medicinsk bildbehandling Signalbehandling
Identifikatorer
urn:nbn:se:liu:diva-103915 (URN)LiTH-MAT-R-2013/16-SE (ISRN)
Tillgänglig från: 2014-02-03 Skapad: 2014-02-03 Senast uppdaterad: 2016-11-24Bibliografiskt granskad
Ladda ner fulltext (pdf)
Large-Scale Optimization Methods with Application to Design of Filter Networks
Ladda ner (pdf)
omslag
5678 351 - 367 av 367
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
• apa
• 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